Solving Same Tree: Comparing Binary Tree Structures

The "Same Tree" problem is about determining whether two binary trees are structurally identical and have the same node values.

Problem Statement

Given the roots of two binary trees p and q, 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

Consider two binary trees:

These two trees are the same.

Solution Approach - Recursive Comparison

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

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

Breaking Down the Solution

• Recursive Strategy: The solution uses recursion to compare corresponding nodes of the two trees.
• Base Cases: Check for null nodes. If both are null, they are the same; if only one is null, they are not the same.
• Value Comparison: Compare the value of the current nodes. If they are different, the trees are not the same.
• Recursive Calls: Recursively compare left and right children of the current nodes.

Conclusion

The Same Tree problem is a fundamental exercise in understanding binary tree structure and recursion, highlighting the importance of simultaneous traversal in tree comparison.