Hi, Construct a BST with 2,1,3. If my understanding is right, now distance between 2,3 will be 2. Will this algo return the correct answer?.
On Thu, Feb 2, 2012 at 1:43 PM, Manni mbd <[email protected]> wrote: > Forget my previous post. it useless i think > Firstly there will be only 1 node upwards which will be at a distance > K units from the specified node. > so we can take help of recursion > > int kthDistance(node *root, int k ,node *start){ > static node * kthUp = NULL; > int distance = -1; > if(node ==NULL) return -1; > else if(node==Start) return 0; > else{ > if(node->left){ > leftDepth = kthDistance(node->left); > if(leftDepth>=0) distance = leftDepth+1; > } > if(node->right && distance<0){ > rightDepth = kthDistance(node->right); > if(rightDepth >=0) distance = rightDepth+1; > } > if(distance ==k) kthUp = node; > return distance; > } > ..... > > hope this helps > > On 2/1/12, atul anand <[email protected]> wrote: > > @Manni : didnt get your algo for upward nodes. > > > > On Wed, Feb 1, 2012 at 2:30 PM, Manni mbd <[email protected]> wrote: > > > >> ^same as above.. > >> for upward.. start again from the nodes now distance is distance is > >> (distance of start node -k) .. if you reach this from the root.. print > >> it.. > >> also better is we use array rather than using linked list .. as > >> sorting can be a tedious task in case of link lists ! > >> > >> On 2/1/12, atul anand <[email protected]> wrote: > >> > if it is binary tree then to print the downward node... > >> > we can search for start node and then do level-order traversal or BFS > >> from > >> > start node till distance K recursively. > >> > > >> > no as we want nodes to be printed in sorted order..what we do is > crated > >> > a > >> > linked-list and insert nodes (found in above method) in sorted way. > >> > then print the linked list. > >> > > >> > for upward nodes......... thinking........... > >> > > >> > On Wed, Feb 1, 2012 at 9:52 AM, atul anand <[email protected]> > >> wrote: > >> > > >> >> are you sure given tree is binary tree and not BST. > >> >> if it is BST then we can search start node and then do inorder > >> >> traversal > >> >> from there. > >> >> before thinking printing abt upward node...please confirm if it a > >> >> binary > >> >> tree or BST. > >> >> > >> >> > >> >> On Tue, Jan 31, 2012 at 9:27 PM, Dhirendra Singh <[email protected]> > >> wrote: > >> >> > >> >>> > >> >>> 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. > >> >>> > >> >>> > >> >>> anyone any idea ?? how to print nodes above the specified node, > >> >>> > >> >>> Note : we do not have a reference to parent > >> >>> > >> >>> > >> >>> > >> >>> > >> >>> > >> >>> -- > >> >>> You received this message because you are subscribed to the Google > >> Groups > >> >>> "Algorithm Geeks" group. > >> >>> To post to this group, send email to [email protected]. > >> >>> To unsubscribe from this group, send email to > >> >>> [email protected]. > >> >>> For more options, visit this group at > >> >>> http://groups.google.com/group/algogeeks?hl=en. > >> >>> > >> >> > >> >> > >> > > >> > -- > >> > You received this message because you are subscribed to the Google > >> > Groups > >> > "Algorithm Geeks" group. > >> > To post to this group, send email to [email protected]. > >> > To unsubscribe from this group, send email to > >> > [email protected]. > >> > For more options, visit this group at > >> > http://groups.google.com/group/algogeeks?hl=en. > >> > > >> > > >> > >> -- > >> You received this message because you are subscribed to the Google > Groups > >> "Algorithm Geeks" group. > >> To post to this group, send email to [email protected]. > >> To unsubscribe from this group, send email to > >> [email protected]. > >> For more options, visit this group at > >> http://groups.google.com/group/algogeeks?hl=en. > >> > >> > > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]. > > For more options, visit this group at > > http://groups.google.com/group/algogeeks?hl=en. > > > > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
