DSA With AI
Week 4 ยท Trees

Same Tree

Decide whether two binary trees are identical in both structure and node values.

Easy Trees Week 4 Practice runner

Frame the problem

  • Two empty trees are the same.
  • One empty and one non-empty tree are different.
  • Values must match at aligned positions.
1. Reveal example inputs and outputs

Example 1

Input:

is_same_tree([
  1,
  [
    2,
    null,
    null
  ],
  [
    3,
    null,
    null
  ]
], [
  1,
  [
    2,
    null,
    null
  ],
  [
    3,
    null,
    null
  ]
])

Output:

true

Example 2

Input:

is_same_tree([
  1,
  [
    2,
    null,
    null
  ],
  null
], [
  1,
  null,
  [
    2,
    null,
    null
  ]
])

Output:

false
2. Brute force first

What three checks must be true at every aligned pair of nodes?

3. Reveal the insight ladder
  1. Handle the empty cases first.
  2. If both nodes exist, compare their values.
  3. Then compare the left subtrees and right subtrees recursively.
  4. All checks must pass for the trees to be the same.
4. Dry run before code
  1. p = [1, 2], q = [1, null, 2].
  2. Roots match at 1.
  3. p.left exists while q.left is empty.
  4. The structural mismatch returns False.
5. Reveal final Python solution 
def is_same_tree(p, q):
    if p is None or q is None:
        return p is q
    p_value, p_left, p_right = p
    q_value, q_left, q_right = q
    return (
        p_value == q_value
        and is_same_tree(p_left, q_left)
        and is_same_tree(p_right, q_right)
    )

Complexity: Time O(n), where n is the smaller point where mismatch may occur or all nodes if equal. Space O(h).

Interview narration

  • This is a lockstep traversal of two trees.
  • I first eliminate the empty-node cases so value access is safe.
  • Then the result is value equality plus recursive equality of both children.

Common traps

  • Comparing only inorder traversals, which can hide structural differences.
  • Treating repeated values as enough to prove equality.
  • Forgetting that two None nodes are equal.

Follow-up drills

1. Can two different trees have the same inorder traversal?

Yes. Without null markers or another traversal, inorder alone does not encode shape.

2. How would you solve it iteratively?

Use a stack of node pairs. Pop pairs, check the same empty/value conditions, and push aligned child pairs.

3. How does this helper support Subtree of Another Tree?

At each candidate root in the large tree, Same Tree verifies whether the entire subtree matches the target subtree.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.