Problem

Given a node in a binary tree. Find the rightmost cousin of the give node.

Examples

Example 1 Let’s start with an example.

1
2
3
4
5
6
7

      1
    /    \
  2       3
 /      /   \
4      5     6
  \        /
   7      8

1
2
3

Input: root = [1, 2, 3, 4, null, 5, 6, null, 7, null, null, 8], target = 4
Output: 6
Explanation: Rightmost cousin of 4 is 6, right most cousin of 7 is 8 and so on.

Solution

Method 1 - Level Order traversal

This approach finds cousins of a target node using Binary Tree Level Order Traversal - Level by Level.

The key is identifying when a new level begins. We track the number of nodes to traverse in the current level. Reaching zero and encountering the target node’s parent signals the next level contains the cousins.

The example illustrates how level tracking and queue size comparison help pinpoint the target level efficiently.

For example, Lets find the cousin of 4. Initially the queue has one element at level=1 i.e. the root {1} and size=1.

While traversing we remove 1 from the queue. Now size = 0 and a new level=2 began where we will enqueue {2, 3} and new size of queue = 2.

The next level will begin after two traverse. So, we can identify the beginning of next level by checking that number of traversals in current level is equal to the size of the queue during the end of previous level. For example: During level=2, size=2. So, next level will occur exactly after two remove operation. First 2 will be removed (now count=1) and its children {4} will be added in queue. Also, we know that the next level is our target level as we hit the target node 4. Then 3 will be removed (now count=0) and its children {5, 6} will be added to queue. At this moment new size of queue = 3.

Now, we are in the target level and all the nodes in the queue are in the same level hence are cousins and the last node is the right most cousin. Below is a O(n) time O(n) space code by using a LinkedList.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

public TreeNode rightMostCousin(TreeNode root, int target) {
	LinkedList<TreeNode> q = new LinkedList<TreeNode>();

	q.add(root);
	int size = q.size();
	boolean targetLevel = false;

	while (!q.isEmpty()) {
		int size = q.size();
		for (int i = 0; i < size; i++) {
			TreeNode curr = q.remove();
			if (curr.val == target) {
				targetLevel = true;
			}

			if (node.left != null) {
				q.add(curr.left);
			}
	
			if (node.right != null) {
				q.add(curr.right);
			}

			if (targetLevel && i == size - 1) {

				if (curr.val != target) {
					return curr;
				} else {
					return null;
				}
				
			}
		}
		
	}

	return null;
}

Complexity

  • Time Complexity - O(n) for doing BFS
  • Space Complexity - O(n) for storing elements in Queue