compareBinaryTree

/**
 * Interview Question:
 * Given the roots of two binary trees, determine whether the two trees are the
 * same.
 *
 * Two binary trees are considered the same when:
 * - They have the same structure
 * - Matching nodes have the same value
 *
 * Example:
 *   Tree A:      1        Tree B:      1
 *              / \                  / \
 *             2   3                2   3
 *   Result: true
 *
 *   Tree A:      1        Tree B:      1
 *              /                    \
 *             2                      2
 *   Result: false
 *
 * Answer:
 * Use recursion. At each pair of nodes:
 * - If both are null, that subtree pair matches
 * - If only one is null, the structures differ
 * - If values differ, the trees differ
 * - Otherwise, recursively compare both left children and both right children
 *
 * Complexity:
 * O(n) time because every matching node pair is visited once.
 * O(h) space for the recursion stack, where h is the tree height.
 *
 * Definition for a binary tree node:
 * function TreeNode(val) {
 *   this.val = val;
 *   this.left = null;
 *   this.right = null;
 * }
 *
 * @param {TreeNode | null} p
 * @param {TreeNode | null} q
 * @return {boolean}
 */
export default function isSameTree(p, q) {
  // Both nodes are missing, so these subtrees match.
  if (p === null && q === null) {
    return true;
  }

  // Only one node is missing, so the tree structures are different.
  if (p === null || q === null) {
    return false;
  }

  // Same structure is not enough; matching nodes must also have equal values.
  if (p.val !== q.val) {
    return false;
  }

  // Both left subtrees and both right subtrees must match.
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}