Cousins in Binary Tree

easy binary tree bfs depth

Problem

In a binary tree with unique values, two nodes are cousins if they are at the same depth but have different parents. Given the root of the tree and two distinct values x and y, return true if and only if the nodes with those values are cousins.

Inputroot = [1, 2, 3, null, 4, null, 5], x = 4, y = 5

Outputtrue

4 (child of 2) and 5 (child of 3) sit at the same depth 2 but under different parents, so they are cousins.

tree (level-order, comma-separated, use "null")

def is_cousins(root, x, y):
    queue = [(root, None)]
    while queue:
        info = {}
        nxt = []
        for node, parent in queue:
            info[node.val] = (parent, len(queue))
            if node.left:
                nxt.append((node.left, node))
            if node.right:
                nxt.append((node.right, node))
        if x in info and y in info:
            return info[x][0] is not info[y][0]
        if x in info or y in info:
            return False
        queue = nxt
    return False

function isCousins(root, x, y) {
  let queue = [[root, null]];
  while (queue.length) {
    const info = new Map();
    const nxt = [];
    for (const [node, parent] of queue) {
      info.set(node.val, parent);
      if (node.left) nxt.push([node.left, node]);
      if (node.right) nxt.push([node.right, node]);
    }
    if (info.has(x) && info.has(y)) return info.get(x) !== info.get(y);
    if (info.has(x) || info.has(y)) return false;
    queue = nxt;
  }
  return false;
}

class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        Queue<TreeNode[]> queue = new LinkedList<>();
        queue.add(new TreeNode[]{ root, null });
        while (!queue.isEmpty()) {
            Map<Integer, TreeNode> info = new HashMap<>();
            int sz = queue.size();
            for (int k = 0; k < sz; k++) {
                TreeNode[] pair = queue.poll();
                TreeNode node = pair[0], parent = pair[1];
                info.put(node.val, parent);
                if (node.left != null) queue.add(new TreeNode[]{ node.left, node });
                if (node.right != null) queue.add(new TreeNode[]{ node.right, node });
            }
            if (info.containsKey(x) && info.containsKey(y)) return info.get(x) != info.get(y);
            if (info.containsKey(x) || info.containsKey(y)) return false;
        }
        return false;
    }
}

bool isCousins(TreeNode* root, int x, int y) {
    queue<pair<TreeNode*, TreeNode*>> q;
    q.push({ root, nullptr });
    while (!q.empty()) {
        unordered_map<int, TreeNode*> info;
        int sz = q.size();
        for (int k = 0; k < sz; k++) {
            auto [node, parent] = q.front(); q.pop();
            info[node->val] = parent;
            if (node->left) q.push({ node->left, node });
            if (node->right) q.push({ node->right, node });
        }
        bool hx = info.count(x), hy = info.count(y);
        if (hx && hy) return info[x] != info[y];
        if (hx || hy) return false;
    }
    return false;
}

Explanation

Two nodes are cousins when they sit at the same depth but have different parents. So we really only need two facts about x and y: how deep each one is, and who its parent is.

A clean way to get both at once is a level-by-level BFS. We walk the tree one row at a time, carrying each node along with its parent as pairs (node, parent). For each row we record every value seen and which parent it came from in a small map called info.

Once a row is processed, we check: if both x and y appear on this row, they share a depth, so they are cousins exactly when their parents differ. If only one of them shows up here, they are on different levels and the answer is immediately false.

Because we decide as soon as either target appears, we never need to compare depths by hand — the level we are on does that for us.

Example: root = [1, 2, 3, null, 4, null, 5], x = 4, y = 5. On the third level both 4 and 5 appear; 4's parent is 2 and 5's parent is 3. Different parents, same depth, so the result is true.

Time: O(n) Space: O(n)