Closest Leaf To Given Node In Binary Tree

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
18 upvotes
Asked in companies
Paytm (One97 Communications Limited)Paytm (One97 Communications Limited)Cerner Corporation

Problem statement

Ninja is stuck in a maze which is in a form of a binary tree. He needs your help in order to get out.

Ninja is presently at the node ‘X’. The only exit points of the maze are the leaf nodes of the tree. You need to tell him the distance to the nearest exit point from his current location. This will help him decide which path he should take in order to escape from the maze.

Example:

sample tree 1

Suppose, Ninja is stuck at node 62. The possible exit points in the maze are: 40, 10, and 20. From all the possible exit points the closest ones are 10 and 20 which are at a distance of 1 unit.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The very first line of input contains an integer 'T' denoting the number of test cases. 

The first of every test case contains the value of node ‘X’, i.e. Ninja’s current position.

The second line of every test case contains elements of the binary tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 on its place.
Example: 
The level order input for the tree depicted in the above image would be :

15 40 62 -1 -1 10 20 -1 -1 -1 -1

Explanation :

Level 1 :
The root node of the tree is 15.

Level 2 :
Left child of 15 = 40
Right child of 15 = 62

Level 3 :
Left child of 40 = null (-1)
Right child of 40 = null (-1)
Left child of 62 = 10
Right child of 62 = 20

Level 4 :
Left child of 10 = null (-1)
Right child of 10 = null (-1)
Left child of 20 = null (-1)
Right child of 20 = null (-1)

15
40 62
-1 -1 10 20
-1 -1 -1 -1
Output format: 
For each test case, return the distance to the nearest exit point from Ninja’s current location.
Note : 
1. Node ‘X’ will always be a unique value and will always be present in the tree.

2. You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= N <= 3000
1 <= DATA <= 10^5, DATA !=-1

Where 'N' denotes the number of nodes in the tree and 'DATA' denotes the node values of the tree.

Time limit: 1 sec
Sample Input 1:
2
62
15 40 62 -1 -1 10 20 -1 -1 -1 -1
2
6 1 3 5 -1 -1 2 -1 -1 -1 -1
Sample Output 1:
1
0
Explanation for Sample Output 1:
In test case 1, Refer to the example given above in the problem description.

In test case 2, from the input we can say that 2 is already a leaf node and thus it is the exit and hence closest exit distance will be 0.
Sample Input 2:
2
3
1 2 3 -1 -1 4 5 6 -1 -1 7 8 -1 -1 9 -1 -1 -1 -1
4
4 3 2 10 -1 3 1 -1 -1 -1 -1 -1 -1
Sample Output 2:
2
2
Explanation for Sample Output 2:
In test case 1, the tree given in the input can be represented as:-

sample tree 2

Ninja is stuck at node 3. The possible exit points in the maze are: 2, 8, and 9. From all the possible exit points the closest one is 2 which are at a distance of 2 units.

In test case 2, similarly we can notice that closest exit will be at distance 2.
Hint

A simple and intuitive approach could be to find the distance of the closest leaf node (from the node ‘X’) in the subtree rooted with the node ‘X’. Also find the distance of the closest leaf node (from the node ‘X’) in subtrees rooted with ancestors of node ‘X’. The minimum of these distances gives us the final answer.

Approaches (2)
Traverse All The Subtrees of Ancestors And Node 'X'

The important point to understand here is that the closest leaf can either be a descendent of the given node ‘X’ or can be reached through one of the ancestors of the given node ‘X’. The idea is to traverse the given tree in preorder until the given node ‘X’ is found. While traversing the tree to find the node ‘X’, store the ancestors of node ‘X’ in an array. These ancestor nodes act as a root for subtrees, which we’ll traverse later to find if there’s any other leaf node closer to node ‘X’ (other than the leaf nodes present in the subtree rooted at ‘X’).

 

When the given node ‘X’ is found in the tree. Calculate the distance of the closest leaf node in the subtree rooted at ‘X’. Store the result obtained in the previous step. Now, traverse through the previously-stored ancestor nodes array. For every subtree rooted with an ancestor, find the distance of the closest leaf node to the given node ‘X’. The minimum of these distances gives us the final answer.

Time Complexity

O(N ^ 2), Where ‘N’ is the number of nodes in the Binary tree.

 

Since for every subtree rooted with ancestor (of node ‘X’) we are traversing the complete subtree. Thus the time complexity will be O(N ^ 2).

Space Complexity

O(H), Where ‘H’ is the height of the Binary tree.

 

Since extra space is used by the recursion stack which goes to max depth of H. Also, O(H) extra space is also required for storing the ancestors of the given node. Thus the space complexity will be O(H).

Code Solution
(100% EXP penalty)
Closest Leaf To Given Node In Binary Tree
Full screen
Console