Closest Leaf To Given Node In Binary Tree
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:

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.

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

Question

Closest Leaf To Given Node In Binary Tree

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.

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

Accepted Answer

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.

Space Complexity: O(n)Explanation:

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).

Time Complexity: O(n^2)Explanation:

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).

Accepted Answer

Efficient Approach

In the previous approach we were traversing all the subtrees rooted with ancestor, which can be avoided. Also the same subtrees are being traversed multiple times. So to avoid this, the idea here is to first traverse the subtree rooted at node ‘X’ and find the closest leaf node. Store this result. Now, we traverse subtrees rooted with ancestors of node ‘X’, starting from the root of the tree.

To avoid the traversal of subtrees which won’t give us the smallest distance we check the following condition:

If the given node ‘X’ is present in the left subtree, find the closest leaf in the right subtree as the for left subtree we have already calculated the smallest distance.
Otherwise, if the given node ‘X’ is present in the right subtree, find the closest leaf in the left subtree as the for right subtree we have already calculated the smallest distance.

Every time we find a leaf node, we check if the distance of the leaf from the given node is minimum or not. If its minimum, we update our result value.

Space Complexity: O(n)Explanation:

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

Since extra space is used by the recursion stack which goes to a max depth of H. Thus the space complexity will be O(H).

Time Complexity: O(n)Explanation:

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

Since we are traversing every node in the tree. Thus the time complexity will be O(N).

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:

Input format:

Example:

Explanation :

Output format:

Note :

Constraints:

Top Paytm Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Paytm Software Developer