Description of the Situation: We have an arbitrary binary tree, a node of that tree, and also an integer: 'K.' We need to print all such nodes which have a distance K from the given node and return the list of these nodes. You can check out this problem here as well: . Print Nodes at Distance k from Node The distance between the two nodes in a binary tree is defined as the number of connections/edges in the path between the two nodes. Let’s see an example: Let's examine the tree shown in the diagram: = pointer to node with data 8. Inputs: target = pointer to node with data 20. root k = 2. 10 14 22 Output : If the target is 14 and k is 3, then the output should be “4 20.” In this type of node, two types of nodes are to be considered: 1. The target node is rooted in the subtree. If the value of k is 2 and the target node is 8, for example, such nodes are 10 and 14. 2. Other nodes could be a target's ancestor or a node in a different subtree. This category includes node 22 for target node 8 when k is 2. Finding the first type of node is straightforward. In a recursive call, simply visit subtrees rooted with the target node and decrement k. As soon as k becomes 0, print the node that is currently being traversed. So, we will call a new function printkdistance(). And we must go through all ancestors for the output nodes that are not in the subtree that has the target node as the root. We calculate the distance between each ancestor and the target node, d. We then travel to the ancestor's other subtree (if the target was discovered in the left subtree, we go to the right subtree, and vice versa) and find all nodes at k-d distance from the ancestor. Let’s see how can we implement this approach: int data; Node left, right; { data = item; } } Node root; { } { System.out.print(node.data); } } { } { printkdistance(node, k); } int dl = printkdistanceNode(node.left, target, k); { { System.out.print(node.data); } } int dr = printkdistanceNode(node.right, target, k); { { System.out.print(node.data); } } } Node target = tree.root.left.right; } } // This is a java program //to print nodes at a distance k from the given node // A Node of a Binary Tree class Node { Node ( int item ) left = right = null ; class BinaryTree { // Recursive function that will help to print all the nodes at distance k in // tree (or subtree) rooted with a given root. void printkdistance ( Node node, int k ) // Base Case will be, if (node == null || k < 0 ) { return ; // If we find a k distant node, we'll print it if (k == 0 ) System.out.println( "" ); return ; // Recursion for left and right subtrees printkdistance(node.left, k- 1 ); printkdistance(node.right, k- 1 ); // Prints nodes at a distance k from a given target node. // The nodes that are at k distance may be in an up or down direction. // This function will return the distance of the root node from the target node. // And, it will return -1 if the target node is not present in a tree rooted with the root // node. int printkdistanceNode ( Node node, Node target, int k ) // The First Base Case: If the tree is empty, then return (-1). if (node == null ) { return - 1 ; // If the target is the same as the root node. We will use the downward // function that will print all nodes at distance k in the subtree rooted with // target or root if (node == target) return 0 ; // Recursion for left subtree. // Check if the target node was in the left subtree. if (dl != - 1 ) // If the root is at k distance from the target, then print the root node. // Note that the distance of root's left child from the target is dl. if (dl + 1 == k) System.out.println( "" ); // Else go into the right subtree and print all the nodes that are at distance of k-dl-2. // Note that the right child is only 2 edges away from the left child. else printkdistance(node.right, k - dl - 2 ); // Now, add 1 to the distance and return the value for parent calls. return 1 + dl; // Now, we will MIRROR THE ABOVE CODE FOR THE RIGHT SUBTREE as well. // Note that we will reach here only when node was not found in left // subtree if (dr != - 1 ) if (dr + 1 == k) System.out.println( "" ); else printkdistance(node.left, k - dr - 2 ); return 1 + dr; // If target is neither in the left nor in the right subtree return - 1 ; // To test the above functions, a Driver Program public static void main ( String args[] ) { BinaryTree tree = new BinaryTree(); /* Let us make the tree as shown in above diagram */ tree.root = new Node( 20 ); tree.root.left = new Node( 8 ); tree.root.right = new Node( 22 ); tree.root.left.left = new Node( 4 ); tree.root.left.right = new Node( 12 ); tree.root.left.right.left = new Node( 10 ); tree.root.left.right.right = new Node( 14 ); tree.printkdistanceNode(tree.root, target, 2 ); Output: 4 20 In this approach, no node is being traversed more than twice. So, the time complexity is O(n). Time Complexity: Another Approach: First, get the Path from the Root Node and add it to a list. For every 'i' th element from Path, just iterate and print nodes that are at '(K-i)'th distance. public int val; public TreeNode left; public TreeNode right; } { discoverPath(root, target); findKDistance( path.get(i), K - j, answer, } } { } answer.add(node.val); } } { path.add(node); } } { TreeNode target = root.left.right; } } import java.io.*; import java.util.*; class TreeNode { public TreeNode ( ) {} public TreeNode ( int val ) { this .val = val; } class CodingNinjas { List<TreeNode> path = null ; //Finding the nodes that are at a distance of K from the target node. public List<Integer> distanceK ( TreeNode root, TreeNode target, int K ) path = new ArrayList<>(); List<Integer> answer = new ArrayList<>(); for (int j= 0 ; j<path.size(); j++) { j == 0 ? null : path.get(j - 1 )); //Now return the list of all nodes at a distance K. return answer; // Blocker is used for nodes that are ancestors; if the target is at left, then we will // have to go right, or if the target is at right, then we will have to go left. public void findKDistance ( TreeNode node, int dist, List<Integer> answer, TreeNode blocker ) if (dist < 0 || node == null || (blocker != null && node == blocker)) { return ; if (dist == 0 ) { findKDistance(node.left, dist - 1 , answer, blocker); findKDistance(node.right, dist - 1 , answer, blocker); //To find the path of the target node from the root node. public boolean discoverPath ( TreeNode node, TreeNode target ) if (node == null ) return false ; if (node==target || discoverPath(node.left, target) || discoverPath(node.right, target)) { return true ; return false ; public static void main ( String [] args ) CodingNinjas codingninjas = new CodingNinjas(); /* Let us make the tree shown in above diagram */ TreeNode root = new TreeNode( 20 ); root.left = new TreeNode( 8 ); root.right = new TreeNode( 22 ); root.left.left = new TreeNode( 4 ); root.left.right = new TreeNode( 12 ); root.left.right.left = new TreeNode( 10 ); root.left.right.right = new TreeNode( 14 ); System.out.println(codingninjas.distanceK(root, target, 2 )); Output: [4, 20] Conclusion In this article, we have studied how to print Nodes at Distance k from Node. We hope that this article has provided you with the help to enhance your knowledge regarding Binary Tree.
