101. Symmetric Tree

Description

Given a binary tree, check whether it is a mirror of itself (i.e, symmetric around its center).

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: [1, 2, 2, 3, 4, 4, 3]

Output: true

Example 2

Input: [1, 2, 2, null, 3, null, 3]

Output: false

Solutions

TreeNode

// 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;
    }
}

Solution 1

/**
 * Time complexity : O(n). Because we traverse the entire input tree once, the 
 *    total run time is O(n), where n is the total number of nodes in the tree.
 * Space complexity : The number of recursive calls is bound by the height of 
 *    the tree. In the worst case, the tree is linear and the height is in O(n). 
 *    Therefore, space complexity due to recursive calls on the stack is O(n) 
 *    in the worst case.
 */

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

Solution 2

/**
 * Time complexity : O(n). Because we traverse the entire input tree once, the 
 *    total run time is O(n), where n is the total number of nodes in the tree.
 * Space complexity : There is additional space required for the search queue. 
 *    In the worst case, we have to insert O(n) nodes in the queue. Therefore, 
 *    space complexity is O(n).
 */

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        Queue<TreeNode> queue = new LinkedList();
        queue.add(root);
        queue.add(root);
        while(!queue.isEmpty()) {
            TreeNode node1 = queue.poll();
            TreeNode node2 = queue.poll();
            if(node1 == null && node2 == null) continue;
            if(node1 == null || node2 == null) return false;
            if(node1.val != node2.val) return false;
            queue.add(node1.left);
            queue.add(node2.right);
            queue.add(node1.right);
            queue.add(node2.left);
        }
        return true;
    }
}

Follow up