Cousins in Binary Tree

Easy
1884.

Cousins in Binary Tree

Cousins in Binary Tree is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Meta and Bloomberg interviews.

You are given the root of a binary tree whose node values are all distinct, and the values x and y of two different nodes in it.

Two nodes are cousins if they are at the same depth but have different parents. The root is at depth 0 and each child is one deeper than its parent.

Return true if the nodes holding x and y are cousins, and false otherwise.

Example 1

Input
root = [1,2,3,4], x = 4, y = 3
Output
false
Explanation
4 is two levels down, 3 only one: different depths.

Example 2

Input
root = [1,2,3,null,4,null,5], x = 5, y = 4
Output
true
Explanation
4 and 5 are both at depth 2, with parents 2 and 3.

Example 3

Input
root = [1,2,3,null,4], x = 2, y = 3
Output
false
Explanation
2 and 3 share the same depth but also the same parent — they are siblings, not cousins.

Constraints

  • 2 <= number of nodes <= 100
  • 1 <= Node.val <= 100
  • all node values are distinct
  • x != y
  • x and y are both values in the tree
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} x
 * @param {number} y
 * @return {boolean}
 */
var isCousins = function(root, x, y) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Cousins in Binary Tree — Solution in Python, Java & C++

Cousins in Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Cousins in Binary Tree is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Meta and Bloomberg interviews.

Problem statement

You are given the root of a binary tree whose node values are all distinct, and the values x and y of two different nodes in it.

Two nodes are cousins if they are at the same depth but have different parents. The root is at depth 0 and each child is one deeper than its parent.

Return true if the nodes holding x and y are cousins, and false otherwise.

Example 1

Input: root = [1,2,3,4], x = 4, y = 3
Output: false
Explanation: 4 is two levels down, 3 only one: different depths.

Example 2

Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true
Explanation: 4 and 5 are both at depth 2, with parents 2 and 3.

Example 3

Input: root = [1,2,3,null,4], x = 2, y = 3
Output: false
Explanation: 2 and 3 share the same depth but also the same parent — they are siblings, not cousins.

Constraints

  • 2 <= number of nodes <= 100
  • 1 <= Node.val <= 100
  • all node values are distinct
  • x != y
  • x and y are both values in the tree

Hints for Cousins in Binary Tree

  1. Hint 1

    Two facts decide the answer for each of x and y: how deep the node is, and who its parent is.

  2. Hint 2

    One traversal can record both facts for both values — pass the depth and the parent down as you go.

  3. Hint 3

    Cousins means equal depths and different parents; siblings fail the second test.

How to solve Cousins in Binary Tree

Being cousins depends only on each node's depth and parent, so one traversal that carries (depth, parent) down to every node finds everything needed.

Approach

  1. Traverse the tree from the root with depth 0 and no parent (use a value that cannot occur, such as 0).
  2. At each node pass depth + 1 and the node's own value as the parent to its children.
  3. When the node's value is x or y, record its depth and parent.
  4. Return true exactly when the two depths are equal and the two parents differ.

Why it works

Values are distinct, so each of x and y is recorded once, with the true depth and parent of that node. The definition of cousins is precisely the final comparison.

Complexity

  • Time — O(n)
  • Space — O(h) for the recursion or stack

Pitfalls

  • Same depth alone is not enough — siblings share a parent and are not cousins.
  • A breadth-first search works too: check, level by level, whether both values appear in the same level and are not children of the same node.

Reference solution

Python

from typing import Optional

def isCousins(root: Optional[TreeNode], x: int, y: int) -> bool:
    found = {}
    stack = [(root, 0, 0)]  # node, depth, parent value (0: no parent)
    while stack:
        node, depth, parent = stack.pop()
        if node.val == x or node.val == y:
            found[node.val] = (depth, parent)
        for child in (node.left, node.right):
            if child:
                stack.append((child, depth + 1, node.val))
    dx, px = found[x]
    dy, py = found[y]
    return dx == dy and px != py

Java

public static boolean isCousins(TreeNode root, int x, int y) {
    int[] info = new int[4]; // depth of x, parent of x, depth of y, parent of y
    locate(root, 0, 0, x, y, info);
    return info[0] == info[2] && info[1] != info[3];
}

static void locate(TreeNode node, int depth, int parent, int x, int y, int[] info) {
    if (node == null) return;
    if (node.val == x) { info[0] = depth; info[1] = parent; }
    if (node.val == y) { info[2] = depth; info[3] = parent; }
    locate(node.left, depth + 1, node.val, x, y, info);
    locate(node.right, depth + 1, node.val, x, y, info);
}

C++

void locate(TreeNode* node, int depth, int parent, int x, int y, int* info);

bool isCousins(TreeNode* root, int x, int y) {
    int info[4] = {0, 0, 0, 0}; // depth of x, parent of x, depth of y, parent of y
    locate(root, 0, 0, x, y, info);
    return info[0] == info[2] && info[1] != info[3];
}

void locate(TreeNode* node, int depth, int parent, int x, int y, int* info) {
    if (!node) return;
    if (node->val == x) { info[0] = depth; info[1] = parent; }
    if (node->val == y) { info[2] = depth; info[3] = parent; }
    locate(node->left, depth + 1, node->val, x, y, info);
    locate(node->right, depth + 1, node->val, x, y, info);
}

JavaScript

var isCousins = function(root, x, y) {
    var info = [0, 0, 0, 0]; // depth of x, parent of x, depth of y, parent of y
    var stack = [[root, 0, 0]];
    while (stack.length > 0) {
        var top = stack.pop(), node = top[0], depth = top[1], parent = top[2];
        if (node.val === x) { info[0] = depth; info[1] = parent; }
        if (node.val === y) { info[2] = depth; info[3] = parent; }
        if (node.left !== null) stack.push([node.left, depth + 1, node.val]);
        if (node.right !== null) stack.push([node.right, depth + 1, node.val]);
    }
    return info[0] === info[2] && info[1] !== info[3];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)