583. Cousins in Binary Tree
You are given the root of a binary tree in which every node holds a distinct value, plus two of those values, x and y.
Two nodes are cousins when they sit at the same depth but hang from different parents. The root lives at depth 0, its children at depth 1, and so on. Siblings — the two children of one node — share a parent, so they are not cousins.
Return true if the nodes carrying x and y are cousins of each other, and false otherwise. Both values are guaranteed to appear somewhere in the tree.
Example 1:
Input: root = [1,2,3,null,4,null,5], x = 4, y = 5
Output: true
Explanation: Node 4 is a child of 2 and node 5 is a child of 3. Both sit at depth 2 under different parents, so they are cousins.
Example 2:
Input: root = [1,2,3,4], x = 4, y = 3
Output: false
Explanation: Node 4 sits at depth 2 while node 3 sits at depth 1. Nodes on different levels can never be cousins.
Example 3:
Input: root = [1,2,3], x = 2, y = 3
Output: false
Explanation: Nodes 2 and 3 share the parent 1 — they are siblings, and siblings are excluded by definition.
Constraints:
- The tree contains between 2 and 100 nodes.
- 1 ≤ Node.val ≤ 100, and every value is distinct.
- x ≠ y, and both values appear in the tree.
Hints:
"Cousins" is really two separate questions: do x and y sit at the same depth, and do they hang from different parents? Any traversal that records the depth and parent of each value can answer both.
With BFS you can process one whole level at a time: if x and y both show up inside the current level — and never as the two children of the same node — they are cousins. If only one of them shows up in a level, you can stop early.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1,2,3,null,4,null,5], x = 4, y = 5
Expected output: true