For a Given node of a binary tree, print the K distance nodes.

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/problems/all-nodes-distance-k-in-binary-tree/.

Problem

You are given a function printKDistanceNodes which takes in a root node of a binary tree, a start node and an integer K. Complete the function to print the value of all the nodes (one-per-line) which are a K distance from the given start node in sorted order. Distance can be upwards or downwards.

Example

start node = 18, k = 2 , then output = 2, 19, 25

start node = 18, k = 3,  then output = -4, 3

Solution

We have already seen a similar problem, where we have to find k distance from the root and k distance from the leaf. Find the distance from root is easy. In the second case of printing from bottom to top (k distance from leaves), we know the direction, i.e. we have to go up. But here we have to find the k elements even going upwards.

Note :- Parent pointer is not given.

Method 1 - Using the recursion

(Printing nodes at a disance of K  downwards  is easy). Its a simple recursive function.So moving to nodes which are in upwards direction.

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 18 and k is 2, then such nodes are 19 and 25.
2) Other nodes, may be an ancestor of target, or a node in some other subtree. For target node 18 and k is 2, the node 2 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 (See this for more details). 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 k-d distance from the ancestor.

// 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)
    {
        System.out.println(root.data);
        return;
    }
 
    // Recur for left and right subtrees
    printkdistanceNodeDown(root.left, k-1);
    printkdistanceNodeDown(root.right, k-1);
}
 
// 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)
            System.out.println(root.data) endl;
 
         // Else go to right subtree and print all k-dl-2 distant nodes
         // Note that the right child is 2 edges away from left child
         else
            printkdistanceNodeDown(root.right, k-dl-2);
 
         // 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)
            System.out.println(root.data) endl;
         else
            printkdistanceNodeDown(root.left, k-dr-2);
         return 1 + dr;
    }
 
    // If target was neither present in left nor in right subtree
    return -1;
}

Method 2 - Using the queue

Use a queue of size K to store the root to node path.
Now since, the queue is of size K.As soon as we find the NODE  in tree, the node at front of queue is at a distance K from NODE. It can be the case that the front node is less than K distant from NODE.
So, maintain a counter.

Now start popping a node from queue which is at distant  i from NODE, and print all downwards nodes at distance K-i  in its other subtree.We only need to print the nodes in other  subtree to avoid Error.

Note :- Since we need to print the nodes in sorted order, we can maintain a priority queue to store the nodes and after processing the nodes, we can print it.

References

• http://www.geeksforgeeks.org/print-nodes-distance-k-given-node-binary-tree/
• stackoverflow.com/questions/7865055/nodes-at-a-distance-k-in-binary-tree
• http://stackoverflow.com/questions/27813998/how-to-find-nodes-at-a-distance-k-from-the-given-node-in-binary-tree

Read More

Print all nodes that are at distance k from a leaf node

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/problems/nodes-at-distance-k-from-leaf-nodes-in-binary-tree/.

Problem

Given a Binary Tree and a positive integer k, print all nodes that are distance k from a leaf node.

Here the meaning of distance is different from previous post. 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.




Example
(Please ignore the empty node, and consider it null)

k = 1, Answer = 2, 19 , 21
k = 2, Answer = 5, 18 , 19

Solution

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[].

// 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.data;
    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 &&
        pathLen-k-1 >= 0 && visited[pathLen-k-1] == false)
    {
        System.out.print(path[pathLen-k-1] + " ");
        visited[pathLen-k-1] = 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 = new int[MAX_HEIGHT];
    boolean[] visited = new boolean[MAX_HEIGHT];
    //all the elements false in visited
    Arrays.fill(visited, false);
    kDistantFromLeafUtil(node, path, visited, 0, k);
}

References

• http://www.geeksforgeeks.org/print-nodes-distance-k-leaf-node/

Read More

Print nodes at k distance from root

Given a root of a tree, and an integer k. Print all the nodes which are at k distance from root.
For example, in the below tree, 4, 5 & 8 are at distance 2 from root.

            1
          /   \
        2      3
      /  \    /
    4     5  8 

Code:

void printKDistant(node *root , int k)   
{
   if(root == NULL)
      return;
   if( k == 0 )
   {
      printf( "%d ", root->data );
      return ;
   }
   else
   {     
      printKDistant( root->left, k-1 ) ;
      printKDistant( root->right, k-1 ) ;
   }
}

Time Complexity: O(n) where n is number of nodes in the given binary tree.

Read More