100. Same Tree(leetcode)

Recursion Visualizer

How isSameTree() Works

Step through every recursive call, watch the call stack grow and shrink, and see how return values bubble back up.

isSameTree.cpp

1bool isSameTree(TreeNode* p, TreeNode* q) {2 if (p == nullptr || q == nullptr) {3 return p == q;4 }5 return (p->val == q->val)6 && isSameTree(p->left, q->left)7 && isSameTree(p->right, q->right);8}

The Two Trees Being Compared

Tree P root → p

Tree Q root → q

Step 0 / 0

Call Stack (most recent on top)

in progress…

Press “Next ▶” to begin the recursion…

What's Happening Now

We start by calling isSameTree(p, q) where p and q are the roots of the two trees. Press Next ▶ to step through the recursion.

Key Ideas Behind This Recursion

01

Base case: the null check

If either pointer is nullptr, we stop recursing. The expression p == q returns true only if both are null — one null and one non-null means the trees differ, so it returns false.

02

Short-circuit && (AND)

The three conditions are joined by &&. If the values don't match, we return false immediately — no need to check children. If the left subtree differs, we never even visit the right subtree.

03

Depth-first, left-to-right

The recursion visits nodes in pre-order: check current node's value, then dive into the left child, then the right child. Each call gets its own frame on the call stack until it returns.

04

Return values bubble up

Each recursive call returns true or false to its caller. The parent combines its children's results with &&. The final answer is whatever bubbles all the way back to the first call.