Given a binary tree, a target node in the binary tree, and an integer value k, print all the nodes that are at distance k from the given target node. No parent pointers are available.
Consider the tree shown in diagram Input: target = pointer to node with data 8. root = pointer to node with data 20. k = 2. Output : 10 14 22 If target is 14 and k is 3, then output should be "4 20"
There are two types of nodes to be considered.
1) Nodes in the subtree rooted with target node. For example if the target node is 8 and k is 2, then such nodes are 10 and 14.
2) Other nodes, may be an ancestor of target, or a node in some other subtree. For target node 8 and k is 2, the node 22 comes in this category.
Finding the first type of nodes is easy to implement. Just traverse subtrees rooted with the target node and decrement k in recursive call. When the k becomes 0, print the node currently being traversed . Here we call the function as printkdistanceNodeDown().
How to find nodes of second type? For the output nodes not lying in the subtree with the target node as the root, we must go through all ancestors. For every ancestor, we find its distance from target node, let the distance be d, now we go to other subtree (if target was found in left subtree, then we go to right subtree and vice versa) of the ancestor and find all nodes at kd distance from the ancestor.
Following is the implementation of the above approach.
 C++

#include <iostream>
using
namespace
std;
// A binary Tree node
struct
node
{
int
data;
struct
node *left, *right;
};
/* Recursive function to print all the nodes at distance k in the
tree (or subtree) rooted with given root. See */
void
printkdistanceNodeDown(node *root,
int
k)
{
// Base Case
if
(root == NULL  k < 0)
return
;
// If we reach a k distant node, print it
if
(k==0)
{
cout << root>data << endl;
return
;
}
// Recur for left and right subtrees
printkdistanceNodeDown(root>left, k1);
printkdistanceNodeDown(root>right, k1);
}
// Prints all nodes at distance k from a given target node.
// The k distant nodes may be upward or downward. This function
// Returns distance of root from target node, it returns 1 if target
// node is not present in tree rooted with root.
int
printkdistanceNode(node* root, node* target ,
int
k)
{
// Base Case 1: If tree is empty, return 1
if
(root == NULL)
return
1;
// If target is same as root. Use the downward function
// to print all nodes at distance k in subtree rooted with
// target or root
if
(root == target)
{
printkdistanceNodeDown(root, k);
return
0;
}
// Recur for left subtree
int
dl = printkdistanceNode(root>left, target, k);
// Check if target node was found in left subtree
if
(dl != 1)
{
// If root is at distance k from target, print root
// Note that dl is Distance of root's left child from target
if
(dl + 1 == k)
cout << root>data << endl;
// Else go to right subtree and print all kdl2 distant nodes
// Note that the right child is 2 edges away from left child
else
printkdistanceNodeDown(root>right, kdl2);
// Add 1 to the distance and return value for parent calls
return
1 + dl;
}
// MIRROR OF ABOVE CODE FOR RIGHT SUBTREE
// Note that we reach here only when node was not found in left subtree
int
dr = printkdistanceNode(root>right, target, k);
if
(dr != 1)
{
if
(dr + 1 == k)
cout << root>data << endl;
else
printkdistanceNodeDown(root>left, kdr2);
return
1 + dr;
}
// If target was neither present in left nor in right subtree
return
1;
}
// A utility function to create a new binary tree node
node *newnode(
int
data)
{
node *temp =
new
node;
temp>data = data;
temp>left = temp>right = NULL;
return
temp;
}
// Driver program to test above functions
int
main()
{
/* Let us construct the tree shown in above diagram */
node * root = newnode(20);
root>left = newnode(8);
root>right = newnode(22);
root>left>left = newnode(4);
root>left>right = newnode(12);
root>left>right>left = newnode(10);
root>left>right>right = newnode(14);
node * target = root>left>right;
printkdistanceNode(root, target, 2);
return
0;
}
Output:
4 20
Time Complexity: At first look the time complexity looks more than O(n), but if we take a closer look, we can observe that no node is traversed more than twice. Therefore the time complexity is O(n).
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