100. Same Tree

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.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

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

Output: true

Example 2

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

Output: false

Example 3

Input: [1, 2, 1], [1, 1, 2]

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), where N is a number of nodes in the tree, since one 
 *    visits each node exactly once.
 * Space complexity : O(log(N)) in the best case of completely balanced tree 
 *    and O(N) in the worst case of completely unbalanced tree, to keep a 
 *    recursion stack.
 */

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) {
            return true;
        }
        if(p == null || q == null || p.val != q.val) {
            return false;
        }
        
        return isSameTree(p.left, q.left) && 
                    isSameTree(p.right, q.right);
    }
}

Solution 2

/**
 * Time complexity : O(N) since each node is visited exactly once.
 * Space complexity : O(log(N)) in the best case of completely balanced tree 
 *    and O(N) in the worst case of completely unbalanced tree, to keep a deque.
 */

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        if(p == null || q == null) return false;
        
        Queue<TreeNode> pQueue = new LinkedList<TreeNode>();
        Queue<TreeNode> qQueue = new LinkedList<TreeNode>();
        
        pQueue.add(p);
        qQueue.add(q);
        
        while(!pQueue.isEmpty() && !qQueue.isEmpty()) {
            TreeNode pTreeNode = pQueue.remove();
            TreeNode qTreeNode = qQueue.remove();
            
            if(pTreeNode.val != qTreeNode.val) return false;
            
            if(pTreeNode.left != null && qTreeNode.left != null) {
                pQueue.add(pTreeNode.left);
                qQueue.add(qTreeNode.left);
            } else if(pTreeNode.left != null || qTreeNode.left != null) {
                return false;
            }
            
            if(pTreeNode.right != null && qTreeNode.right != null) {
                pQueue.add(pTreeNode.right);
                qQueue.add(qTreeNode.right);
            } else if(pTreeNode.right != null || qTreeNode.right != null) {
                return false;
            }
        }
        return true;
    }
}

Solution 3

/**
 * Time complexity : O(N) since each node is visited exactly once.
 * Space complexity : O(log(N)) in the best case of completely balanced tree 
 *    and O(N) in the worst case of completely unbalanced tree, to keep a deque.
 */

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) {
            return true;
        }
        if(p == null || q == null) {
            return false;
        }
        
        Queue<TreeNode> queue = new LinkedList();
        queue.add(p);
        queue.add(q);
        
        while(!queue.isEmpty()) {
            TreeNode n1 = queue.remove();
            TreeNode n2 = queue.remove();
            if(n1.val != n2.val) {
                return false;
            }
            if(n1.left != null && n2.left != null) {
                queue.add(n1.left);
                queue.add(n2.left);
            } else if(n1.left != null || n2.left != null) {
                return false;
            }
            if(n1.right != null && n2.right != null) {
                queue.add(n1.right);
                queue.add(n2.right);
            } else if(n1.right != null || n2.right != null) {
                return false;
            }
        }
        return true;
    }
}

Follow up