Print all nodes that are at distance k from a leaf node
Given a Binary Tree and a positive integer k, print all nodes that are distance k from a leaf node.
Here k distance from a leaf means k levels higher than a leaf node. For example if k is more than height of Binary Tree, then nothing should be printed. Expected time complexity is O(n) where n is the number nodes in the given Binary Tree.
The idea is to traverse the tree. Keep storing all ancestors till we hit a leaf node. When we reach a leaf node, we print the ancestor at distance k. We also need to keep track of nodes that are already printed as output. For that we use a boolean array visited[].
 C++

/* Program to print all nodes which are at distance k from a leaf */
#include <iostream>
using
namespace
std;
#define MAX_HEIGHT 10000
struct
Node
{
int
key;
Node *left, *right;
};
/* utility that allocates a new Node with the given key */
Node* newNode(
int
key)
{
Node* node =
new
Node;
node>key = key;
node>left = node>right = NULL;
return
(node);
}
/* This function prints all nodes that are distance k from a leaf node
path[] > Store ancestors of a node
visited[] > Stores true if a node is printed as output. A node may be k
distance away from many leaves, we want to print it once */
void
kDistantFromLeafUtil(Node* node,
int
path[],
bool
visited[],
int
pathLen,
int
k)
{
// Base case
if
(node==NULL)
return
;
/* append this Node to the path array */
path[pathLen] = node>key;
visited[pathLen] =
false
;
pathLen++;
/* it's a leaf, so print the ancestor at distance k only
if the ancestor is not already printed */
if
(node>left == NULL && node>right == NULL &&
pathLenk1 >= 0 && visited[pathLenk1] ==
false
)
{
cout << path[pathLenk1] <<
" "
;
visited[pathLenk1] =
true
;
return
;
}
/* If not leaf node, recur for left and right subtrees */
kDistantFromLeafUtil(node>left, path, visited, pathLen, k);
kDistantFromLeafUtil(node>right, path, visited, pathLen, k);
}
/* Given a binary tree and a nuber k, print all nodes that are k
distant from a leaf*/
void
printKDistantfromLeaf(Node* node,
int
k)
{
int
path[MAX_HEIGHT];
bool
visited[MAX_HEIGHT] = {
false
};
kDistantFromLeafUtil(node, path, visited, 0, k);
}
/* Driver program to test above functions*/
int
main()
{
// Let us create binary tree given in the above example
Node * root = newNode(1);
root>left = newNode(2);
root>right = newNode(3);
root>left>left = newNode(4);
root>left>right = newNode(5);
root>right>left = newNode(6);
root>right>right = newNode(7);
root>right>left>right = newNode(8);
cout <<
"Nodes at distance 2 are: "
;
printKDistantfromLeaf(root, 2);
return
0;
}
Output:
Nodes at distance 2 are: 3 1
Time Complexity: Time Complexity of above code is O(n) as the code does a simple tree traversal.
Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growthoriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at
http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide