The O(n) Club: Cousins in Binary Tree: Sibling Rivalry—Algorithm Edition

The O(n) Club: Cousins in Binary Tree—Sibling Rivalry, Algorithm Edition

⚡ TL;DR

If two nodes are at the same depth but have different parents, congrats—they’re cousins, not jealous siblings. Just scan level by level with BFS and compare their parents. Fast, simple, and no family drama!

// Classic BFS to sniff out cousinly relations
public boolean isCousins(TreeNode root, int x, int y) {
    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) {
                if (node.left.val == x) xParent = node;
                if (node.left.val == y) yParent = node;
                queue.offer(node.left);
            }
            if (node.right != null) {
                if (node.right.val == x) xParent = node;
                if (node.right.val == y) yParent = node;
                queue.offer(node.right);
            }
        }
        if (xParent != null && yParent != null) {
            return xParent != yParent;
        }
        if (xParent != null || yParent != null) {
            return false;
        }
    }
    return false;
}
</treenode>

🧠 How Devs Usually Mess This Up

Classic rookie move: Find both nodes at the same depth, label them cousins, and promptly ship a buggy PR. Did you check for different parents? Nope. Oops, you just made siblings into cousins—cue the HR nightmares. And don’t get too comfy, this still works whether the tree is bushy, sparse, zig-zaggy, or as lopsided as your caffeine schedule. If you ignored node existence, enjoy the null pointer slap.

🔍 What’s Actually Going On

Imagine your company org chart. Two folks report to different managers, but share the same power level. That’s peers—cousins! Not folks reporting to the same boss, who are stuck in sibling rivalry. In tree land, it’s exactly the same logic: same level, different parent. Use BFS to meander level-by-level, sniffing out those cousin connections like an HR exec picking peer reviewers.

🛠️ PseudoCode

• BFS traversal. Queue the root, then loop through each tree level.
• Track if x or y is found at this level, stashing their parent nodes.
• After each level:

  • if (xParent != null && yParent != null)

    Return xParent != yParent.
  • Otherwise, if only one found:

    return false;

    They can’t be cousins, someone is lost or a time traveler.
• Keep looping until you run out of nodes or cousin drama.

💻 The Code

// Java BFS solution: No sibling-cousin confusion here!
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) {
                    if (node.left.val == x) xParent = node;
                    if (node.left.val == y) yParent = node;
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    if (node.right.val == x) xParent = node;
                    if (node.right.val == y) yParent = node;
                    queue.offer(node.right);
                }
            }
            if (xParent != null && yParent != null) {
                return xParent != yParent;
            }
            if (xParent != null || yParent != null) {
                return false;
            }
        }
        return false;
    }
     // Classic TreeNode definition
    public static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int x) { val = x; }
    }
}
</treenode>

⚠️ Pitfalls, Traps & Runtime Smacks

• Don’t ship if you haven’t double-checked parents! Siblings and cousins—never the same.
• If the tree looks more like spaghetti than a tree (unbalanced, missing nodes)—still works.
• Watch out: No guarantee x or y is even in the tree unless the interviewer promises it.
• Runtime? O(n) time, O(n) space. No Big-O biceps needed, just walk every node once.

🧠 Interviewer Brain-Tattoo

Every node has parents. Ask about them unless you want to send sibling drama to production.