Cousins in Binary Tree

📋

Problem

Imagine a family reunion where you want to find out if two people are cousins - they share the same generation but have different parents.

Given the root of a binary tree and two integers x and y representing the values of two different nodes in the tree, determine if the nodes corresponding to x and y are cousins. Two nodes are cousins if they are at the same depth but have different parents. Return true if they are cousins, otherwise false.

The number of nodes in the tree is in the range [2, 100].1 ≤ Node.val ≤ 100x != yx and y exist in the tree

Edge cases: x and y are siblings → expected output: falsex or y is the root node → expected output: falsex and y are at different depths → expected output: false

</>

IDE

def isCousins(root: Optional[TreeNode], x: int, y: int) -> bool:public boolean isCousins(TreeNode root, int x, int y)bool isCousins(TreeNode* root, int x, int y)function isCousins(root, x, y)

def isCousins(root, x, y):
    # Write your solution here
    pass

class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool isCousins(TreeNode* root, int x, int y) {
    // Write your solution here
    return false;
}

function isCousins(root, x, y) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: trueReturning true when nodes are siblings (same parent).✅ Add explicit check: if x_parent == y_parent, return false.

Wrong: trueReturning true when nodes are at different depths.✅ Add depth equality check before comparing parents: if x_depth != y_depth, return false.

Wrong: falseReturning false when nodes are cousins due to incomplete BFS or DFS traversal.✅ Ensure BFS or DFS visits all nodes and correctly tracks depth and parent for both x and y.

Wrong: trueNot handling root node case properly, returning true if root is one of the nodes.✅ Check if either x or y is root (depth 0), return false immediately.

Wrong: timeoutUsing exponential or repeated traversals causing TLE on large inputs.✅ Use single BFS or DFS traversal with O(n) complexity to find depth and parent.

✓

Test Cases

Focus on handling special cases like siblings and root nodes to avoid common pitfalls.

Consider algorithmic traps such as greedy approaches or incomplete BFS traversals.

Optimize your solution to run in linear time using BFS or DFS to handle large inputs efficiently.

t1_01basic

Input{"root":[1,2,3,4],"x":4,"y":3}

Expectedfalse

⏱ Performance - must finish in 2000ms

Node 4 is at depth 2 with parent 2, node 3 is at depth 1 with parent 1, so they are not cousins.

💡 Think about the depth and parent of each node.

💡 Check if both nodes have the same depth but different parents.

💡 Return true only if depths match and parents differ.

Why it failed: Returned true incorrectly: failed to verify that nodes are at the same depth and have different parents. Fix by checking both conditions explicitly.

✓ Correctly identified nodes are not cousins due to different depths or parents.

t1_02basic

Input{"root":[1,2,3,null,4,null,5],"x":5,"y":4}

Expectedtrue

⏱ Performance - must finish in 2000ms

Nodes 4 and 5 are at depth 2 with different parents (2 and 3 respectively), so they are cousins.

💡 Use BFS or DFS to find depth and parent of each node.

💡 Verify that depths are equal and parents are different.

💡 Return true only if both conditions hold.

Why it failed: Returned false incorrectly: likely failed to check parents properly or depths are not compared correctly. Fix by storing and comparing both depth and parent for each node.

✓ Correctly identified nodes as cousins with same depth and different parents.

t2_01edge

Input{"root":[1,2,3],"x":2,"y":3}

Expectedfalse

⏱ Performance - must finish in 2000ms

Nodes 2 and 3 are siblings (same parent 1), so they are not cousins.

💡 Check if nodes share the same parent.

💡 If parents are the same, nodes cannot be cousins.

💡 Return false if parents match regardless of depth.

Why it failed: Returned true incorrectly: failed to detect sibling relationship. Fix by comparing parents and returning false if they are the same.

✓ Correctly identified siblings are not cousins.

t2_02edge

Input{"root":[1,2],"x":1,"y":2}

Expectedfalse

⏱ Performance - must finish in 2000ms

Node 1 is the root and node 2 is its child; root cannot be cousin with any node.

💡 Consider the depth of the root node (0).

💡 Root node has no parent, so cannot be cousin with any node.

💡 Return false if either node is root.

Why it failed: Returned true incorrectly: failed to handle root node case. Fix by checking if either node is root and returning false.

✓ Correctly handled root node case.

t2_03edge

Input{"root":[1,2,3,4,null,null,5],"x":4,"y":5}

Expectedtrue

⏱ Performance - must finish in 2000ms

Node 4 is at depth 2 with parent 2, node 5 is at depth 2 with parent 3; since depths are equal and parents differ, nodes 4 and 5 are cousins.

💡 Check depths carefully for both nodes.

💡 If depths differ, return false regardless of parents.

💡 Return true only if depths equal and parents differ.

Why it failed: Returned true incorrectly: failed to verify depths are equal. Fix by comparing depths before parents.

✓ Correctly identified nodes at same depth with different parents as cousins.

t3_01corner

Input{"root":[1,2,3,4,null,null,5,6],"x":6,"y":5}

Expectedfalse

⏱ Performance - must finish in 2000ms

Node 6 is child of 4 at depth 3, node 5 is child of 3 at depth 2; different depths, so not cousins.

💡 Check if nodes are at the same depth.

💡 If depths differ, nodes cannot be cousins.

💡 Return false if depths differ regardless of parents.

Why it failed: Returned true incorrectly: failed to check depth equality before parent comparison. Fix by adding depth equality check first.

✓ Correctly rejected nodes at different depths as cousins.

t3_02corner

Input{"root":[1,2,3,4,5,6,7],"x":4,"y":5}

Expectedfalse

⏱ Performance - must finish in 2000ms

Nodes 4 and 5 are siblings (same parent 2), so not cousins.

💡 Check if nodes share the same parent.

💡 Siblings are not cousins even if at same depth.

💡 Return false if parents are the same.

Why it failed: Returned true incorrectly: failed to detect sibling relationship. Fix by comparing parents and returning false if equal.

✓ Correctly identified siblings are not cousins.

t3_03corner

Input{"root":[1,2,3,null,4,null,5],"x":4,"y":5}

Expectedtrue

⏱ Performance - must finish in 2000ms

Nodes 4 and 5 are at same depth with different parents, so they are cousins.

💡 Use BFS to track nodes level by level.

💡 Check parents of nodes at the same level.

💡 Return true if parents differ and depths equal.

Why it failed: Returned false incorrectly: likely used greedy or incomplete BFS that stops early. Fix by completing BFS level and checking all nodes at that level.

✓ Correctly identified cousins using BFS level order traversal.

t4_01performance

Input{"root":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"x":99,"y":100}

Expectedtrue

⏱ Performance - must finish in 2000ms

Large tree with 100 nodes; solution must run in O(n) time to avoid timeout.

💡 Use BFS or DFS with O(n) complexity.

💡 Avoid repeated traversals or exponential approaches.

💡 Track depth and parent in a single traversal.

Why it failed: Solution timed out due to exponential or repeated traversals. Fix by using single BFS or DFS traversal with O(n) complexity.

✓ Solution runs efficiently in O(n) time for large input.

Practice

1. Given the following code snippet implementing the optimal zigzag level order traversal, what is the value of result after processing the input tree [3,9,20,null,null,15,7] (3 is root, 9 left child, 20 right child, 15 and 7 are children of 20)?

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

def zigzagLevelOrder(root):
    if not root:
        return []
    currentLevel = [root]
    nextLevel = []
    result = []
    left_to_right = True
    while currentLevel:
        level_vals = []
        while currentLevel:
            node = currentLevel.pop()
            level_vals.append(node.val)
            if left_to_right:
                if node.left:
                    nextLevel.append(node.left)
                if node.right:
                    nextLevel.append(node.right)
            else:
                if node.right:
                    nextLevel.append(node.right)
                if node.left:
                    nextLevel.append(node.left)
        result.append(level_vals)
        currentLevel, nextLevel = nextLevel, []
        left_to_right = not left_to_right
    return result

easy

A. [[3], [20, 9], [15, 7]]

B. [[3], [9, 20], [15, 7]]

C. [[3], [20, 9], [7, 15]]

D. [[3], [9, 20], [7, 15]]

Solution

1. Step 1: Trace first level

   Start with root 3, left_to_right is True, so level_vals = [3]. Children added to nextLevel: left 9, right 20.

2. Step 2: Trace second level

   Now currentLevel = [9, 20], left_to_right is False, pop 20 first, then 9. level_vals = [20, 9]. For 20, add right child 7 then left child 15 to nextLevel.

3. Step 3: Trace third level

   currentLevel = [7, 15], left_to_right is True, pop 15 then 7, level_vals = [15, 7]. No children to add.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Order matches zigzag pattern for given tree [OK]

Hint: Pop order and push order alternate each level [OK]

Common Mistakes:

• Swapping children order incorrectly
• Mixing up left_to_right flag

2. Given the following code snippet and the binary tree below, what is the final returned value? Tree structure: 1 / \ 2 3 / \ 4 5

from collections import deque

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

class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
        queue = deque([root])
        node = None
        while queue:
            node = queue.popleft()
            if node.right:
                queue.append(node.right)
            if node.left:
                queue.append(node.left)
        return node.val

root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
sol = Solution()
print(sol.findBottomLeftValue(root))

easy

A. 2

B. 5

C. 4

D. 3

Solution

1. Step 1: Trace queue operations

   Start with queue=[1]. Pop 1, enqueue right=3 then left=2 -> queue=[3,2]. Pop 3, enqueue right=5 then left=4 -> queue=[2,5,4]. Pop 2 (no children) -> queue=[5,4]. Pop 5 (no children) -> queue=[4]. Pop 4 (no children) -> queue=[]. Last popped node is 4.

2. Step 2: Identify last popped node value

   Last popped node is 4, so return 4.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Last node popped is 4, confirming BFS with right-to-left insertion finds bottom-left node [OK]

Hint: Trace queue pops and inserts carefully to find last node [OK]

Common Mistakes:

• Confusing order of enqueueing children
• Assuming left child is processed before right in BFS
• Returning first node at last level instead of last popped

3. You are given a binary tree and need to find the shortest distance from the root node down to the nearest leaf node. Which algorithmic approach guarantees the optimal solution with minimal time complexity?

easy

A. Breadth-First Search (BFS) stopping at the first encountered leaf node

B. Dynamic Programming storing minimum depths for subtrees and combining results

C. Depth-First Search (DFS) exploring all paths to leaves and returning the minimum depth

D. Greedy approach choosing the child with the smaller value at each step

Solution

1. Step 1: Understand the problem requirement

   The problem asks for the minimum depth to a leaf node, which means the shortest path from root to any leaf.

2. Step 2: Identify the algorithm that finds shortest path in unweighted trees

   BFS explores nodes level by level and stops immediately when it finds the first leaf, ensuring the shortest path is found efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BFS stops at first leaf -> minimal depth found [OK]

Hint: Shortest path in trees -> BFS with early stop [OK]

Common Mistakes:

• Assuming DFS always finds minimum depth efficiently
• Confusing greedy value-based choice with shortest path
• Thinking DP is needed for simple tree traversal

4. Suppose the vertical order traversal problem is extended so that nodes can appear multiple times if they have the same column and row but different parents (e.g., in a graph-like structure with shared nodes). Which modification to the BFS with column tracking approach correctly handles this scenario?

hard

A. Modify BFS to track (node, column, row) and store nodes in a list keyed by (column, row), then sort by parent ID

B. Use DFS with sorting by column, row, and parent to order nodes

C. Use BFS with column tracking but ignore row and parent, just append nodes as visited

D. Use BFS with column tracking and a visited set to avoid revisiting nodes

Solution

1. Step 1: Understand problem extension

   Nodes can appear multiple times if they share column and row but differ by parent, so row and parent info must be tracked.

2. Step 2: Evaluate modifications

   Tracking (node, column, row) and sorting by parent ID ensures correct ordering. Ignoring row or parent loses correctness. Visited set prevents duplicates but may skip valid repeats.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Tracking row and parent allows correct ordering of duplicates [OK]

Hint: Track row and parent to distinguish duplicates in BFS [OK]

Common Mistakes:

• Ignoring row or parent info leads to incorrect grouping
• Using visited set that skips valid repeated nodes

5. Suppose the problem changes: instead of finding the minimum depth to any leaf, you must find the minimum depth to a leaf node with a specific target value. Which modification to the BFS approach is correct?

hard

A. Continue BFS until the first leaf is found, then check if its value matches target; if not, continue BFS

B. Use DFS to explore all paths and return the minimum depth of leaves matching the target value

C. Modify BFS to enqueue only nodes whose values are less than or equal to the target value

D. Stop BFS at the first node with the target value, regardless of whether it is a leaf

Solution

1. Step 1: Understand the new requirement

   We want the minimum depth to a leaf node with a specific value, not just any leaf.

2. Step 2: Modify BFS to check leaf value before returning

   BFS should stop only when it finds a leaf node whose value matches the target; otherwise, continue searching.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BFS guarantees shortest path; checking leaf value before stopping is correct [OK]

Hint: BFS with conditional leaf check for target value [OK]

Common Mistakes:

• Stopping at first leaf regardless of value
• Pruning BFS incorrectly by node values
• Switching to DFS losing BFS optimality