Print all nodes at distance k from a given node | GeeksforGeeks
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.
http://k2code.blogspot.com/2015/09/for-given-node-of-binary-tree-print-k.html
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.
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.
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.
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.
http://algorithms.tutorialhorizon.com/print-all-the-nodes-which-are-x-distance-from-the-given
Read full article from Print all nodes at distance k from a given node | GeeksforGeeks
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.
http://k2code.blogspot.com/2015/09/for-given-node-of-binary-tree-print-k.html
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.
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.
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.
class Node { int data; Node left, right; Node(int item) { data = item; left = right = null; }}class BinaryTree { static Node root; /* Recursive function to print all the nodes at distance k in the tree (or subtree) rooted with given root. See */ void printkdistanceNodeDown(Node node, int k) { // Base Case if (node == null || k < 0) { return; } // If we reach a k distant node, print it if (k == 0) { System.out.print(node.data); System.out.println(""); return; } // Recur for left and right subtrees printkdistanceNodeDown(node.left, k - 1); printkdistanceNodeDown(node.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 node, Node target, int k) { // Base Case 1: If tree is empty, return -1 if (node == 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 (node == target) { printkdistanceNodeDown(node, k); return 0; } // Recur for left subtree int dl = printkdistanceNode(node.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.print(node.data); System.out.println(""); } // 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(node.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(node.right, target, k); if (dr != -1) { if (dr + 1 == k) { System.out.print(node.data); System.out.println(""); } else { printkdistanceNodeDown(node.left, k - dr - 2); } return 1 + dr; } // If target was neither present in left nor in right subtree return -1; }
}
http://k2code.blogspot.com/2015/09/for-given-node-of-binary-tree-print-k.htmlMethod 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.
http://algorithms.tutorialhorizon.com/print-all-the-nodes-which-are-x-distance-from-the-given
Read full article from Print all nodes at distance k from a given node | GeeksforGeeks
