#872 - Leaf-Similar Trees

EasyBinary Tree - DFS

Two binary trees are leaf-similar if their leaf value sequences (left to right) are identical. Given the roots of two binary trees, return true if they are leaf-similar.

Input	Output
root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]	true
root1 = [1,2,3], root2 = [1,3,2]	false

Solution Space

Try it

/**
 * Returns true if both trees have the same leaf sequence (left to right).
 *
 * @param root1 Root of the first binary tree
 * @param root2 Root of the second binary tree
 */
export function leafSimilar(
  root1: TreeNode | null,
  root2: TreeNode | null,
): boolean {
  const leaves1: number[] = [];
  const leaves2: number[] = [];
  collectLeaves(root1, leaves1);
  collectLeaves(root2, leaves2);

  if (leaves1.length !== leaves2.length) return false;
  return leaves1.every((v, i) => v === leaves2[i]);
}

function collectLeaves(node: TreeNode | null, leaves: number[]): void {
  if (!node) return;
  if (!node.left && !node.right) {
    leaves.push(node.val);
    return;
  }
  collectLeaves(node.left, leaves);
  collectLeaves(node.right, leaves);
}

Approach: DFS leaf collection – collect leaves from each tree into an array, then compare.

Time: O(n + m) – visits every node in both trees.

Space: O(n + m) – leaf arrays plus call stack.

#437 Path Sum III

#1372 Longest ZigZag Path in a Binary Tree