Are the Two Nodes on the Same Level With Different Parents
Solve this ProblemYou are given the root of a binary tree in which all node values are distinct, and two different integers x and y. Two nodes are cousins if they are on the same level of the tree but their parents are different nodes. Return true if the tree contains both x and y and the nodes holding them are cousins; otherwise return false.
You can find each value's depth and parent with two searches, or sweep the tree level by level and decide as soon as you know.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
2 ≤ number of nodes ≤ 100, and every node value is distinct, 1 ≤ node.val ≤ 1000 - ◆
x and y are two different integers between 1 and 1000; they may or may not appear in the tree - ◆
The tree is given as its root node; each node has a val, a left child and a right child - ◆
Two nodes are "cousins" when they are on the same level (same depth) but have different parents. Return true if both x and y are in the tree and their nodes are cousins; otherwise false (siblings, different levels, or a missing value)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Locate Each Value Separately, Then Compare
GoodSearch the tree twice with a helper that remembers the parent and depth as it descends. The first search finds x and reports its (parent, depth); the second finds y. If either value is missing, the answer is false. Otherwise the nodes are cousins exactly when their depths are equal but their parents differ. Each search may visit up to n nodes, so the time is O(n) (about 2n visits) with O(h) recursion space.
O(n)O(h)1class Solution {
2 public boolean areCousins(TreeNode root, int x, int y) {
3 int[] a = locate(root, null, 0, x);
4 int[] b = locate(root, null, 0, y);
5 if (a == null || b == null) return false;
6 return a[1] == b[1] && a[0] != b[0];
7 }
8
9 private int[] locate(TreeNode node, TreeNode parent, int depth, int target) {
10 if (node == null) return null;
11 if (node.val == target) return new int[]{parent == null ? -1 : parent.val, depth};
12 int[] left = locate(node.left, node, depth + 1, target);
13 if (left != null) return left;
14 return locate(node.right, node, depth + 1, target);
15 }
16}Optimal — One Level-by-Level Sweep With Early Exit
OptimalSweep the tree one level at a time with a queue. On each level, note whether x or y appears among its nodes. While handling a node, also check its two children: if they are exactly x and y, they are siblings, so the answer is false immediately. After finishing a level: if both were seen, they share a level and were never siblings — cousins, so return true. If only one was seen, the other lies on a different level (or does not exist) — return false without exploring any deeper. A single pass, and it stops as soon as the answer is known: O(n) worst case, O(w) space for the queue.
O(n)O(w)1class Solution {
2 public boolean areCousins(TreeNode root, int x, int y) {
3 if (root == null) return false;
4 Queue<TreeNode> queue = new ArrayDeque<>();
5 queue.add(root);
6 while (!queue.isEmpty()) {
7 int size = queue.size();
8 boolean seenX = false, seenY = false;
9 for (int i = 0; i < size; i++) {
10 TreeNode node = queue.poll();
11 if (node.val == x) seenX = true;
12 if (node.val == y) seenY = true;
13 if (node.left != null && node.right != null) {
14 int a = node.left.val, b = node.right.val;
15 if ((a == x && b == y) || (a == y && b == x)) return false;
16 }
17 if (node.left != null) queue.add(node.left);
18 if (node.right != null) queue.add(node.right);
19 }
20 if (seenX && seenY) return true;
21 if (seenX || seenY) return false;
22 }
23 return false;
24 }
25}