100 Same Tree

title: Same Tree
tags:
- same-tree
- No.100
- simple
- tree
- recurrence
- depth-first-search

Description

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

Example 3:

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

Corner Cases

• two empty trees
• one empty tree
• null node

Solutions

Pre-Order Depth First Search

Take depth first search to compare sub-trees. Use pre-order because we can stop the program as soon as an inequal case is detected.

For any tree node, if the height of the left sub-tree is h_L and the height of the right one is h_R, then we have:

T(\max\{h_L, h_R\} + 1) = T(h_L) + T(h_R) + O(1)

Since we visit each edge and vertex once, then running time is O(V + E).

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return isSameSubTree(p, q);
    }
    
    private boolean isSameSubTree(TreeNode sp, TreeNode sq) {
        if (sp == null && sq == null) {return true;}
        if (sp == null || sq == null) {return false;}
        else if (sp.val != sq.val)    {return false;}
        
        boolean leftSame  = isSameSubTree(sp.left, sq.left);
        boolean rightSame = isSameSubTree(sp.right, sq.right);
        return leftSame && rightSame;
    }
}

Stack Without Recurrence

Use stack to implement pre-order DFS and compare the two trees.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Stack<TreeNode> sp = new Stack<TreeNode>();
        Stack<TreeNode> sq = new Stack<TreeNode>();

        TreeNode xp = p;
        TreeNode xq = q;

        if (p == null && q != null) {return false;}

        while (xp != null || !sp.empty()) {
            if (xp != null) {
                if (xq == null)       {return false;}
                if (xp.val != xq.val) {return false;}
                sp.push(xp);
                sq.push(xq);
                xp = xp.left;
                xq = xq.left;
            } else { //xp == null && !sp.empty()
                if (xq != null) {return false;}
                TreeNode tp = sp.pop();
                TreeNode tq = sq.pop();
                xp = tp.right;
                xq = tq.right;
            }
        }
        return true;
    }
}