DSA sheet · Trees · DFS & BFS pattern

Same Tree & Symmetric Tree

These two problems are taught together because they use the same idea. If you understand Same Tree properly, Symmetric Tree needs only one small change. The teacher solves both twice: first with DFS (recursion), then with BFS (a queue), so we learn to think in both styles.

Every problem below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Same Tree with DFS
• Part B · Symmetric Tree with DFS
• Part C · Same Tree with BFS
• Part D · Symmetric Tree with BFS
• Part E · Revision page

Part 0 · Before starting

What is a tree node?

Each node is a small box with 3 things: its value, a link to its left child and a link to its right child. If a child is missing, the link is None (nothing there).

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val       # the number in this node
        self.left = left     # left child, or None
        self.right = right   # right child, or None

Two ways to visit every node

Why read constraints first? (the teacher always does this)

Constraints are not decoration. They answer 3 questions before you write any code:

1. Do I need a base case? If the number of nodes can be 0, the root itself can be None, so the code must handle that.
2. int or long? Are the values small enough for a normal integer? (In Python ints never overflow, but in Java/C++ this matters.)
3. Will my code be fast enough (no TLE)? Roughly, more than about 10⁸ operations gives TLE (Time Limit Exceeded). If n is tiny, even O(n²) or O(n³) is fine.

Part A · Same Tree with DFS

LeetCode 100

1The question in simple words

You are given the roots of two binary trees, p and q. Tell whether they are the same tree.

Two trees are "the same" only when both of these are true:

• Same structure (shape): wherever tree 1 has a left child, tree 2 also has a left child in that position. Wherever tree 1 has a right child, tree 2 also has one. No extra or missing nodes.
• Same values: when both trees have a node in the same position, the two numbers are equal.

2What the constraints tell us

• Number of nodes: 0 to 100 → 0 is allowed, so a tree can be completely empty. We must write a base case for None.
• Values: −10⁴ to 10⁴ → small numbers, a normal int is fine.
• n ≤ 100 is very small → O(n), O(n²), even O(n³) would pass. So we don't need any clever optimisation. Just write clean, correct code.

3Intuition: how to think about it

Imagine you put one finger on each tree, both at the root. You move the two fingers together, always to the same position: if one goes left, the other also goes left.

At every position you ask a few questions: "Is there a node under both fingers? Are their values equal?"

• If any question fails at any position → the trees are not same, answer False.
• If every position passes → the trees are same, answer True.

Moving the fingers "go left fully, come back, then go right" is exactly DFS. In code, the "two fingers" are the two parameters of our function: p (finger on tree 1) and q (finger on tree 2).

4Building the conditions from examples

The teacher doesn't give the rules directly. She walks through 3 examples and discovers one rule from each. Let's do the same.

  tree p        tree q
     1             1
    / \           / \
   2   3         2   3
  / \           / \
 4   5         4   5

  tree p        tree q
     1             1
    / \           / \
   2   3         2   4
  / \           / \
 4   5         4   5

  tree p        tree q
     1             1
    / \           /
   2   5         2     ← missing
  /             /
 4             4

From Example 1 → Rule: both are None → True

Walk the fingers: root 1 and 1 → exist, equal ✓. Left 2 and 2 ✓. Left 4 and 4 ✓. Right 5 and 5 ✓. Right side 3 and 3 ✓. So they are the same tree.

Now look at node 3. It has no left child in either tree. When the fingers go to 3's left, both land on None. Nothing is there and nothing is missing, so this position agrees. There is nothing more to check below it, because there is no node.

From Example 2 → Rule: both exist but values differ → False

Everything matches until the right side of the root: tree p has 3, tree q has 4. Both nodes exist, but the values are not equal. One mismatch is enough to say "not same".

From Example 3 → Rule: only one of them is None → False

At the right side of the root, tree p has node 5, but tree q has nothing. One finger is on a node, the other is on None. The shapes are different, so the answer is False. It can also be the other way round (p is None, q has a node). Both cases are False.

The last situation → both exist and values are equal → check the children

If all 3 rules passed, this position is fine. That doesn't mean the whole tree is same yet. We still have to check what's below. This is where DFS comes in: we call the same function again for the children.

• Compare left with left: call with (p.left, q.left)
• Compare right with right: call with (p.right, q.right)

What do we return after the two calls? AND, not OR

Each call gives back True or False. Should the tree be "same" if either side is same, or only if both sides are same?

Think of Example 2: the left side (2-4-5) is same → True, the right side (3 vs 4) → False. The trees are clearly not same. So we need both to be True → use and.

5Approach steps (the algorithm in plain English)

1. Take two nodes p and q (same position in the two trees).
2. If both are None → return True.
3. If only one is None → return False.
4. If the values differ → return False.
5. Otherwise check left children together and right children together (recursively).
6. Return True only if both the left check and the right check are True.

6Code (Python)

class Solution:
    def isSameTree(self, p, q):
        if p is None and q is None:      # Rule 1
            return True
        if p is None or q is None:       # Rule 2
            return False
        if p.val != q.val:               # Rule 3
            return False
        left = self.isSameTree(p.left, q.left)       # left with left
        right = self.isSameTree(p.right, q.right)    # right with right
        return left and right

Shorter way, same meaning: replace the last 3 lines with return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right). A bonus of the one-line version: if the left side is already False, Python doesn't even run the right call.

7Code line by line

8Dry run using the call stack

The teacher's dry run uses Example 1, but with q's right node changed from 3 to 4 (that's Example 2). "N" = None. Read it top to bottom like a story:

1. Call (1, 1): both exist, 1 = 1 ✓ → go left first. (1,1) waits on the stack.
2. Call (2, 2): ✓ → go left. (2,2) waits.
3. Call (4, 4): ✓ → go left.
4. Call (N, N), the left children of 4: both None → True. This call is finished and removed from the stack.
5. Back in (4,4), go right: call (N, N) → True.
6. (4,4) now has left = True, right = True → returns True to (2,2) and leaves the stack.
7. (2,2) goes right: call (5, 5) ✓ → its two children are (N,N) and (N,N) → True, True → (5,5) returns True.
8. (2,2) has left = True, right = True → returns True to (1,1).
9. (1,1) goes right: call (3, 4): both exist, but 3 ≠ 4 → False (Rule 3).
10. (1,1) has left = True, right = False → True and False = False. The stack is now empty. Final answer: False ✓

The newest call is on top (red). A call leaves the stack as soon as it returns its answer to the call below it.

9Complexity & remember

• Time O(n): we visit each node once.
• Space O(n): the calls waiting on the stack. (More precisely, the stack is as tall as the tree: about log n for a balanced tree, n in the worst case, a tree shaped like a straight line.)

Part B · Symmetric Tree with DFS

LeetCode 101

1The question in simple words

Now you get only one tree. Check whether it is symmetric, meaning a mirror image of itself. Imagine folding the paper along a vertical line through the root: the left half should land exactly on the right half.

        1
      /   \
     2     2
    / \   / \
   3   4 4   3

        1
      /   \
     2     2
      \     \
       3     3

In a mirror, the left side of one half must match the right side of the other half. In the first tree: the left 2's left child (3) matches the right 2's right child (3). The left 2's right child (4) matches the right 2's left child (4).

2What the constraints tell us

• Number of nodes: at least 1 (1 to 1000) → the root always exists. We don't need the "empty tree" check at the top.
• But careful: in DFS we still need the None checks inside the recursion. The teacher's point: in DFS, the base case is the only thing that stops the recursion. Without it, the function would keep going into None children and crash. In BFS, the loop stops by itself when the queue is empty, so there the top-level check really can be skipped.

3Intuition: why this is almost the same as Same Tree

Cut the tree at the root. You now have two smaller trees: the left subtree and the right subtree. The question becomes: are these two trees mirror images of each other?

That is just like Same Tree, comparing two trees with two fingers. The only difference is the direction the fingers move:

4The conditions (same rules, new examples)

The teacher checks that every rule from Same Tree still holds here:

• Both None → True. e.g. a leaf 3 on the left and its mirror leaf 3 on the right: their children are all None on both sides → fine.
• Only one None → False. e.g. the left 2 has a left child, but the right 2 has no right child (its mirror spot) → not a mirror.
• Both exist, values differ → False. e.g. 5 on one side, 4 at the mirror spot.
• Both exist, values equal → go to the children, but mirrored: (p.left, q.right) and (p.right, q.left). Return and of both.

All the rules are copied. Only the two recursive calls change. That's why the teacher says "only these two parts of the code need to change, we just swap them".

5How do we start with only one tree?

Our helper function needs two nodes, but we have one root. The teacher's trick: write a helper isMirror(p, q) and call it with the same root twice: isMirror(root, root).

• First call: p = root, q = root, the same node, so the values are obviously equal ✓.
• Next, it compares p.left with q.right, which means root.left vs root.right. That's the real comparison we wanted. From here on, p and q are different nodes.

6Approach steps

1. Call isMirror(root, root).
2. Inside: both None → True; one None → False; values differ → False.
3. Otherwise return isMirror(p.left, q.right) and isMirror(p.right, q.left).

7Code (Python)

class Solution:
    def isSymmetric(self, root):
        if root is None:                 # safe guard (constraints say root exists)
            return True
        return self.isMirror(root, root)

    def isMirror(self, p, q):
        if p is None and q is None:      # Rule 1 (same as Same Tree)
            return True
        if p is None or q is None:       # Rule 2
            return False
        if p.val != q.val:               # Rule 3
            return False
        # ONLY CHANGE: mirror -> left with right, right with left
        return self.isMirror(p.left, q.right) and self.isMirror(p.right, q.left)

8Dry run

        1
      /   \
    2a     2b          (2a = left 2, 2b = right 2)
   /  \      \
  3    4      3        ← 2b has NO left child

1. isMirror(1, 1): same node, equal ✓ → first check (1.left, 1.right) = (2a, 2b).
2. (2a, 2b): both exist, 2 = 2 ✓ → outer pair first: (2a.left, 2b.right) = (3, 3).
3. (3, 3): ✓ → its pairs (N, N) and (N, N) → True, True → returns True.
4. Back in (2a, 2b): inner pair (2a.right, 2b.left) = (4, N) → only one is None → False.
5. (2a, 2b) = True and False = False.
6. Back in (1,1): the first part is already False, so and stops right there. Final answer: False ✓ The 4 has no mirror partner.

9Complexity & remember

• Time O(n). The teacher explains it as n/2: each call handles two nodes at once (one from each half), so there are about half as many calls as nodes. n/2 is still linear, so in an interview just say O(n).
• Space O(n) for the call stack.

Part C · Same Tree with BFS

Same question as Part A (two trees, are they same?), but now we check level by level using a queue instead of recursion. The rules don't change. Only the way we move through the tree changes.

1Recall normal BFS (level order)

from collections import deque
queue = deque([root])          # 1. put the root in the queue
while queue:                   # 2. until the queue is empty
    node = queue.popleft()     # 3. take ONE node from the front
    # ... do something with node (print / add) ...
    if node.left:  queue.append(node.left)    # 4. add children
    if node.right: queue.append(node.right)

2Intuition: what changes when we have two trees?

• We have two roots → put both in the queue at the start: p, then q.
• In normal BFS we pop one node because we only print it. Here we want to compare, and comparing needs two nodes → pop two at a time. The first popped node is from tree 1, the second is the node from tree 2 in the same position.
• Check them with the same rules.
• If they match, add their children to the queue in pairs, so that later, when we pop two, we again get a matching pair.

3The conditions, and the 3 important points she explains

Point 1: push None children too (don't skip them)

In normal BFS we only push a child if it exists. Here we push it even if it's None. Why?

Suppose tree 1 has a left child and tree 2 doesn't. If we skip the None, we push only tree 1's child. Later we pop two, but the second one isn't its partner (or the queue is empty, and the pop crashes). The pairs get mixed up.

If we push the None, the pair stays together as (node, None), and Rule 2 catches it → False ✓.

Point 2: both None → continue, NOT return True

This is the most important difference from DFS.

• In DFS, return True only ends that one small call. It goes back to its parent call, which then continues checking the other side. Nothing is skipped.
• In BFS there are no small calls. We are inside one while loop in the main function. return True would end the whole function and say "same tree!" while other pairs are still waiting in the queue, unchecked.

So when both are None, this pair is fine. We just skip it and move to the next pair → continue.

Point 3: one None, or values differ → return False immediately

Here returning right away is correct. One mismatch anywhere means the trees aren't same, so there's no need to check the rest.

Bonus points

• Order of pushing matters: since we pop two at a time, whatever we push next to each other gets compared. So push n1.left, n2.left, then n1.right, n2.right.
• Why return True after the loop? We only reach the end of the loop if no pair ever returned False. Every pair was checked and passed. And because we always push in pairs and pop in pairs, the queue will become empty.
• Why no separate base case for 0 nodes? If both trees are empty, the queue starts as [None, None]. We pop them, both are None → continue, the queue is empty → return True. Pushing None already handles it.

4Approach steps

1. Make a queue and push p and q.
2. While the queue is not empty: pop two nodes n1, n2.
3. Both None → continue.
4. One None → return False.
5. Values differ → return False.
6. Push n1.left, n2.left, n1.right, n2.right (None included).
7. After the loop → return True.

5Code (Python)

from collections import deque

class Solution:
    def isSameTree(self, p, q):
        queue = deque()
        queue.append(p)
        queue.append(q)

        while queue:
            n1 = queue.popleft()
            n2 = queue.popleft()

            if n1 is None and n2 is None:
                continue
            if n1 is None or n2 is None:
                return False
            if n1.val != n2.val:
                return False

            queue.append(n1.left)
            queue.append(n2.left)
            queue.append(n1.right)
            queue.append(n2.right)

        return True

6Code line by line

7Dry run: watch the queue

Using Example 1 (both trees: 1 → 2, 3 → 2 has 4, 5). Yellow = the two we pop at this step. N = None.

Notice the order we checked: 1 → 2 → 3 → 4 → 5. Level 0, then level 1, then level 2. That's BFS.

Why continue matters: the wrong version on a tricky example

  tree p        tree q
     1             1
    / \           / \
   2   3         2   3
      /             /
     5             6

8Complexity & DFS vs BFS

• Time O(n): every node goes into the queue once and comes out once.
• Space O(n): the queue (plus the extra None entries).

Which is better, DFS or BFS? For this problem, both are O(n) time and O(n) space, so neither wins on paper. The teacher's advice: for some problems DFS is easier, for others BFS is. So for every tree problem, practise thinking of both, then pick the one that's easier or faster.

Part D · Symmetric Tree with BFS

1Intuition: what changes from Part C?

Take the BFS Same Tree code and change just 2 things:

1. Starting pair: there's only one tree now, so push root, root (the same trick as in DFS). Or push root.left, root.right directly. The teacher shows that both work.
2. Mirror pairing when pushing children: push n1.left next to n2.right, and n1.right next to n2.left. Because we pop two at a time, the mirror partners come out together.

Everything else is identical: pop two, continue on both None, False on one None or different values, True at the end.

The constraints say at least 1 node, so the root exists and we don't need an empty check here.

2Code (Python)

from collections import deque

class Solution:
    def isSymmetric(self, root):
        queue = deque()
        queue.append(root.left)        # the left half...
        queue.append(root.right)       # ...vs the right half

        while queue:
            n1 = queue.popleft()
            n2 = queue.popleft()

            if n1 is None and n2 is None:
                continue
            if n1 is None or n2 is None:
                return False
            if n1.val != n2.val:
                return False

            queue.append(n1.left)      # outer pair
            queue.append(n2.right)
            queue.append(n1.right)     # inner pair
            queue.append(n2.left)

        return True

3Dry run

        1
      /   \
    2a     2b
   / \     / \
  3   4   4   3

If the bottom row were 3 4 3 4 instead, step 1 would push (3, 4, 4, 3). Step 2 would pop 3 and 4 → different → return False.

4Complexity & why BFS ran slower

O(n) time, O(n) space, the same as DFS. But on LeetCode the BFS version ran a bit slower. The teacher's reason: BFS does many enqueue and dequeue operations, including all the None entries. DFS only keeps one chain of calls on the stack at a time.

Part E · Revision page

t1 = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
t2 = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
t3 = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(4))
sym = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(2, TreeNode(4), TreeNode(3)))
not_sym = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(2, None, TreeNode(3)))

s = Solution()
print(s.isSameTree(t1, t2))     # True
print(s.isSameTree(t1, t3))     # False
print(s.isSymmetric(sym))       # True
print(s.isSymmetric(not_sym))   # False

Based on these videos: Same Tree & Symmetric Tree | DFS · Same Tree & Symmetric Tree Using BFS