Same Tree

Problem:

Given two binary trees, check if they are the same.

Two binary trees are considered the same if they have the same structure and same node values.

For example, the following trees are the same

    1         1

   / \       / \

  2   3     2   3

but the following trees are not the same

    1         1

   / \       / \

  2   4     2   3

the following trees are not the same too

    1         1

   /           \

  2             2

follow up questions: the recursive solution is trivial, can we solve it with iteration?

Solution:

One of the recursive solution is to do a preorder traversal of the trees. If the current nodes are the same, then we recursively exam the left children and right children.

To convert the recursive solution to iterative solution. We need to use a stack or queue to replace the internal caller stack. We can choose to use a queue to store the nodes, thus make a level order traversal of the tree, or we can use a stack to store the nodes, and do a in-order or pre-order traversal. 

import java.util.*;
class Solution {
 
  public static void main(String...args) {
    Node tree1 = new Node(1, new Node(2), new Node(3));
    Node tree2 = new Node(1, new Node(2), new Node(3));
    System.out.println(isSame(tree1, tree2)); 
    System.out.println(isSame2(tree1, tree2)); 
  }
 
  private static boolean isSame(Node root1, Node root2) {
    if(root1 == null && root2 == null)
      return true;
    if(root1 == null || root2 == null)
      return false;
    if(root1.val != root2.val)
      return false;
    return isSame(root1.left, root2.left) && isSame(root1.right, root2.right);
  }
 
  private static boolean isSame2(Node root1, Node root2) {
    if(root1 == null && root2 == null)
      return true;
    if(root1 == null || root2 == null)
      return false;
    if(root1.val != root2.val)
      return false;
   
    Queue<Node> queue1 = new ArrayDeque<>();
    Queue<Node> queue2 = new ArrayDeque<>();
    queue1.offer(root1);
    queue2.offer(root2);
    while(!queue1.isEmpty()) {
      root1 = queue1.poll();
      root2 = queue2.poll();
      if(!check(root1.left, root2.left)) return false;
      if(root1.left != null) {
        queue1.offer(root1.left);
        queue2.offer(root2.left);
      }
      if(!check(root1.right, root2.right)) return false;
      if(root1.right != null) {
        queue1.offer(root1.right);
        queue2.offer(root2.right);
      }
    }
    return true;
  }
 
  private static boolean check(Node root1, Node root2) {
    if(root1 == null && root2 == null)
      return true;
    if(root1 == null || root2 == null)
      return false;
    if(root1.val != root2.val)
      return false;
    return true;
  }
  public static class Node {
    private int val;
    private Node left;
    private Node right;
    public Node(int val) {
      this.val = val;
    }
    public Node(int val, Node left, Node right) {
      this.left = left;
      this.right = right;
      this.val = val;
    }
  }
}

Both recursive and iterative solution has time complexity O(N) and space complexity O(H).