Cousins in Binary Tree
Easy · Trees · Tree · Depth-First Search · Breadth-First Search · Binary Tree
Problem
You are given the root of a binary tree whose values are all unique, and two different values x and y that both occur in the tree.
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.
Examples
Input: root = [1,2,3,4,5,6,7], x = 5, y = 6 Output: true
5 and 6 are both at depth 2, under parents 2 and 3.
Input: root = [1,2,3,4,5,6,7], x = 4, y = 5 Output: false
4 and 5 share the parent 2.
Input: root = [1,2,3,None,4], x = 3, y = 4 Output: false
3 is at depth 1 and 4 at depth 2.
Constraints
- 2 <= number of nodes <= 100
- 1 <= Node.val <= 100
- All values are unique
- x != y, and both are in the tree
Approaches
- Baseline: search for x and y separately — time O(n), space O(h)
Follow-up
What if you had to answer many cousin questions on the same tree? Record every node’s depth and parent once, then each question is O(1). See the use cases for listing all cousins of one node, and for replacing every value with the sum of its cousins.
Related problems
Start free on Cariara · Coding problems · System design studio
