loading

Same Tree — Step-by-Step Visualization

easyLeetCode #100TreeDepth-First SearchBinary Tree

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.

Algorithm Pattern

Recursive Comparison

Key Idea

To compare two trees, we can use a recursive Depth-First Search (DFS). At each step, we check: (1) if both nodes are null (same), (2) if only one is null (different), or (3) if their values are different. If all these checks pass, we recursivly compare their left and right children.

Step-by-Step Approach

  1. Base Case 1: If both `p` and `q` are null, they are the same. Return `true`.
  2. Base Case 2: If one is null and the other isn't, they are different. Return `false`.
  3. Value Check: If `p.val` is not equal to `q.val`, return `false`.
  4. Recursive Step: Return `isSameTree(p.left, q.left) && isSameTree(p.right, q.right)`.

Common Gotchas

  • Make sure to handle the null checks before accessing `node.val`.
  • The trees must be structurally identical, not just have the same values in any order.

Related Problems

← All problems