Same Tree

Given two binary trees, return whether or not the two trees are identical. Note: identical meaning they exhibit the same structure and the same values at each node.

Example(s)

Example 1:

Tree 1:      Tree 2:
    2            2
   / \          / \
  1   3        1   3
Output: true

Example 2:

Tree 1:      Tree 2:
    1            1
     \          /
      9        9
       \      /
       18    18
Output: false

Example 3:

Tree 1:      Tree 2:
    2            2
   / \          / \
  3   1        1   3
Output: false

Solution

JavaScript Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * Check if two binary trees are identical
 * @param {TreeNode} p - Root of first tree
 * @param {TreeNode} q - Root of second tree
 * @return {boolean} - True if trees are identical, false otherwise
 */
function isSameTree(p, q) {
  if (!p && !q) return true;
  if (!p || !q) return false;
  if (p.val !== q.val) return false;
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

Python Solution

from typing import Optional

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_same_tree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    """
    Check if two binary trees are identical
    
    Args:
        p: Root of first tree
        q: Root of second tree
        
    Returns:
        bool: True if trees are identical, false otherwise
    """
    if not p and not q:
        return True
    if not p or not q:
        return False
    if p.val != q.val:
        return False
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

Complexity

• Time Complexity: O(min(n, m)) - Where n and m are the number of nodes in each tree
• Space Complexity: O(min(h1, h2)) - Where h1 and h2 are the heights of the trees

Approach

The solution uses a recursive approach:

1. Base cases handle null nodes and mismatched structures
2. Value comparison checks if current nodes have the same value
3. Recursive calls compare left and right subtrees
4. Return true only if all conditions are met

Key Insights

• Recursive comparison efficiently checks both structure and values
• Base cases handle null nodes and mismatched structures
• Edge cases include empty trees, single-node trees, and trees with different values or structures
• Simultaneous traversal ensures both trees are compared in lockstep
• O(min(n, m)) time optimizes by stopping at the smaller tree's size