DSA sheet · Trees · BFS pattern (also solved with DFS)

Cousins in Binary Tree

This problem sits in the BFS pattern of the sheet, but the teacher solves it both ways. First with DFS, which she calls the friendlier version for beginners. Then with BFS, which she calls the best approach, because it can stop early, as soon as it reaches the level where x and y live. The problem is a nice "family relations" question: it teaches you to collect two facts about a node (its level and its parent) and then compare them.

Every part 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 · Family words you need first
• Part A · Cousins with DFS
• Part B · Cousins with BFS
• Part C · Revision page

Part 0 · Family words you need first

Think of the tree as a family tree. The root is the oldest person, and every child hangs below its parent.

We will use this tree for most of the page:

        1          level 0
       / \
      2   3        level 1
     /   / \
    4   6   7      level 2
     \
      5            level 3

• 4 and 6: same level (2), parents 2 and 3 are different → cousins.
• 6 and 7: same level, but the same parent (3) → siblings, not cousins.
• 4 and 3: different levels (2 and 1). 3 is the brother of 4's parent, so 3 is 4's uncle → not cousins.

Part A · Cousins with DFS

LeetCode 993

1The question in simple words

You get the root of a binary tree and two numbers x and y. Each is the value of some node in the tree. Return True if those two nodes are cousins, otherwise False.

Cousins need both of these:

• same level, and
• different parents.

      1
     / \
    2   3
   /
  4
(different levels)

      1
     / \
    2   3

(same level,
 same parent 1)

        1
       / \
      2   3
     /   / \
    4   6   7
(same level,
 parents 2 and 3)

2What the constraints tell us

• Number of nodes: 2 to 100 → the tree is never empty. For BFS we won't need a "root is None" check at the start. (For DFS we still need a None check inside the recursion, because that is what stops it at the bottom.)
• n ≤ 100 is tiny. Any approach, DFS or BFS, is fast. TLE (Time Limit Exceeded) only starts at around 10⁸ operations.
• Values are from 1 to 100 → small, a normal int is fine.
• Every value is unique, and x ≠ y, and both are in the tree. Why this matters: once we find a node whose value equals x, it is the x node. There is no second copy somewhere else. So we can stop searching as soon as both are found. If values could repeat, "the node with value 4" wouldn't even be well defined.

3Intuition: what we need to know at the end

Imagine you are a detective with a notebook that has four empty boxes:

Once all four boxes are filled, the answer is just one line:

x level == y level and x parent != y parent → True, else False

So the whole job is: walk the tree and fill these four boxes. In DFS we walk deep first. While walking, every node needs to know two things about itself: what level it is on, and who its parent is.

4Building the logic step by step

What do we check at each node?

Standing at a node, the teacher asks it two questions: "Does your value match x?" and "Does your value match y?"

• If it matches x → fill x level with this node's level, and x parent with this node's parent.
• If it matches y → fill y level and y parent the same way.
• Then go to the left child and the right child and ask them the same questions.

Why the function needs extra parameters

A node only knows its value and its two children. It does not know its own level, and it does not know who its parent is. So the caller has to hand this information down:

• level: the root starts at 0. When we go to a child, we send level + 1.
• parent: the root has no parent, so we send None. When we go to a child, the current node becomes the child's parent, so we send root.
• x and y: passed along unchanged, so every call knows what to look for.

The base case

If the node is None, there is nothing to check and no children to visit → just return. This is what stops the recursion at the bottom of the tree.

Can we stop as soon as we find x?

No. Say we are looking for 4 and 6. We reach 4 first and fill x's boxes. But we have no idea where 6 is. It might be below 4, or somewhere on the right side. So we must keep going.

But once both x and y are found, all four boxes are full and there is nothing left to learn. So the teacher adds one more check: if all the boxes are already filled, return right away.

What if x or y is never found?

Then its level box stays at its starting value (we use −1). The levels won't match, so the answer is False. (The constraints promise both exist, but the code is safe anyway.)

5Approach steps

1. Create four variables: x level, x parent, y level, y parent (levels start at −1, meaning "not found yet").
2. Call dfs(root, level=0, parent=None).
3. In dfs: if the node is None → return. If both x and y are already found → return.
4. If node value == x → save this level and this parent for x.
5. If node value == y → save this level and this parent for y.
6. Call dfs on the left child and on the right child with level + 1 and parent = this node.
7. After dfs finishes: return x level == y level and x parent is not y parent.

6Code (Python)

class Solution:
    def isCousins(self, root, x, y):
        self.x_level = -1        # -1 means "not found yet"
        self.x_parent = None
        self.y_level = -1
        self.y_parent = None
        self.dfs(root, 0, None, x, y)    # root: level 0, no parent
        return self.x_level == self.y_level and self.x_parent is not self.y_parent

    def dfs(self, root, level, parent, x, y):
        if root is None:                              # base case
            return
        if self.x_level != -1 and self.y_level != -1: # both found, stop early
            return
        if root.val == x:
            self.x_level = level
            self.x_parent = parent
        if root.val == y:
            self.y_level = level
            self.y_parent = parent
        self.dfs(root.left, level + 1, root, x, y)    # I am my child's parent
        self.dfs(root.right, level + 1, root, x, y)

7Code line by line

8Dry run using the call stack

Tree from Part 0, with x = 4, y = 6. Each call is written as (node, level, parent). N = None.

        1
       / \
      2   3
     /   / \
    4   6   7
     \
      5

1. Call (1, 0, N): 1 is not 4 and not 6 → go left. (1,0,N) waits on the stack.
2. Call (2, 1, 1): no match → go left.
3. Call (4, 2, 2): 4 == x → x level = 2, x parent = node 2. We can't stop yet, because y hasn't been found.
4. 4's left is None → that call returns at once.
5. 4's right: call (5, 3, 4): no match. Its left and right are None → both return. (5,3,4) is done and leaves the stack.
6. (4,2,2) has finished both sides → leaves the stack. Back in (2,1,1), its right child is None → returns. (2,1,1) leaves the stack.
7. Back in (1,0,N), now go right: call (3, 1, 1): no match → go left.
8. Call (6, 2, 3): 6 == y → y level = 2, y parent = node 3. All four boxes are full now.
9. 6's children are None → return. Back in (3,1,1), go right: call (7, 2, 3) → the "both found" check fires → return without looking at 7.
10. Everything unwinds. Boxes: x (level 2, parent 2), y (level 2, parent 3). Same level ✓, different parents ✓ → True.

Try x = 6, y = 7 yourself: both are level 2 but the parent is 3 for both → False. Try x = 4, y = 3: levels 2 and 1 → False.

9Complexity & remember

• Time O(n): in the worst case we visit every node once.
• Space O(n): the call stack. For a balanced tree it is only about log n deep. For a skewed tree (almost all nodes on one side, like a straight line) the stack holds nearly all n nodes, so the worst case is O(n).

Part B · Cousins with BFS

Same question. Now we go level by level with a queue. The teacher's claim: BFS is the better approach here, because cousins always sit on the same level, and BFS handles one whole level at a time.

1The question in simple words

Same as Part A: return True if x and y are on the same level with different parents.

2What the constraints tell us

• At least 2 nodes → the root is never None, so no base case is needed before starting the queue. The while loop stops by itself when the queue is empty.
• Unique values → when we see x on some level, it's the only x anywhere. This is what lets us say "only one of them is on this level → the other must be on a different level → False".

3Intuition

In level-order BFS, the queue holds one full level at a time. So:

• Level check comes for free. If x and y are both popped during the same round of the inner loop, they are on the same level. We don't need a level variable at all.
• Parent check is done from the parent's side. When we pop a node, we look at its two children before they go into the queue. If its two children are exactly x and y, then x and y are siblings → False immediately.

So we look for the False case (siblings) at the parent, and the True case (both on one level) at the end of each level.

4Building the conditions from examples

Example 1: x = 4, y = 6 → True, found then and there

The levels are [1], then [2, 3], then [4, 6, 7], then [5]. While handling the level [4, 6, 7], we pop 4 (that's x) and 6 (that's y). Both on this level, and nobody earlier said "siblings". So it's True right now. There's no need to go on to 7 or to the next level with 5.

To remember "I saw x on this level" and "I saw y on this level", we keep two flags, found_x and found_y. We reset them to False at the start of each level.

Example 2: x = 2, y = 3 (siblings) → False

When we pop 1, we look at its children: left = 2, right = 3. Both exist, and they are exactly x and y (in either order). So they share the parent 1 → siblings → return False then and there. Why keep looking at other nodes? We already know the answer.

Example 3: x = 4, y = 3 (different levels) → False

On the level [2, 3] we pop 3 (that's y) → found_y = True. But x (4) is not on this level, so found_x stays False. At the end of the level, exactly one flag is True. Values are unique, so the other one must be on some other level → they can't be cousins → return False immediately.

Putting it together: what happens at the end of each level

If the loop ever ends without returning (in theory only, since both values exist), we return False.

5Approach steps

1. Put the root in a queue.
2. While the queue isn't empty: take the level size, and set found_x = found_y = False.
3. Pop each node of this level. If its value is x → found_x = True. If it is y → found_y = True.
4. If it has both children and they are {x, y} in either order → return False (siblings).
5. Push its existing children.
6. After the level: both flags True → return True. Exactly one True → return False.
7. After the loop → return False.

6Code (Python)

from collections import deque

class Solution:
    def isCousins(self, root, x, y):
        queue = deque([root])
        while queue:
            size = len(queue)            # nodes on this level
            found_x = False
            found_y = False
            for _ in range(size):
                node = queue.popleft()
                if node.val == x:
                    found_x = True
                if node.val == y:
                    found_y = True
                # siblings check: both children are x and y
                if node.left and node.right:
                    a = node.left.val
                    b = node.right.val
                    if (a == x and b == y) or (a == y and b == x):
                        return False
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            if found_x and found_y:      # same level, different parents
                return True
            if found_x or found_y:       # only one here, other is elsewhere
                return False
        return False

7Code line by line

8Dry run: watch the queue

Same tree, x = 4, y = 6. Yellow = the nodes of the current level.

Now two more quick runs:

9Complexity, DFS vs BFS & remember

• Time O(n): in the worst case every node enters and leaves the queue once.
• Space O(n): the queue holds at most one level, and the widest level can have about n/2 nodes.

Why the teacher calls BFS better here. On paper, both are O(n) time and O(n) space. But BFS stops at the level where x and y live. Picture a very tall tree where 4 and 6 sit on level 2: BFS answers right after level 2, without touching anything deeper. DFS dives to the bottom of the left side first. So in the best and average cases BFS saves both time and memory. In the worst case they are the same.

Why DFS is still worth knowing. The teacher calls the DFS version more beginner friendly: it just fills four variables and checks one line at the end.

Part C · Revision page

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

root = TreeNode(1,
                TreeNode(2, TreeNode(4, None, TreeNode(5))),
                TreeNode(3, TreeNode(6), TreeNode(7)))
s = Solution()
print(s.isCousins(root, 4, 6))   # True
print(s.isCousins(root, 6, 7))   # False
print(s.isCousins(root, 4, 3))   # False
print(s.isCousins(root, 2, 3))   # False
print(s.isCousins(root, 5, 7))   # False

Based on this video: Cousins in Binary Tree | DFS & BFS