Print All Nodes at K distance from the leaf node in Binary Search or Binary Search Tree

Print All Nodes at K distance from the leaf node in Binary Search or Binary Search Tree

We have to print Nodes at K distance from leaf Node in given Binary Tree. Here I have taken the Binary Search Tree. Because It is easy to make Binary Search Tree than making Binary Tree. 

Please see the following figure, this BST, which is made from following array:

Node Value for BST is:

array[]={10, 5, 6, 7, 3, 4, 17, 20, 15, 16, 18, 19}

Size of BST=12,

Here 10 is the root of the BST. We have to print the all nodes which is K=2 distance from the Leaf Nodes.

Leaf Nodes (Green colour) are 4, 7, 16, 19.

Nodes which are K=2, from leaf Node, are 5, 17, 20, please see yellow colour. For example 5 is at K=2 distance from the leaf node. 

Algorithms: 

First define the variable which we are going to use, 

K=> Given, Distance from the leaf Node.

len=> Initialize with zero, will use as index, in path array and visitedNode array.

path[] array, which will store the node during the tree traversal.

visitedNode boolean array, which will track the node, which are K, distance from leaf.

step1: Check root is null or not, if null return, otherwise step2.

step2: Assign root value to the path at len index. 

          Assign false to visitedNode for len index.

step3: check if the root is leaf node and visitedNode is false and difference between len-k-1>=0.

           Print that root, print=> path[len-k-1]. Change value of visitedNode at index len-k-1 to true. 

           If don't do this then, our algo will print double value. 

           return 

step4: Go to left subtree and repeat step1.

step5: Go to right subtree and repeat step1.

Time Complexity is O(N)

Please find the solution on Ideone:

http://ideone.com/PNelwg

Input: 

12

10 5 6 7 3 4 17 20 15 16 18 19
2

Output:

5 17 20

Now I will remove the visitedNode array, then what will happen, see the Ideone link

http://ideone.com/ECoUOl.

Input: 

12

10 5 6 7 3 4 17 20 15 16 18 19
2

Output:

5 5 17 20
Here we can see the we are again the same Node, So we need vistedNode boolean array to keep trap the Nodes which are at K distance from the leaf Node and print and visited previously.