Problem

Submissions

Hints & solutions

Discuss

Cousins of Given Node in Binary Tree

Moderate

0/80

Average time to solve is 10m

13 upvotes

Asked in companies

Problem statement

Given a binary tree of N nodes and a node of this tree, you need to return a list containing the values of the cousins of the given node in the given binary tree sorted by non-decreasing order of their values.

Note:

Two nodes of a binary tree are cousins if they have the same depth or level, but have different parents.

No two nodes in the given binary tree will have the same data values.

Example :

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer T representing the number of test cases. 

The first line of each test case will contain the values of the nodes of the tree in the level order form ( -1 for NULL node). Refer to the below example for further clarification.

The second and the last line of each test case will contain the value of the node for which the cousins are to be found.

Example: 
Consider the binary tree:

The input of the tree depicted in the image above will be like: 

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :
Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null (-1).

Note :

The above format was just to provide clarity on how the input is formed for a given tree. 

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output format :

For each test case, print the value of the cousins of the given node in the binary tree, or -1 if the given node has no cousins in the binary tree.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 3000
1 <= nodeVal <= 10^9

Time Limit: 1 sec

Sample Input 1 :

2
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
4
1 2 3 -1 -1 -1 -1
2

Sample Output 1 :

5 6
-1

Explanation For Sample Input 1 :

The tree representation for test case 2 is given below.

Sample Input 2 :

2
1 2 3 4 5 6 -1 7 8 -1 -1 9 10 -1 -1 -1 -1 -1 -1 -1 -1
9   
1 2 -1 3 4 -1 -1 -1 -1
3

Sample Output 2 :

7 8 10
-1

Hint 1

Hint 2

Try using DFS to find the nodes at the same depth of the given node.

Approaches (2)

Approach 1

Approach 2

Depth First Search

Find the level of the given node of the binary tree. For this we will use a recursive approach, i.e. DFS. Keep in mind that the level of a parent is 1 less than its children.
Store all the nodes at the same level of the given node i.e. we found in the previous step in array.
Traverse array and remove those nodes which are siblings to the given node i.e. (parent of given node and node in array is the same.) .
Return the list.

Time Complexity

O(N), where N is the number of nodes in the given binary tree.

As, every node of the tree is visited twice in the traversal.

Space Complexity

O(H), where H is the height of the given tree.

In the worst case, as the maximum number of recursive calls at a time in the stack, is at max the total number of nodes in the tree when the given tree is skewed tree(H = N). Extra Space required for Depth First Traversals is O(H) for Binary Tree.

(100% EXP penalty)

Cousins of Given Node in Binary Tree

Console