101 Symmetric Tree

title: Symmetric Tree
tags:
- symmetric-tree
- No.101
- simple
- tree
- depth-first-search
- recurrence
- stack

Description

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

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

Corner Cases

• empty tree
• single root

Solutions

Pre-Order Depth First Search

For root node, we have two sub-trees:

     +----- root -----+
     |                |
Left Sub-Tree   Right Sub-Tree

Use pre-order dfs to visit the two sub-trees and return false as long as the nodes in them are inequivalent. Compare left with right and right with left.

The running time is O(V+E), same as dfs in graph.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return (root == null) ? true : isSymmetricSubTree(root.left, root.right);
    }
    
    private boolean isSymmetricSubTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {return true;}
        if (p == null || q == null) {return false;}
        else if (p.val != q.val)    {return false;}
        
        boolean leftRight = isSymmetricSubTree(p.left, q.right);
        boolean rightLeft = isSymmetricSubTree(p.right, q.left);
        return leftRight && rightLeft;
    }
}

Stack Without Recurrence

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {return true;}
        
        Stack<TreeNode> sl = new Stack<TreeNode>();
        Stack<TreeNode> sr = new Stack<TreeNode>();
        
        TreeNode xl = root.left;
        TreeNode xr = root.right;
        
        if (xl == null && xr != null) {return false;}
        
        while(xl != null || !sl.empty()) {
            if (xl != null) {
                if (xr == null)       {return false;}
                if (xl.val != xr.val) {return false;}
                sl.push(xl);
                sr.push(xr);
                xl = xl.left;
                xr = xr.right;
            }
            else {
                if (xr != null) {return false;}
                xl = sl.pop();
                xr = sr.pop();
                xl = xl.right;
                xr = xr.left;
            }
        }        
        return !(xr != null || !sr.empty());
    }
}