Cousins in Binary Tree

Easy

#0947Time: O(N). In the worst case, we traverse the entire tree twice, once for `x` and once for `y`. The complexity is O(N) + O(N) = O(N).Space: O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case of a skewed tree, this can be O(N).1 company

Algorithms

Depth-First Search Breadth-First Search

Data structures

Tree Binary Tree

Companies

Tekion

Prompt

Given the root of a binary tree with unique values and the values of two different nodes of the tree x and y, return true if the nodes corresponding to the values x and y in the tree are cousins, or false otherwise.

Two nodes of a binary tree are cousins if they have the same depth with different parents.

Note that in a binary tree, the root node is at the depth 0, and children of each depth k node are at the depth k + 1.

Example 1:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false

Example 2:

Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true

Example 3:

Input: root = [1,2,3,null,4], x = 2, y = 3
Output: false

Constraints:

The number of nodes in the tree is in the range [2, 100].
1 <= Node.val <= 100
Each node has a unique value.
x != y
x and y are exist in the tree.

Approaches

3 approaches with complexity analysis and trade-offs.

This straightforward approach involves two independent traversals of the tree. First, we traverse the tree to find the depth and parent of node x. Then, we perform a second, separate traversal to find the depth and parent of node y. Once we have this information for both nodes, we can easily check if they satisfy the conditions for being cousins (same depth, different parents).

Algorithm

Create a helper class or structure to hold the result of a search, containing the parent node and the depth.
Define a recursive helper function, findNode(node, parent, depth, target), that performs a DFS to find the target value.
If the current node is null, return null.
If node.val matches the target, create and return a new result object with the current parent and depth.
Recursively call findNode on the left child. If it returns a non-null result, propagate that result up.
Otherwise, recursively call findNode on the right child and return its result.
In the main isCousins function, call the helper function once to find the info for x.
Call the helper function a second time to find the info for y.
Compare the results: return true if infoX.depth == infoY.depth and infoX.parent != infoY.parent.

Walkthrough

The core idea is to isolate the problem of finding a node's information. We create a helper function that takes the root and a target value and returns the target's depth and its immediate parent. This function can be implemented using a standard Depth-First Search (DFS). The main function then orchestrates the process by calling this helper twice, once for x and once for y, and then comparing the returned information to make the final decision.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    // A simple class to hold the result of a search18    class NodeInfo {19        TreeNode parent;20        int depth;21        NodeInfo(TreeNode p, int d) {22            this.parent = p;23            this.depth = d;24        }25    }26 27    public boolean isCousins(TreeNode root, int x, int y) {28        NodeInfo infoX = findNode(root, null, 0, x);29        NodeInfo infoY = findNode(root, null, 0, y);30 31        return infoX.depth == infoY.depth && infoX.parent != infoY.parent;32    }33 34    private NodeInfo findNode(TreeNode node, TreeNode parent, int depth, int target) {35        if (node == null) {36            return null;37        }38        if (node.val == target) {39            return new NodeInfo(parent, depth);40        }41 42        NodeInfo leftResult = findNode(node.left, node, depth + 1, target);43        if (leftResult != null) {44            return leftResult;45        }46        47        return findNode(node.right, node, depth + 1, target);48    }49}

Complexity

Time

O(N). In the worst case, we traverse the entire tree twice, once for `x` and once for `y`. The complexity is O(N) + O(N) = O(N).

Space

O(H), where H is the height of the tree. This space is used by the recursion stack. In the worst case of a skewed tree, this can be O(N).

Trade-offs

Pros

Simple to conceptualize and implement.
The logic for finding a node is cleanly separated from the main comparison logic.

Cons

Inefficient as it may traverse the tree twice. If x and y are in different subtrees, each search might traverse a large portion of the tree.

Solutions

Solution

1/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int x , y ; private TreeNode p1 , p2 ; private int d1 , d2 ; public boolean isCousins ( TreeNode root , int x , int y ) { this . x = x ; this . y = y ; dfs ( root , null , 0 ); return p1 != p2 && d1 == d2 ; } private void dfs ( TreeNode root , TreeNode p , int d ) { if ( root == null ) { return ; } if ( root . val == x ) { p1 = p ; d1 = d ; } if ( root . val == y ) { p2 = p ; d2 = d ; } dfs ( root . left , root , d + 1 ); dfs ( root . right , root , d + 1 ); } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem