Cousins in Binary Tree

🎯

Cousins in Binary Tree

easyTREEAmazonGoogle

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

💡 This problem involves understanding tree traversal by levels and comparing nodes' parents and depths. Beginners often struggle because they confuse cousins with siblings or nodes at different depths, and they may not know how to efficiently traverse the tree level by level.

📋

Problem Statement

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

💡

Example

Input"root = [1,2,3,4], x = 4, y = 3"

Outputfalse

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

Input"root = [1,2,3,null,4,null,5], x = 5, y = 4"

Outputtrue

Nodes 4 and 5 are both at depth 2 but have different parents (2 and 3), so they are cousins.

• x and y are siblings → expected output: false
• x or y is the root node → expected output: false
• x and y are at different depths → expected output: false
• Tree with only two nodes → expected output: false

⚠️

Common Mistakes

Confusing cousins with siblings

Returns true for siblings, which is incorrect

✅ Ensure parents are different when depths are equal

Not checking if nodes are at the same depth

Returns true for nodes at different levels

✅ Compare depths explicitly before checking parents

Assuming root can be cousin with other nodes

Returns true if root is one of the nodes

✅ Root has no parent, so cousins condition fails if root involved

Using BFS but not resetting parent info each level

Incorrectly matches nodes from different levels

✅ Reset parent tracking variables at each BFS level

Not handling null children before accessing their values

Runtime errors or exceptions

✅ Check if child exists before accessing val

🧠

Brute Force (DFS to find depth and parent separately)

💡 This approach exists to build foundational understanding by explicitly finding each node's depth and parent through separate traversals, which helps beginners grasp the problem's core requirements before optimizing.

Intuition

We find the depth and parent of each target node by traversing the tree twice or more, then compare these values to decide if they are cousins.

Algorithm

1. Traverse the tree to find the depth and parent of node x.
2. Traverse the tree again to find the depth and parent of node y.
3. Compare the depths and parents of x and y.
4. Return true if depths are equal and parents are different; otherwise, false.

💡 The challenge is to separately track depth and parent for each node, which is straightforward but inefficient.

</>

Code

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

def find_depth_and_parent(root: Optional[TreeNode], val: int, depth: int = 0, parent: Optional[TreeNode] = None):
    if not root:
        return -1, None
    if root.val == val:
        return depth, parent
    left = find_depth_and_parent(root.left, val, depth + 1, root)
    if left[0] != -1:
        return left
    return find_depth_and_parent(root.right, val, depth + 1, root)

def isCousins(root: Optional[TreeNode], x: int, y: int) -> bool:
    x_depth, x_parent = find_depth_and_parent(root, x)
    y_depth, y_parent = find_depth_and_parent(root, y)
    return x_depth == y_depth and x_parent != y_parent

# Example usage:
# root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
# print(isCousins(root, 4, 3))  # Output: False

Line Notes

def find_depth_and_parent(root: Optional[TreeNode], val: int, depth: int = 0, parent: Optional[TreeNode] = None):Function signature includes depth and parent to track during recursion

if not root:Base case: reached leaf's child, val not found here

if root.val == val:Found the target node, return current depth and parent

left = find_depth_and_parent(root.left, val, depth + 1, root)Search left subtree, increment depth, current node is parent

if left[0] != -1:If found in left subtree, return result immediately

return find_depth_and_parent(root.right, val, depth + 1, root)Otherwise, search right subtree

x_depth, x_parent = find_depth_and_parent(root, x)Find depth and parent for x

y_depth, y_parent = find_depth_and_parent(root, y)Find depth and parent for y

return x_depth == y_depth and x_parent != y_parentCheck cousin condition: same depth, different parents

import java.util.*;
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}
public class Solution {
    private int xDepth = -1, yDepth = -1;
    private TreeNode xParent = null, yParent = null;

    private void dfs(TreeNode node, TreeNode parent, int depth, int x, int y) {
        if (node == null) return;
        if (node.val == x) {
            xDepth = depth;
            xParent = parent;
        } else if (node.val == y) {
            yDepth = depth;
            yParent = parent;
        }
        dfs(node.left, node, depth + 1, x, y);
        dfs(node.right, node, depth + 1, x, y);
    }

    public boolean isCousins(TreeNode root, int x, int y) {
        dfs(root, null, 0, x, y);
        return xDepth == yDepth && xParent != yParent;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(1);
    //     root.left = new TreeNode(2);
    //     root.right = new TreeNode(3);
    //     root.left.left = new TreeNode(4);
    //     Solution sol = new Solution();
    //     System.out.println(sol.isCousins(root, 4, 3)); // false
    // }
}

Line Notes

private void dfs(TreeNode node, TreeNode parent, int depth, int x, int y) {DFS helper to find depth and parent for x and y simultaneously

if (node == null) return;Base case: reached leaf's child

if (node.val == x) {Found node x, record depth and parent

else if (node.val == y) {Found node y, record depth and parent

dfs(node.left, node, depth + 1, x, y);Recurse left subtree, increment depth, current node is parent

dfs(node.right, node, depth + 1, x, y);Recurse right subtree similarly

return xDepth == yDepth && xParent != yParent;Check cousin condition after DFS completes

#include <iostream>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

class Solution {
    int xDepth = -1, yDepth = -1;
    TreeNode* xParent = nullptr;
    TreeNode* yParent = nullptr;

    void dfs(TreeNode* node, TreeNode* parent, int depth, int x, int y) {
        if (!node) return;
        if (node->val == x) {
            xDepth = depth;
            xParent = parent;
        } else if (node->val == y) {
            yDepth = depth;
            yParent = parent;
        }
        dfs(node->left, node, depth + 1, x, y);
        dfs(node->right, node, depth + 1, x, y);
    }

public:
    bool isCousins(TreeNode* root, int x, int y) {
        dfs(root, nullptr, 0, x, y);
        return xDepth == yDepth && xParent != yParent;
    }
};

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(1);
//     root->left = new TreeNode(2);
//     root->right = new TreeNode(3);
//     root->left->left = new TreeNode(4);
//     Solution sol;
//     cout << sol.isCousins(root, 4, 3) << endl; // Output: 0 (false)
//     return 0;
// }

Line Notes

void dfs(TreeNode* node, TreeNode* parent, int depth, int x, int y) {DFS helper to find depth and parent for x and y

if (!node) return;Base case: null node reached

if (node->val == x) {Found node x, record depth and parent

else if (node->val == y) {Found node y, record depth and parent

dfs(node->left, node, depth + 1, x, y);Recurse left subtree with updated depth and parent

dfs(node->right, node, depth + 1, x, y);Recurse right subtree similarly

return xDepth == yDepth && xParent != yParent;Check cousin condition after DFS

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function isCousins(root, x, y) {
    let xDepth = -1, yDepth = -1;
    let xParent = null, yParent = null;

    function dfs(node, parent, depth) {
        if (!node) return;
        if (node.val === x) {
            xDepth = depth;
            xParent = parent;
        } else if (node.val === y) {
            yDepth = depth;
            yParent = parent;
        }
        dfs(node.left, node, depth + 1);
        dfs(node.right, node, depth + 1);
    }

    dfs(root, null, 0);
    return xDepth === yDepth && xParent !== yParent;
}

// Example usage:
// const root = new TreeNode(1, new TreeNode(2, new TreeNode(4)), new TreeNode(3));
// console.log(isCousins(root, 4, 3)); // false

Line Notes

function dfs(node, parent, depth) {DFS helper to find depth and parent for x and y

if (!node) return;Base case: null node reached

if (node.val === x) {Found node x, record depth and parent

else if (node.val === y) {Found node y, record depth and parent

dfs(node.left, node, depth + 1);Recurse left subtree with updated depth and parent

dfs(node.right, node, depth + 1);Recurse right subtree similarly

return xDepth === yDepth && xParent !== yParent;Check cousin condition after DFS

⏱

Complexity

TimeO(n)

SpaceO(h)

We traverse the tree once or twice, each traversal is O(n). The recursion stack uses O(h) space where h is tree height.

💡 For n=100 nodes, this means at most 200 node visits and stack depth up to tree height, which is efficient enough for this problem.

Interview Verdict: Accepted

Though not the most optimal, this approach is accepted and helps understand the problem deeply before optimizing.

🧠

Better (Single DFS to find both nodes simultaneously)

💡 This approach improves efficiency by finding depth and parent of both nodes in a single DFS traversal, reducing redundant work and making the code cleaner.

Intuition

Instead of two separate traversals, we track both nodes' depth and parent in one DFS pass, then compare results.

Algorithm

1. Initialize variables to store depth and parent for x and y.
2. Perform a single DFS traversal, updating these variables when x or y is found.
3. After traversal, compare the depths and parents of x and y.
4. Return true if depths are equal and parents differ; otherwise, false.

💡 The key is to track both nodes in one traversal, which requires careful state management.

</>

Code

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

class Solution:
    def __init__(self):
        self.x_depth = -1
        self.y_depth = -1
        self.x_parent = None
        self.y_parent = None

    def dfs(self, node: Optional[TreeNode], parent: Optional[TreeNode], depth: int, x: int, y: int):
        if not node:
            return
        if node.val == x:
            self.x_depth = depth
            self.x_parent = parent
        elif node.val == y:
            self.y_depth = depth
            self.y_parent = parent
        self.dfs(node.left, node, depth + 1, x, y)
        self.dfs(node.right, node, depth + 1, x, y)

    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
        self.dfs(root, None, 0, x, y)
        return self.x_depth == self.y_depth and self.x_parent != self.y_parent

# Example usage:
# root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
# sol = Solution()
# print(sol.isCousins(root, 4, 3))  # Output: False

Line Notes

class Solution:Encapsulate state to track x and y info during DFS

def dfs(self, node: Optional[TreeNode], parent: Optional[TreeNode], depth: int, x: int, y: int):Single DFS to find both nodes simultaneously

if node.val == x:Record depth and parent for x when found

elif node.val == y:Record depth and parent for y when found

self.dfs(node.left, node, depth + 1, x, y)Recurse left subtree with updated depth and parent

self.dfs(node.right, node, depth + 1, x, y)Recurse right subtree similarly

return self.x_depth == self.y_depth and self.x_parent != self.y_parentCheck cousin condition after DFS

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}
public class Solution {
    private int xDepth = -1, yDepth = -1;
    private TreeNode xParent = null, yParent = null;

    private void dfs(TreeNode node, TreeNode parent, int depth, int x, int y) {
        if (node == null) return;
        if (node.val == x) {
            xDepth = depth;
            xParent = parent;
        } else if (node.val == y) {
            yDepth = depth;
            yParent = parent;
        }
        dfs(node.left, node, depth + 1, x, y);
        dfs(node.right, node, depth + 1, x, y);
    }

    public boolean isCousins(TreeNode root, int x, int y) {
        dfs(root, null, 0, x, y);
        return xDepth == yDepth && xParent != yParent;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(1);
    //     root.left = new TreeNode(2);
    //     root.right = new TreeNode(3);
    //     root.left.left = new TreeNode(4);
    //     Solution sol = new Solution();
    //     System.out.println(sol.isCousins(root, 4, 3)); // false
    // }
}

Line Notes

private void dfs(TreeNode node, TreeNode parent, int depth, int x, int y) {Single DFS to find both nodes' depth and parent

if (node == null) return;Base case for recursion

if (node.val == x) {Record x's depth and parent

else if (node.val == y) {Record y's depth and parent

dfs(node.left, node, depth + 1, x, y);Recurse left subtree

dfs(node.right, node, depth + 1, x, y);Recurse right subtree

return xDepth == yDepth && xParent != yParent;Check cousin condition

#include <iostream>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

class Solution {
    int xDepth = -1, yDepth = -1;
    TreeNode* xParent = nullptr;
    TreeNode* yParent = nullptr;

    void dfs(TreeNode* node, TreeNode* parent, int depth, int x, int y) {
        if (!node) return;
        if (node->val == x) {
            xDepth = depth;
            xParent = parent;
        } else if (node->val == y) {
            yDepth = depth;
            yParent = parent;
        }
        dfs(node->left, node, depth + 1, x, y);
        dfs(node->right, node, depth + 1, x, y);
    }

public:
    bool isCousins(TreeNode* root, int x, int y) {
        dfs(root, nullptr, 0, x, y);
        return xDepth == yDepth && xParent != yParent;
    }
};

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(1);
//     root->left = new TreeNode(2);
//     root->right = new TreeNode(3);
//     root->left->left = new TreeNode(4);
//     Solution sol;
//     cout << sol.isCousins(root, 4, 3) << endl; // Output: 0 (false)
//     return 0;
// }

Line Notes

void dfs(TreeNode* node, TreeNode* parent, int depth, int x, int y) {Single DFS to find both nodes' info

if (!node) return;Base case for recursion

if (node->val == x) {Record x's depth and parent

else if (node->val == y) {Record y's depth and parent

dfs(node->left, node, depth + 1, x, y);Recurse left subtree

dfs(node->right, node, depth + 1, x, y);Recurse right subtree

return xDepth == yDepth && xParent != yParent;Check cousin condition

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function isCousins(root, x, y) {
    let xDepth = -1, yDepth = -1;
    let xParent = null, yParent = null;

    function dfs(node, parent, depth) {
        if (!node) return;
        if (node.val === x) {
            xDepth = depth;
            xParent = parent;
        } else if (node.val === y) {
            yDepth = depth;
            yParent = parent;
        }
        dfs(node.left, node, depth + 1);
        dfs(node.right, node, depth + 1);
    }

    dfs(root, null, 0);
    return xDepth === yDepth && xParent !== yParent;
}

// Example usage:
// const root = new TreeNode(1, new TreeNode(2, new TreeNode(4)), new TreeNode(3));
// console.log(isCousins(root, 4, 3)); // false

Line Notes

function dfs(node, parent, depth) {Single DFS to find both nodes' depth and parent

if (!node) return;Base case for recursion

if (node.val === x) {Record x's depth and parent

else if (node.val === y) {Record y's depth and parent

dfs(node.left, node, depth + 1);Recurse left subtree

dfs(node.right, node, depth + 1);Recurse right subtree

return xDepth === yDepth && xParent !== yParent;Check cousin condition

⏱

Complexity

TimeO(n)

SpaceO(h)

Single DFS traversal visits each node once, O(n). Recursion stack uses O(h) space.

💡 For n=100, this halves the work compared to brute force, making it more efficient and elegant.

Interview Verdict: Accepted

This is a clean and efficient solution suitable for interviews.

🧠

Optimal (BFS Level Order Traversal)

💡 This approach uses BFS to traverse the tree level by level, which naturally groups nodes by depth. It checks if x and y appear at the same level with different parents, making the cousin check straightforward and efficient.

Intuition

By traversing level by level, we can detect if both nodes appear in the same level and verify their parents differ without extra depth tracking.

Algorithm

1. Initialize a queue with the root node.
2. While the queue is not empty, process nodes level by level.
3. For each level, check if x and y are found and record their parents.
4. If both found at the same level with different parents, return true.
5. If only one found at a level, return false immediately.
6. If neither found, continue to next level.
7. Return false if traversal ends without confirming cousins.

💡 The key is to leverage BFS to group nodes by depth and check cousin conditions within the same level.

</>

Code

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
    queue = deque([root])
    while queue:
        size = len(queue)
        x_parent = y_parent = None
        for _ in range(size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
                if node.left.val == x:
                    x_parent = node
                if node.left.val == y:
                    y_parent = node
            if node.right:
                queue.append(node.right)
                if node.right.val == x:
                    x_parent = node
                if node.right.val == y:
                    y_parent = node
        if x_parent and y_parent:
            return x_parent != y_parent
        if x_parent or y_parent:
            return False
    return False

# Example usage:
# root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
# print(isCousins(root, 4, 3))  # Output: False

Line Notes

queue = deque([root])Initialize queue for BFS starting with root

while queue:Process nodes level by level until queue is empty

size = len(queue)Number of nodes at current level

x_parent = y_parent = NoneReset parents for x and y at each level

for _ in range(size):Iterate over all nodes at current level

if node.left:Check left child existence

if node.left.val == x:Record parent if left child is x

if node.left.val == y:Record parent if left child is y

if node.right:Check right child existence

if node.right.val == x:Record parent if right child is x

if node.right.val == y:Record parent if right child is y

if x_parent and y_parent:If both found at this level, check if parents differ

if x_parent or y_parent:If only one found, they can't be cousins

return FalseIf neither found, continue or end with false

import java.util.*;
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}
public class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        if (root == null) return false;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            TreeNode xParent = null, yParent = null;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                    if (node.left.val == x) xParent = node;
                    if (node.left.val == y) yParent = node;
                }
                if (node.right != null) {
                    queue.offer(node.right);
                    if (node.right.val == x) xParent = node;
                    if (node.right.val == y) yParent = node;
                }
            }
            if (xParent != null && yParent != null) return xParent != yParent;
            if (xParent != null || yParent != null) return false;
        }
        return false;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(1);
    //     root.left = new TreeNode(2);
    //     root.right = new TreeNode(3);
    //     root.left.left = new TreeNode(4);
    //     Solution sol = new Solution();
    //     System.out.println(sol.isCousins(root, 4, 3)); // false
    // }
}

Line Notes

Queue<TreeNode> queue = new LinkedList<>();Initialize queue for BFS

while (!queue.isEmpty()) {Process nodes level by level

int size = queue.size();Number of nodes at current level

TreeNode xParent = null, yParent = null;Reset parents for x and y at each level

for (int i = 0; i < size; i++) {Iterate over current level nodes

if (node.left != null) {Check left child

if (node.left.val == x) xParent = node;Record parent if left child is x

if (node.left.val == y) yParent = node;Record parent if left child is y

if (node.right != null) {Check right child

if (node.right.val == x) xParent = node;Record parent if right child is x

if (node.right.val == y) yParent = node;Record parent if right child is y

if (xParent != null && yParent != null) return xParent != yParent;If both found, check parents differ

if (xParent != null || yParent != null) return false;If only one found, return false

#include <iostream>
#include <queue>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        if (!root) return false;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();
            TreeNode* xParent = nullptr;
            TreeNode* yParent = nullptr;
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front(); q.pop();
                if (node->left) {
                    q.push(node->left);
                    if (node->left->val == x) xParent = node;
                    if (node->left->val == y) yParent = node;
                }
                if (node->right) {
                    q.push(node->right);
                    if (node->right->val == x) xParent = node;
                    if (node->right->val == y) yParent = node;
                }
            }
            if (xParent && yParent) return xParent != yParent;
            if (xParent || yParent) return false;
        }
        return false;
    }
};

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(1);
//     root->left = new TreeNode(2);
//     root->right = new TreeNode(3);
//     root->left->left = new TreeNode(4);
//     Solution sol;
//     cout << sol.isCousins(root, 4, 3) << endl; // Output: 0 (false)
//     return 0;
// }

Line Notes

queue<TreeNode*> q;Initialize queue for BFS

while (!q.empty()) {Process nodes level by level

int size = q.size();Number of nodes at current level

TreeNode* xParent = nullptr;Reset x's parent for this level

TreeNode* yParent = nullptr;Reset y's parent for this level

for (int i = 0; i < size; i++) {Iterate over current level nodes

if (node->left) {Check left child

if (node->left->val == x) xParent = node;Record parent if left child is x

if (node->left->val == y) yParent = node;Record parent if left child is y

if (node->right) {Check right child

if (node->right->val == x) xParent = node;Record parent if right child is x

if (node->right->val == y) yParent = node;Record parent if right child is y

if (xParent && yParent) return xParent != yParent;If both found, check parents differ

if (xParent || yParent) return false;If only one found, return false

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function isCousins(root, x, y) {
    if (!root) return false;
    const queue = [root];
    while (queue.length > 0) {
        const size = queue.length;
        let xParent = null, yParent = null;
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            if (node.left) {
                queue.push(node.left);
                if (node.left.val === x) xParent = node;
                if (node.left.val === y) yParent = node;
            }
            if (node.right) {
                queue.push(node.right);
                if (node.right.val === x) xParent = node;
                if (node.right.val === y) yParent = node;
            }
        }
        if (xParent && yParent) return xParent !== yParent;
        if (xParent || yParent) return false;
    }
    return false;
}

// Example usage:
// const root = new TreeNode(1, new TreeNode(2, new TreeNode(4)), new TreeNode(3));
// console.log(isCousins(root, 4, 3)); // false

Line Notes

const queue = [root];Initialize queue for BFS

while (queue.length > 0) {Process nodes level by level

const size = queue.length;Number of nodes at current level

let xParent = null, yParent = null;Reset parents for x and y at each level

for (let i = 0; i < size; i++) {Iterate over current level nodes

if (node.left) {Check left child

if (node.left.val === x) xParent = node;Record parent if left child is x

if (node.left.val === y) yParent = node;Record parent if left child is y

if (node.right) {Check right child

if (node.right.val === x) xParent = node;Record parent if right child is x

if (node.right.val === y) yParent = node;Record parent if right child is y

if (xParent && yParent) return xParent !== yParent;If both found, check parents differ

if (xParent || yParent) return false;If only one found, return false

⏱

Complexity

TimeO(n)

SpaceO(n)

BFS visits each node once, O(n). Queue can hold up to O(n) nodes in worst case (complete binary tree last level).

💡 For n=100, BFS is efficient and uses extra space for the queue, but this is acceptable for typical interview constraints.

Interview Verdict: Accepted

This is the preferred approach in interviews for level-based tree problems due to its clarity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, the BFS approach is usually best to code due to clarity and natural level grouping. The single DFS is also acceptable. Brute force is mainly for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Separate DFS for each node)	O(n) per DFS, total O(n) * 2 = O(n)	O(h) recursion stack	Possible if tree is skewed	Yes	Mention only - never code
2. Better (Single DFS for both nodes)	O(n)	O(h) recursion stack	Possible if tree is skewed	Yes	Good to code if comfortable with DFS
3. Optimal (BFS Level Order Traversal)	O(n)	O(n) queue space in worst case	No	Yes	Preferred approach to code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach to show your understanding. Next, present the optimized DFS and BFS solutions. Practice coding and testing each approach.

How to Present

Step 1: Clarify the problem and confirm input/output expectations.Step 2: Describe the brute force approach to find depth and parent separately.Step 3: Improve to a single DFS traversal to find both nodes simultaneously.Step 4: Present BFS level order traversal as the optimal approach.Step 5: Code your chosen approach and test with examples and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of tree traversal, ability to track node depth and parent, and your skill in optimizing from brute force to BFS. They also check your coding accuracy and testing thoroughness.

Common Follow-ups

• What if the tree is very large? → BFS still works efficiently with O(n) time and space.
• Can you solve this without storing parents explicitly? → Not easily, since parent info is needed to distinguish siblings.

💡 These follow-ups test your understanding of scalability and the necessity of parent tracking in cousin detection.

🔍

Pattern Recognition

When to Use

1) Problem involves binary tree nodes, 2) Need to compare nodes at same depth, 3) Need to check parent nodes, 4) Cousin or sibling relationship mentioned.

Signature Phrases

same depthdifferent parentscousins in binary treelevel order traversal

NOT This Pattern When

Problems that only require DFS without parent or depth checks, or unrelated tree problems like BST insertions.

Similar Problems

Same Tree - checks structural equality, simpler tree traversalBinary Tree Level Order Traversal - BFS by levels, foundational for cousin checksCheck If Two Nodes are Siblings - similar parent check but siblings instead of cousins

Practice

1. You are given a binary tree and asked to compute the average value of nodes on each level. Which algorithmic approach guarantees an optimal solution that processes nodes level-by-level and efficiently computes these averages?

easy

A. Depth-first search (DFS) without tracking levels, summing all nodes and dividing by total count.

B. Breadth-first search (BFS) using a queue to traverse nodes level-by-level, summing values per level and dividing by the number of nodes at that level.

C. Greedy approach that picks the maximum node value at each level and averages those maximums.

D. Dynamic programming that stores partial sums of subtrees and combines them bottom-up.

Solution

1. Step 1: Understand the problem requires level-wise aggregation

   The problem asks for averages per level, so nodes must be grouped by their depth in the tree.

2. Step 2: Identify BFS as the natural approach for level order traversal

   BFS uses a queue to process nodes level-by-level, allowing summing and counting nodes at each level before moving on.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   BFS naturally groups nodes by level, enabling correct average calculation [OK]

Hint: Level order traversal = BFS with queue [OK]

Common Mistakes:

• Using DFS without level tracking loses level grouping
• Greedy max per level ignores all other nodes
• Bottom-up DP is unnecessary and complex here

2. You need to find the visible nodes when looking at a binary tree from the right side, returning the nodes that appear at each depth level from top to bottom. Which approach guarantees an optimal solution that captures the rightmost nodes at each level efficiently?

easy

A. Perform a DFS traversal visiting right child first and add the first node encountered at each depth level.

B. Use a BFS traversal but add the first node encountered at each level instead of the last.

C. Perform a DFS traversal visiting left child first and overwrite the node value at each depth level.

D. Use a BFS traversal and collect all nodes at each level, then pick the leftmost node.

Solution

1. Step 1: Understand traversal order impact

   Visiting the right child first ensures the first node encountered at each depth is the rightmost node visible from the right side.

2. Step 2: Why first node per level matters

   By adding the first node at each depth, we avoid overwriting with left nodes that are hidden behind right nodes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Right-first DFS captures rightmost nodes without overwriting [OK]

Hint: Right-first DFS adds first node per level [OK]

Common Mistakes:

• Visiting left child first and overwriting nodes causes left nodes to replace right nodes
• Using BFS but picking first node instead of last at each level
• Collecting leftmost nodes instead of rightmost

3. Consider the following code snippet for counting good nodes in a binary tree. Given the tree with root value 3, left child 1 (with left child 3), and right child 4 (with left child 1 and right child 5), what is the final returned count?

easy

A. 4

B. 6

C. 5

D. 3

Solution

1. Step 1: Trace stack operations and count updates

   Start with stack=[(3,3)]. Pop (3,3), count=1. Push right (4,3), left (1,3). Pop (1,3), node.val=1 < 3 no count. Push left (3,3). Pop (3,3), node.val=3 >=3 count=2. Pop (4,3), node.val=4 >=3 count=3. Push right (5,4), left (1,4). Pop (1,4), node.val=1 <4 no count. Pop (5,4), node.val=5 >=4 count=4.

2. Step 2: Final count after traversal

   Count is 4 after visiting all nodes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Count matches expected good nodes in example [OK]

Hint: Track max_val updates carefully during stack pops [OK]

Common Mistakes:

• Off-by-one counting
• Ignoring max_val update before pushing children
• Mixing left and right child order

4. The following code attempts the optimal DFS approach for bottom-up level order traversal. Identify the line containing the subtle bug that causes incorrect output for an empty tree input.

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]

medium

A. Line 10: dfs(root, 0)

B. Line 11: return levels[::-1]

C. Line 2: levels = []

D. Line 3: def dfs(node, level):

Solution

1. Step 1: Consider empty tree input (root = None)

   If root is None, dfs returns immediately without adding levels.

2. Step 2: Check what happens after dfs call

   levels remains empty, so return levels[::-1] returns [], which is correct and expected.

3. Step 3: Identify bug

   Returning levels[::-1] when levels is empty is correct; the subtle bug is missing an explicit check for root being None before calling dfs to avoid unnecessary calls.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Returning reversed empty list is correct; no bug in dfs call line [OK]

Hint: Returning reversed empty list is safe for empty tree [OK]

Common Mistakes:

• Assuming dfs call on None causes error
• Not handling empty tree explicitly but no failure occurs

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