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. Consider the following Python code implementing the optimal DFS approach for bottom-up level order traversal. What is the final output when run on the given tree?

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

def levelOrderBottom(root):
    levels = []
    def dfs(node, level):
        if not node:
            return
        if len(levels) == level:
            levels.append([])
        levels[level].append(node.val)
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    dfs(root, 0)
    return levels[::-1]

root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20, TreeNode(15), TreeNode(7))
print(levelOrderBottom(root))

easy

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

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

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

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

Solution

1. Step 1: Trace dfs calls and levels

   Level 0: [3], Level 1: [9, 20], Level 2: [15, 7]

2. Step 2: Reverse levels list before returning

   Reversing [[3], [9, 20], [15, 7]] yields [[15, 7], [9, 20], [3]]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches bottom-up level order traversal [OK]

Hint: Remember to reverse levels collected by DFS [OK]

Common Mistakes:

• Forgetting to reverse levels
• Mixing up left and right children order

2. Consider the following Python code for vertical order traversal of a binary tree:

from collections import deque
from sortedcontainers import SortedDict

def verticalOrder(root):
    if not root:
        return []
    col_table = SortedDict()
    queue = deque([(root, 0)])
    while queue:
        node, col = queue.popleft()
        if col not in col_table:
            col_table[col] = []
        col_table[col].append(node.val)
        if node.left:
            queue.append((node.left, col - 1))
        if node.right:
            queue.append((node.right, col + 1))
    return list(col_table.values())

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

root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(verticalOrder(root))

What is the output of this code?

easy

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

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

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

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

Solution

1. Step 1: Trace queue and col_table updates

   Start with root (3, col=0). Append 3 to col 0. Enqueue left child (9, col=-1), right child (20, col=1).

2. Step 2: Process nodes in BFS order

   Process (9, -1): append 9 to col -1. No children. Process (20, 1): append 20 to col 1. Enqueue (15, 0), (7, 2). Process (15, 0): append 15 to col 0. Process (7, 2): append 7 to col 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Columns sorted: -1:[9], 0:[3,15], 1:[20], 2:[7] matches [[9], [3, 15], [20], [7]] [OK]

Hint: BFS preserves top-to-bottom order in each column [OK]

Common Mistakes:

• Mixing order of nodes in same column
• Misassigning column indices for children

3. You are given a binary tree and need to find the maximum width among all levels. The width is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), including null nodes in between. Which approach guarantees an optimal solution for this problem?

easy

A. Use BFS with indexing of nodes to track their positions and normalize indices at each level to avoid overflow.

B. Perform a simple level order traversal counting only non-null nodes at each level and take the maximum count.

C. Use DFS to traverse the tree and track the minimum and maximum node indices at each depth to compute width.

D. Apply a greedy approach that always picks the widest subtree at each node to estimate maximum width.

Solution

1. Step 1: Understand the problem constraints

   The width includes null nodes between end-nodes, so counting only non-null nodes per level underestimates width.

2. Step 2: Identify the approach that tracks positions

   BFS with indexing assigns position indices to nodes, allowing calculation of width as the difference between first and last indices at each level. Normalizing indices prevents integer overflow on deep trees.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Indexing with normalization handles sparse trees and deep levels correctly [OK]

Hint: Index nodes with BFS and normalize indices [OK]

Common Mistakes:

• Counting only non-null nodes per level
• Using DFS without proper indexing
• Ignoring index normalization causing overflow

4. 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

5. Suppose you want to modify the bottom-up level order traversal to return only the k bottom-most levels of the tree. Which modification to the optimal DFS approach is correct and efficient?

hard

A. Use BFS and prepend each level to the result list, stopping after k levels are collected.

B. During DFS, keep track of maximum depth and prune traversal once depth exceeds k.

C. Modify DFS to insert each node's value at the front of its level list to avoid reversal.

D. Perform full DFS to collect all levels, then slice the last k levels from the reversed list before returning.

Solution

1. Step 1: Understand requirement to return only k bottom-most levels

   We must know total depth to identify bottom k levels.

2. Step 2: Evaluate options

   Only performing full DFS and then slicing the reversed levels guarantees correctness; pruning by depth is incorrect because bottom levels are deepest, not shallowest.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Full DFS then slicing is simple and correct [OK]

Hint: Bottom k levels require knowing total depth first [OK]

Common Mistakes:

• Pruning DFS early loses bottom levels
• Inserting at front of level list breaks order