Knots at a distance of k in a binary tree

Question

You are given the printKDistanceNodes function, which takes the root of the node of the binary tree, the beginning of the node, and the integer K. Complete the function to print the values ​​of all nodes (one line) that are the distance K from the given beginning of the node in sorted order. The distance can be up or down.

Answer 1

private void printNodeAtN(Node root, Node start, int k) { if (root != null) { // calculate if the start is in left or right subtree - if start is // root this variable is null Boolean left = isLeft(root, start); int depth = depth(root, start, 0); if (depth == -1) return; printNodeDown(root, k); if (root == start) return; if (left) { if (depth > k) { // print the nodes at depth-k level in left tree printNode(depth - k - 1, root.left); } else if (depth < k) { // print the nodes at right tree level k-depth printNode(k - depth - 1, root.right); } else { System.out.println(root.data); } } else { // similar if the start is in right subtree if (depth > k) { // print the nodes at depth-k level in left tree printNode(depth - k - 1, root.right); } else if (depth < k) { // print the nodes at right tree level k-depth printNode(k - depth - 1, root.left); } else { System.out.println(root.data); } } } } // print the nodes at depth - "level" from root void printNode(int level, Node root) { if (level == 0 && root != null) { System.out.println(root.data); } else { printNode(level - 1, root.left); printNode(level - 1, root.right); } } // print the children of the start void printNodeDown(Node start, int k) { if (start != null) { if (k == 0) { System.out.println(start.data); } printNodeDown(start.left, k - 1); printNodeDown(start.right, k - 1); } } private int depth(Node root, Node node, int d) { if (root == null) return -1; if (root != null && node == root) { return d; } else { int left = depth(root.left, node, d + 1); int right = depth(root.right, node, d + 1); if (left > right) return left; else return right; } } 

Answer 2

At a distance of K there are no more nodes that are up - starting at the beginning of the node and moving up the parents for the steps K. Add this to the sorted data structure.

Then you need to add the descending nodes. To do this, you can make a BFS with a queue where you store the depth with the node when you insert it into the queue (the start node is at level 0, these are children at level 1, etc.). Then, when you place the nodes, if they are at level K, add them to the sorted data structure. when you start entering nodes at the K + 1 level, you can stop.

Finally, print the nodes from the sorted data structure (they will be sorted).

EDIT: if the parent pointer is missing:

Write a recursive function int Go(Node node) , which returns the depth of the start of the node relative to the one passed to the node and -1 if the subtree of the node does not contain start. The function will find the Kth parent as a side effect. Pseudocode:

 static Node KthParent = null; static Node start = ...; static int K = ...; int Go(Node node) { if (node == start) return 0; intDepth = -1; if(node.LeftChild != null) { int leftDepth = Go(node.LeftChild); if(leftDepth >= 0) intDepth = leftDepth+1; } if (intDepth < 0 && node.rightChild != null) { int rightDepth = Go(node.RightChild); if(rightDepth >= 0) intDepth = rightDepth+1; } if(intDepth == K) KthParent = node; return intDepth; } 

Answer 3

 private static int printNodeAtK(Node root, Node start, int k, boolean found){ if(root != null){ if(k == 0 && found){ System.out.println(root.data); } if(root==start || found == true){ int leftd = printNodeAtK(root.left, start, k-1, true); int rightd = printNodeAtK(root.right,start,k-1,true); return 1; }else{ int leftd = printNodeAtK(root.left, start, k, false); int rightd = printNodeAtK(root.right,start,k,false); if(leftd == k || rightd == k){ System.out.println(root.data); } if(leftd != -1 && leftd > rightd){ return leftd+1; }else if(rightd != -1 && rightd>leftd){ return rightd+1; }else{ return -1; } } } return -1; } 

Answer 4

 typedef struct node { int data; struct node *left; struct node *right; }node; void printkdistanceNodeDown(node *n, int k) { if(!n) return ; if(k==0) { printf("%d\n",n->data); return; } printkdistanceNodeDown(n->left,k-1); printkdistanceNodeDown(n->right,k-1); } void printkdistanceNodeDown_fromUp(node* target ,int *k) { if(!target) return ; if(*k==0) { printf("%d\n",target->data); return; } else { int val=*k; printkdistanceNodeDown(target,val-1); } } int printkdistanceNodeUp(node* root, node* n , int k) { if(!root) return 0; if(root->data==n->data) return 1; int pl=printkdistanceNodeUp(root->left,n,k); int pr=printkdistanceNodeUp(root->right,n,k); if(pl ) { k--; if(k==0) printf("%d\n",root->data); else { printkdistanceNodeDown_fromUp(root->right,k); printkdistanceNodeDown_fromUp(root->left,k-1); } return 1; } if(pr ) { k--; if(k==0) printf("%d\n",root->data); else { printkdistanceNodeDown_fromUp(root->left,k); printkdistanceNodeDown_fromUp(root->right,k-1); } return 1; } return 0; } void printkdistanceNode(node* root, node* n , int k ) { if(!root) return ; int val=k; printkdistanceNodeUp(root,n,k); printkdistanceNodeDown(n,val); } 

caller function: printkdistanceNode(root,n,k);

The output will print all nodes at a distance k from the given node up and down.

Answer 5

 struct node{ int data; node* left; node* right; bool printed; }; void print_k_dist(node** root,node** p,int k,int kmax); void reinit_printed(node **root); void print_k_dist(node** root,node **p,int k,int kmax) { if(*p==NULL) return; node* par=parent(root,p); if(k<=kmax &&(*p)->printed==0) { cout<<(*p)->data<<" "; (*p)->printed=1; k++; print_k_dist(root,&par,k,kmax); print_k_dist(root,&(*p)->left,k,kmax); print_k_dist(root,&(*p)->right,k,kmax); } else return; } void reinit_printed(node **root) { if(*root==NULL) return; else { (*root)->printed=0; reinit_printed(&(*root)->left); reinit_printed(&(*root)->right); } } 

Answer 6

Here in this code, PrintNodesAtKDistance will first try to find the required node.

 if(root.value == requiredNode) 

When we find the desired node, we print all the child nodes at a distance K from this node.

Now our task is to print all the nodes that are in other branches (Go up and print). We return -1 until we find our desired node. When we get our desired node, we get lPath or rPath >=0 . Now we need to print all the nodes that are at a distance of (lPath/rPath) -1

 public void PrintNodes(Node Root, int requiredNode, int iDistance) { PrintNodesAtKDistance(Root, requiredNode, iDistance); } public int PrintNodesAtKDistance(Node root, int requiredNode, int iDistance) { if ((root == null) || (iDistance < 0)) return -1; int lPath = -1, rPath = -1; if(root.value == requiredNode) { PrintChildNodes(root, iDistance); return iDistance - 1; } lPath = PrintNodesAtKDistance(root.left, requiredNode, iDistance); rPath = PrintNodesAtKDistance(root.right, requiredNode, iDistance); if (lPath > 0) { PrintChildNodes(root.right, lPath - 1); return lPath - 1; } else if(lPath == 0) { Debug.WriteLine(root.value); } if(rPath > 0) { PrintChildNodes(root.left, rPath - 1); return rPath - 1; } else if (rPath == 0) { Debug.WriteLine(root.value); } return -1; } public void PrintChildNodes(Node aNode, int iDistance) { if (aNode == null) return; if(iDistance == 0) { Debug.WriteLine(aNode.value); } PrintChildNodes(aNode.left, iDistance - 1); PrintChildNodes(aNode.right, iDistance - 1); } 

Answer 7

Here is the complete Java program. Geeksforgeeks Inspired Algorithm

 // Java program to print all nodes at a distance k from given node class BinaryTreePrintKDistance { Node root; /* * Recursive function to print all the nodes at distance k in tree (or * subtree) rooted with given root. */ void printKDistanceForDescendant(Node targetNode, int currentDist, int inputDist) { // Base Case if (targetNode == null || currentDist > inputDist) return; // If we reach ak distant node, print it if (currentDist == inputDist) { System.out.print(targetNode.data); System.out.println(""); return; } ++currentDist; // Recur for left and right subtrees printKDistanceForDescendant(targetNode.left, currentDist, inputDist); printKDistanceForDescendant(targetNode.right, currentDist, inputDist); } public int printkdistance(Node targetNode, Node currentNode, int inputDist) { if (currentNode == null) { return -1; } if (targetNode.data == currentNode.data) { printKDistanceForDescendant(currentNode, 0, inputDist); return 0; } int ld = printkdistance(targetNode, currentNode.left, inputDist); if (ld != -1) { if (ld + 1 == inputDist) { System.out.println(currentNode.data); } else { printKDistanceForDescendant(currentNode.right, 0, inputDist - ld - 2); } return ld + 1; } int rd = printkdistance(targetNode, currentNode.right, inputDist); if (rd != -1) { if (rd + 1 == inputDist) { System.out.println(currentNode.data); } else { printKDistanceForDescendant(currentNode.left, 0, inputDist - rd - 2); } return rd + 1; } return -1; } // Driver program to test the above functions @SuppressWarnings("unchecked") public static void main(String args[]) { BinaryTreePrintKDistance tree = new BinaryTreePrintKDistance(); /* Let us construct the tree 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); Node target = tree.root.left; tree.printkdistance(target, tree.root, 2); } static class Node<T> { public Node left; public Node right; public T data; Node(T data) { this.data = data; } } }