Marauder Bot

Problem

You are given the roots of two binary trees and must decide whether they are identical: the same shape at every position, with the same value stored at each corresponding node.

Example. Trees rooted at 1 with left child 2 and right child 3, in both cases, are the same tree. A root 1 with only a left child 2 is not the same as a root 1 with only a right child 2, even with identical values, because the shape differs.

Key idea

Flattening each tree into a list of values, such as an inorder traversal, and comparing the lists is tempting but does not work: different shapes can produce identical traversal sequences, so a list comparison alone can miss a structural mismatch.

Instead, walk both trees together, node by node, comparing as you go. If both current nodes are null, that branch matches. If exactly one is null, or the values differ, the trees diverge and the answer is immediately false. Otherwise the pair matches, and the trees are the same overall only if the left children also match and the right children also match. This paired recursion never separates structure from values, so shape and content are checked simultaneously. The same comparison also runs iteratively, pushing corresponding node pairs onto a stack and popping them together.

Solution

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

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  if (p === null && q === null) {
    // both sides ended together, so this branch matches
    return true;
  }

  if (p === null || q === null || p.val !== q.val) {
    // one side ended early, or the values differ: shapes diverge here
    return false;
  }

  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

Complexity

Time: O(min(m, n)). The traversal stops at the first mismatch, and otherwise visits each node of the smaller tree once, since a size or shape difference is itself a mismatch.
Space: O(h). The recursion stack depth matches the shorter tree's height, or O(n) for an explicit queue iteratively.

Watch out for

Check for one-null-one-not before comparing values: reading a null node's value crashes rather than reporting a mismatch.
Two trees with the same values arranged differently are not the same tree; only a synchronized, position-aware comparison catches this.
Short-circuit as soon as any pair disagrees rather than traversing both trees fully.

Pattern

This is the template for any structural-equality check: recurse on corresponding parts of two structures at once rather than reducing either one to a flat summary first. The same synchronized-traversal idea extends directly to checking whether one tree is a subtree of another.

Same Tree