You have a binary tree, find the minimum length from the input node to leaf.

Note: It does not have any parent pointer.A node of tree has only left, right and node value information.

Login

+1 vote

We can make adjacency list to store the graph, and then apply BFS from the input node.

As BFS increases level by level, for each node in particular level we check if the size of a vector is one then print that level of that node(i.e. the ans).

As BFS increases level by level, for each node in particular level we check if the size of a vector is one then print that level of that node(i.e. the ans).

commented
by
admin

You are correct. I have changed question, so how to solve this without repopulating given tree in any other structure.

0 votes

Explanation: the above program uses recursion to find the minimum length from any given node to a leaf in the Binary tree.

Approach

Find length of left subTree

Find length of right subTree

add one to a smallest of the two to find the actual length from node to the leaf

Note: sample binary tree is not formed in this example assuming binary tree is present and 3 is one value of it

Language: Java

```
class Test{
int minLength(int node){
if(node==null){
return -1;
}
int leftLength=minLength(node.Left);
int rightLength=minLength(node.right);
return min(leftLength, rightLength)+1;
}
min(int a, int b){
if(a<=b){
return a;
}else
return b;
}
public static void main(String[] args){
int node=3;
system.out.Println( minLength(node) );
}
}
```

- All categories
- Interview Question (230)
- Coding(Hiring) (42)
- Competitive Coding (5)
- Phone Interview (5)
- Written Test (15)
- Algorithm (12)
- Puzzle (4)

...