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.

This approach improves upon the previous one by finding the required information for both nodes, x and y, in a single pass through the tree. We can perform a single Depth-First Search (DFS) traversal and keep track of the parent and depth of x and y as we encounter them.

Algorithm

Initialize class-level variables to store the parent and depth for x and y (e.g., parentX, depthX, parentY, depthY).
Create a recursive DFS helper function, dfs(node, parent, depth).
The function traverses the tree. When it encounters x or y, it records their respective parent and depth in the class-level variables.
If node.val == x, update parentX and depthX.
If node.val == y, update parentY and depthY.
Add an optimization to stop the traversal once both x and y have been found.
Recursively call dfs for the left and right children, passing node as the new parent and depth + 1 as the new depth.
After the initial call to dfs returns, compare the recorded values: return true if depthX == depthY and parentX != parentY.

Walkthrough

Instead of traversing the tree twice, we can gather all the necessary information in one go. We perform a single DFS from the root. During the traversal, we pass down the current node's parent and its depth. When we find either x or y, we store their parent and depth information in shared variables. After the traversal is complete, we will have the information for both nodes and can perform the final check.

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    private TreeNode parentX;18    private TreeNode parentY;19    private int depthX = -1;20    private int depthY = -1;21 22    public boolean isCousins(TreeNode root, int x, int y) {23        dfs(root, null, 0, x, y);24        return depthX == depthY && parentX != parentY;25    }26 27    private void dfs(TreeNode node, TreeNode parent, int depth, int x, int y) {28        if (node == null) {29            return;30        }31 32        if (node.val == x) {33            parentX = parent;34            depthX = depth;35        }36        if (node.val == y) {37            parentY = parent;38            depthY = depth;39        }40 41        // Optimization: if both found, no need to go deeper42        if (depthX != -1 && depthY != -1) {43            return;44        }45 46        dfs(node.left, node, depth + 1, x, y);47        48        // Optimization: if both found after left traversal, no need to traverse right49        if (depthX != -1 && depthY != -1) {50            return;51        }52        dfs(node.right, node, depth + 1, x, y);53    }54}

Complexity

Time

O(N), as we traverse each node at most once.

Space

O(H), where H is the height of the tree, for the recursion stack. In the worst case of a skewed tree, this is O(N).

Trade-offs

Pros

More efficient than two separate traversals as it only requires a single pass over the tree.
The logic is still relatively simple to follow.

Cons

Uses class-level variables to maintain state across recursive calls, which can sometimes be less clean than passing state through parameters or return values.
For very deep, skewed trees, the recursion depth could lead to a stack overflow error (though unlikely with the given constraints).

Since the definition of cousins is based on depth, a Breadth-First Search (BFS) is a very natural and efficient approach. BFS explores the tree level by level. We can iterate through the tree one level at a time and check if both x and y appear on the same level, while also ensuring they don't share the same parent.

Algorithm

Initialize a queue for level-order traversal and add the root.
Loop while the queue is not empty.
- In each iteration, first get the number of nodes at the current level (levelSize).
- Initialize boolean flags foundX = false and foundY = false for the current level.
- Loop levelSize times to process all nodes on the current level.
  - Dequeue a node.
  - Sibling Check: Check if the current node is the parent of both x and y. If node.left and node.right contain x and y, they are siblings, so return false immediately.
  - Check if the node's value is x or y and update the corresponding boolean flag.
  - Enqueue the non-null children of the node for the next level.
- After processing the level, check the flags:
  - If foundX and foundY are both true, they are on the same level and are not siblings (due to the earlier check). Return true.
  - If only one of foundX or foundY is true, they are at different depths. Return false.
If the loop completes without returning, it means the nodes were not found as cousins. Return false.

Walkthrough

This iterative approach uses a queue to explore the tree layer by layer. The key insight is to process all nodes at a given depth before moving to the next depth. For each level, we check for the presence of x and y. A crucial part of this approach is checking for the sibling condition: before we even check if a node's value is x or y, we check if its children are x and y. If they are, we know they share a parent and can immediately conclude they are not cousins.

If we finish a level and find that both x and y were present, we know they have the same depth and are not siblings, so they must be cousins. If only one was found, they are at different depths, so they cannot be cousins. If neither was found, we continue to the next level.

1import java.util.LinkedList;2import java.util.Queue;3 4/**5 * Definition for a binary tree node.6 * public class TreeNode {7 *     int val;8 *     TreeNode left;9 *     TreeNode right;10 *     TreeNode() {}11 *     TreeNode(int val) { this.val = val; }12 *     TreeNode(int val, TreeNode left, TreeNode right) {13 *         this.val = val;14 *         this.left = left;15 *         this.right = right;16 *     }17 * }18 */19class Solution {20    public boolean isCousins(TreeNode root, int x, int y) {21        if (root == null) {22            return false;23        }24 25        Queue<TreeNode> queue = new LinkedList<>();26        queue.offer(root);27 28        while (!queue.isEmpty()) {29            int levelSize = queue.size();30            boolean foundX = false;31            boolean foundY = false;32 33            // Process one level at a time34            for (int i = 0; i < levelSize; i++) {35                TreeNode node = queue.poll();36 37                // Check if x and y are children of the same node (siblings)38                if (node.left != null && node.right != null) {39                    if ((node.left.val == x && node.right.val == y) ||40                        (node.left.val == y && node.right.val == x)) {41                        return false;42                    }43                }44 45                if (node.val == x) foundX = true;46                if (node.val == y) foundY = true;47 48                if (node.left != null) queue.offer(node.left);49                if (node.right != null) queue.offer(node.right);50            }51 52            if (foundX && foundY) return true; // Found on same level, not siblings53            if (foundX || foundY) return false; // Found on different levels54        }55        return false;56    }57}

Complexity

Time

O(N), as each node is visited exactly once.

Space

O(W), where W is the maximum width of the tree. This space is used by the queue. In the worst case of a complete binary tree, W can be up to N/2, making the space complexity O(N).

Trade-offs

Pros

Very efficient as it can terminate early as soon as the conditions are met or violated.
Conceptually clean and a natural fit for problems involving levels/depth.
Iterative approach avoids potential stack overflow issues on very deep trees.

Cons

The space complexity can be O(N) for wide, complete binary trees, which might be worse than DFS's O(H) for very deep, narrow trees.

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 ); } }

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isCousins ( TreeNode * root , int x , int y ) { TreeNode * p1 , * p2 ; int d1 , d2 ; function < void ( TreeNode * , TreeNode * , int ) > dfs = [ & ]( TreeNode * root , TreeNode * fa , int d ) { if ( ! root ) { return ; } if ( root -> val == x ) { p1 = fa ; d1 = d ; } if ( root -> val == y ) { p2 = fa ; d2 = d ; } dfs ( root -> left , root , d + 1 ); dfs ( root -> right , root , d + 1 ); }; dfs ( root , nullptr , 0 ); return p1 != p2 && d1 == d2 ; } };

1# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def isCousins ( self , root : Optional [ TreeNode ], x : int , y : int ) -> bool : def dfs ( root , fa , d ): if root is None : return if root . val == x : t [ 0 ] = ( fa , d ) if root . val == y : t [ 1 ] = ( fa , d ) dfs ( root . left , root , d + 1 ) dfs ( root . right , root , d + 1 ) t = [ None , None ] dfs ( root , None , 0 ) return t [ 0 ][ 0 ] != t [ 1 ][ 0 ] and t [ 0 ][ 1 ] == t [ 1 ][ 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

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 ); } }

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isCousins ( TreeNode * root , int x , int y ) { TreeNode * p1 , * p2 ; int d1 , d2 ; function < void ( TreeNode * , TreeNode * , int ) > dfs = [ & ]( TreeNode * root , TreeNode * fa , int d ) { if ( ! root ) { return ; } if ( root -> val == x ) { p1 = fa ; d1 = d ; } if ( root -> val == y ) { p2 = fa ; d2 = d ; } dfs ( root -> left , root , d + 1 ); dfs ( root -> right , root , d + 1 ); }; dfs ( root , nullptr , 0 ); return p1 != p2 && d1 == d2 ; } };

1# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def isCousins ( self , root : Optional [ TreeNode ], x : int , y : int ) -> bool : def dfs ( root , fa , d ): if root is None : return if root . val == x : t [ 0 ] = ( fa , d ) if root . val == y : t [ 1 ] = ( fa , d ) dfs ( root . left , root , d + 1 ) dfs ( root . right , root , d + 1 ) t = [ None , None ] dfs ( root , None , 0 ) return t [ 0 ][ 0 ] != t [ 1 ][ 0 ] and t [ 0 ][ 1 ] == t [ 1 ][ 1 ]

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.