Cousins in Binary Tree

▶

Steps

setup

Initialize queue with root node

The algorithm starts by checking if the root is null. Since it is not, it initializes a queue with the root node (value 1) to begin BFS traversal.

💡 Initializing the queue with the root node sets up the BFS traversal starting point.

Line:

queue = deque([root])

💡 The queue will hold nodes level by level, enabling level order traversal.

fill_row

Start processing level 0 (root level)

The algorithm records the size of the queue (1) indicating one node at this level. It resets x_parent and y_parent to None before processing nodes at this level.

💡 Resetting parent trackers at each level ensures we only consider parents of x and y found at the current depth.

Line:

size = len(queue)
x_parent = y_parent = None

💡 Tracking parents per level is crucial to determine if x and y are cousins at the same depth.

fill_cells

Dequeue node 1 for processing

Node 1 is dequeued from the queue to process its children.

💡 Dequeuing the current node allows the algorithm to explore its children for the next level.

Line:

node = queue.popleft()

💡 Processing nodes level by level requires dequeuing nodes one by one.

fill_cells

Process node 1's left child (node 2)

Node 1's left child (node 2) is added to the queue. Since node 2's value is neither x=4 nor y=3, no parent is recorded.

💡 Adding children to the queue prepares the next level for processing.

Line:

if node.left:
    queue.append(node.left)
    if node.left.val == x:
        x_parent = node
    if node.left.val == y:
        y_parent = node

💡 Only when a child matches x or y do we record the parent; otherwise, we just enqueue for future processing.

fill_cells

Process node 1's right child (node 3)

Node 1's right child (node 3) is added to the queue. Node 3's value matches y=3, so y_parent is set to node 1.

💡 Recording y_parent here is critical to later check if x and y share the same parent.

Line:

if node.right:
    queue.append(node.right)
    if node.right.val == x:
        x_parent = node
    if node.right.val == y:
        y_parent = node

💡 Finding y at this level means we must check if x is also found at the same level to determine cousin status.

compare

Check if both x and y found at level 0

After processing all nodes at level 0, the algorithm checks if both x_parent and y_parent are set. Only y_parent is set, so it returns false immediately.

💡 If only one of x or y is found at a level, they cannot be cousins, so the algorithm stops early.

Line:

if x_parent and y_parent:
    return x_parent != y_parent
if x_parent or y_parent:
    return False

💡 Cousins must be found at the same level; finding only one means they are not cousins.

prune

Early return: nodes are not cousins

The algorithm returns false because x and y were not found at the same level with different parents.

💡 This early return optimizes the algorithm by avoiding unnecessary traversal.

Line:

return False

💡 The BFS level order traversal ensures correctness by checking level by level.

reconstruct

Final state with answer

The algorithm has concluded that nodes 4 and 3 are not cousins and returns false as the final answer.

💡 The final state confirms the answer after BFS traversal and level checks.

💡 The BFS approach efficiently determines cousin relationships by level and parent comparison.

summary

Summary of BFS traversal and cousin check

The BFS traversal processed the root level, found y but not x, and concluded nodes 4 and 3 are not cousins.

💡 Summarizing the traversal helps consolidate understanding of the BFS approach and cousin criteria.

💡 Cousins must be at the same depth with different parents; this example shows the algorithm correctly identifies when this is not true.

end

End of visualization

The visualization ends with the final answer and the tree fully processed.

💡 Ending the visualization confirms the algorithm's completion and final result.

💡 The BFS approach is complete and the answer is final.

from typing import Optional
from collections import deque

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

def isCousins(root: Optional[TreeNode], x: int, y: int) -> bool:
    if not root:
        return False  # STEP 1
    queue = deque([root])  # STEP 1
    while queue:  # STEP 2
        size = len(queue)  # STEP 2
        x_parent = y_parent = None  # STEP 2
        for _ in range(size):  # STEP 3
            node = queue.popleft()  # STEP 3
            if node.left:  # STEP 3
                queue.append(node.left)  # STEP 3
                if node.left.val == x:  # STEP 3
                    x_parent = node  # STEP 3
                if node.left.val == y:  # STEP 3
                    y_parent = node  # STEP 3
            if node.right:  # STEP 4
                queue.append(node.right)  # STEP 4
                if node.right.val == x:  # STEP 4
                    x_parent = node  # STEP 4
                if node.right.val == y:  # STEP 4
                    y_parent = node  # STEP 4
        if x_parent and y_parent:  # STEP 5
            return x_parent != y_parent  # STEP 5
        if x_parent or y_parent:  # STEP 5
            return False  # STEP 5
    return False  # STEP 6

📊

Cousins in Binary Tree - Watch the Algorithm Execute, Step by Step

Watching the BFS traversal step-by-step reveals how the algorithm checks nodes at the same depth and compares their parents, which is the key to understanding cousin relationships in trees.

Current node: 1

1234

DFS Stack

1 (entered)queue=[1]

Current node: 1

1234

DFS Stack

1 (entered)size=1 x_parent=null y_parent=null

Current node: 1

1234

DFS Stack

1 (left_pending)size=1 x_parent=null y_parent=null

Current node: 2

1234

DFS Stack

1 (right_pending)size=1 x_parent=null y_parent=null

Current node: 3

1234

DFS Stack

1 (level_done)size=1 x_parent=null y_parent=1

1234

Return: false

1234

Return: false

1234

Return: false

1234

Return: false

1234

Return: false

Key Takeaways

✓ BFS level order traversal is essential to check nodes at the same depth simultaneously.

Reading code alone can obscure how level boundaries are maintained; visualization clarifies this.

✓ Tracking parents of x and y at each level allows immediate decision making about cousin status.

It is easy to miss that parents must be different and nodes must be at the same level for cousins.

✓ Early return when only one of x or y is found at a level optimizes the algorithm.

Understanding this pruning step is easier when seeing the traversal stop early in the visualization.

Practice

1. You need to find the maximum value at each depth level of a binary tree. Which approach guarantees an efficient and correct solution for this problem?

easy

A. Perform a breadth-first search (BFS) level order traversal, tracking the maximum value per level.

B. Use a greedy traversal that picks the largest child node at each step without level tracking.

C. Apply a dynamic programming approach that stores maximum values for subtrees without level information.

D. Use a depth-first search (DFS) without tracking levels, updating a global maximum value.

Solution

1. Step 1: Understand the problem requires per-level maximums

   The problem asks for the largest value at each tree row (level), so we must process nodes grouped by their depth.

2. Step 2: Identify BFS level order traversal as the correct pattern

   BFS naturally processes nodes level by level, allowing us to track and update the maximum value for each level efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BFS processes nodes level-wise, perfect for per-level max tracking [OK]

Hint: Level order traversal matches per-level processing [OK]

Common Mistakes:

• Using DFS without level tracking loses level grouping
• Greedy picks largest child but misses other nodes at same level
• DP without level info cannot isolate per-level max

2. Consider the following Python code for N-ary tree level order traversal. Given the tree root = Node(1, [Node(3, [Node(5), Node(6)]), Node(2), Node(4)]), what is the value of res after the first iteration of the outer while loop completes?

easy

A. [[1]]

B. [[1, 3, 2, 4]]

C. [[3, 2, 4]]

D. [[5, 6]]

Solution

1. Step 1: Trace the first outer loop iteration

   Initially, current_level contains only the root node with value 1.

2. Step 2: Collect values and enqueue children

   We pop node 1, append its value to level_nodes -> [1], and enqueue its children (3, 2, 4) into next_level.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   After first iteration, res = [[1]] as only root level processed [OK]

Hint: First level contains only root node value [OK]

Common Mistakes:

• Confusing first level with all children nodes

3. Identify the bug in the following code snippet for the right side view of a binary tree:

def rightSideView(root: Optional[TreeNode]) -> List[int]:
    rightside = []
    def dfs(node, depth):
        if not node:
            return
        if depth == len(rightside):
            rightside.append(node.val)
        dfs(node.left, depth + 1)  # Line X
        dfs(node.right, depth + 1) # Line Y
    dfs(root, 0)
    return rightside

Which line contains the bug causing incorrect right side view?

medium

A. Line with 'if depth == len(rightside): rightside.append(node.val)'

B. Line X: 'dfs(node.left, depth + 1)'

C. Line Y: 'dfs(node.right, depth + 1)'

D. Line with 'if not node: return'

Solution

1. Step 1: Understand traversal order

   The code visits left child before right child, so left nodes are appended first at each depth.

2. Step 2: Why this causes bug

   Visiting left first causes left nodes to be recorded as visible, overwriting right nodes that should be visible from the right side.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Swapping left and right child calls fixes the bug [OK]

Hint: Right-first DFS needed to capture rightmost nodes [OK]

Common Mistakes:

• Visiting left child before right in DFS causes wrong nodes appended
• Appending nodes without checking depth length
• Not handling null nodes properly

4. Suppose the binary tree nodes can be dynamically added or removed during traversal, or the tree is extremely deep (height > 10^5). Which modification to the level order traversal algorithm is most appropriate to handle these constraints efficiently?

hard

A. Use the recursive DFS with level tracking approach as is, since it handles all cases optimally.

B. Switch to an iterative BFS approach using a queue to avoid recursion stack overflow and handle dynamic changes.

C. Use a naive recursive approach without level tracking and sort nodes by level after traversal.

D. Use a depth-limited DFS that stops at a fixed depth to avoid deep recursion.

Solution

1. Step 1: Identify issues with recursive DFS on very deep trees

   Recursive DFS risks stack overflow on very deep trees and does not handle dynamic changes well.

2. Step 2: Evaluate iterative BFS suitability

   Iterative BFS with a queue avoids recursion stack issues and can handle dynamic node additions/removals during traversal.

3. Step 3: Discard naive and depth-limited approaches

   Naive recursion and sorting is inefficient; depth-limited DFS misses nodes beyond limit.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Iterative BFS is robust for deep or dynamic trees [OK]

Hint: Iterative BFS avoids recursion limits and handles dynamic trees [OK]

Common Mistakes:

• Assuming recursion always works
• Ignoring stack overflow risk
• Using depth limits that lose nodes

5. Suppose the binary tree can have nodes with duplicate values and you want to return the right side view but also include all nodes visible from the right side at each depth (not just the first). Which modification to the optimal DFS approach correctly handles this variant?

hard

A. Use DFS with right-first traversal but overwrite the node value at each depth to keep the last visited node.

B. Use BFS level order traversal and collect the last node at each level only.

C. Change DFS to visit left child first and append all nodes at each depth to a list.

D. Modify DFS to visit right child first and append every node encountered at each depth to a list instead of only the first.

Solution

1. Step 1: Understand requirement

   We want all nodes visible from the right side at each depth, not just the first.

2. Step 2: Modify DFS to collect all nodes per depth

   Visiting right child first ensures rightmost nodes are visited first, but we must append every node at that depth to a list, not just the first.

3. Step 3: Why other options fail

   Left-first traversal or overwriting values loses rightmost visibility; BFS collecting only last node misses duplicates.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Right-first DFS appending all nodes per depth captures all visible nodes [OK]

Hint: Right-first DFS appending all nodes per depth [OK]

Common Mistakes:

• Using left-first traversal loses rightmost nodes
• Appending only first or last node per depth misses duplicates
• Overwriting values loses multiple visible nodes