algoadvance

Leetcode 101. Symmetric Tree

Problem Statement

LeetCode Problem 101: Symmetric Tree

Given the root of a binary tree, determine if it is a mirror of itself (i.e., symmetric around its center).

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]
Output: false

Clarifying Questions

  1. What do the tree nodes contain?
    • The tree nodes contain integer values.
  2. Can the tree be empty?
    • Yes, an empty tree (where root is null) should be considered symmetric.
  3. Is there any particular size constraint on the binary tree?
    • The problem does not specify any constraints on the size of the tree, so we can assume it can be large.

Strategy

We’ll use recursion to check for symmetry. For a tree to be symmetric, its left subtree must be a mirror reflection of its right subtree. Here’s the plan:

  1. Start with the root node.
  2. Create a helper function that checks if two trees are mirror images of each other.
  3. This helper function will:
    • Compare the values of two nodes.
    • Recursively check the left subtree of the left node with the right subtree of the right node.
    • Recursively check the right subtree of the left node with the left subtree of the right node.
  4. Return true if the above conditions satisfy, otherwise false.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isMirror(root.left, root.right);
    }
    
    private boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            return true;
        }
        if (t1 == null || t2 == null) {
            return false;
        }
        return (t1.val == t2.val)
            && isMirror(t1.right, t2.left)
            && isMirror(t1.left, t2.right);
    }
}

Time Complexity

The time complexity of this solution is (O(n)), where (n) is the number of nodes in the tree. This is because we perform a constant amount of work per node (comparing values and making recursive calls), and thus visit each node once.

The space complexity is (O(h)), where (h) is the height of the tree. This is due to the recursive call stack, which in the worst case (for a completely unbalanced tree) can be as deep as the height of the tree. In the best case (for a completely balanced tree), the height would be (O(\log n)).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI