993 · Cousins in Binary Tree

Two nodes are cousins when they sit at the same depth under different parents. Both halves matter, and the second one is what stops this from being a one-line depth comparison — siblings share a depth too, and siblings are explicitly not cousins.

1 — What to record

The reason this problem earns a place in the traversal pattern is that it needs two facts per node, gathered in a single pass: the node's depth, and its parent's value. Depth you already carry down as a recursion parameter; the parent is the same trick applied to a different piece of information. Once you see that a DFS can thread arbitrary context downward this way, the same shape solves a large family of questions.

Values are guaranteed unique in this problem, so the parent's value is enough to identify it — no need to pass the node reference itself.

2 — Cousins

root = [1,2,3,null,4,null,5], x = 5, y = 4. Both live at depth 2, under 3 and 2 respectively.

void dfs(TreeNode nd, int d, int parent) {    if (nd == null) return;    if (nd.val == x) { dx = d; px = parent; }    if (nd.val == y) { dy = d; py = parent; }    dfs(nd.left,  d + 1, nd.val);    dfs(nd.right, d + 1, nd.val);}

3 — Siblings are not cousins

root = [1,2,3,null,4], x = 2, y = 3. Same depth, but the same parent.

void dfs(TreeNode nd, int d, int parent) {    if (nd == null) return;    if (nd.val == x) { dx = d; px = parent; }    if (nd.val == y) { dy = d; py = parent; }    dfs(nd.left,  d + 1, nd.val);    dfs(nd.right, d + 1, nd.val);}

If you only compared depths you would return true here, and this is the test case that catches it.

4 — Complexity and edge cases

• Time: O(n), one pass. You can return early once both targets are found, but it does not change the bound.
• Space: O(h) for the recursion stack.
• The root has no parent — seed it with a sentinel (-1, or null if you pass node references). The root can never be a cousin of anything, so any sentinel that cannot collide with a real value works.
• x and y are guaranteed distinct and both present, so you do not need to handle "not found". If you generalise the function, decide what that should mean.
• BFS alternative: scan level by level; if exactly one of x and y appears on a level, return false; if both appear, return true unless they came from the same parent. Slightly more code, and it lets you stop at the shallower of the two.

5 — Reference implementation

private int dx, dy, px, py;

public boolean isCousins(TreeNode root, int x, int y) {
    dfs(root, 0, -1, x, y);           // -1: the root has no parent
    return dx == dy && px != py;         // same depth AND different parents
}

private void dfs(TreeNode nd, int d, int parent, int x, int y) {
    if (nd == null) return;
    if (nd.val == x) { dx = d; px = parent; }
    if (nd.val == y) { dy = d; py = parent; }
    dfs(nd.left,  d + 1, nd.val, x, y);
    dfs(nd.right, d + 1, nd.val, x, y);
}