Like Adam says, the complexity will depend upon what your input looks like, as also, what exactly is the problem.
If you are required to do a search for the keys first, then it's going to be really expensive. If on the other hand, you already have the two pointers, and if you do have the parent pointers, then it can be done in O(d) on the depth of the tree (worst case O(n)). On the other hand, if the example that you gave is *the *tree, then the path from the nth node (the node with key = n) in the tree can be quite simply be determined in O(log n) time - both because the tree is balanced, and because the indices are integer positions and one simply do integer division by 2 right up to key=1 to discover the path to the root. On Wed, Sep 8, 2010 at 12:31 AM, Adam <wangyanadam1...@gmail.com> wrote: > What do you input into the algorithm corresponding to the specific > node? A pointer pointing to the node or just the key value of that > node used for query? These two situations are totally different in > which the former one can be handled in O(d) time complexity and the > other one will be O(2^d) complex, where d is the depth of the specific > node. > > On Sep 6, 11:08 pm, Debajyoti Sarma <sarma.debajy...@gmail.com> wrote: > > How to print the path from root to a specific node in a binary tree?? > > I want to store the path in a array[] of node*. > > can it b done in O(n) or less? > > Remember it's not BST. > > > > 1 > > / \ > > 2 3 > > / \ / \ > > 4 5 6 7 > > / \ / \ / \ / \ > > 8 9 10 11 12 13 14 15 > > > > path of 6 will b 1,3,6. > > path of 9 will be 1,2,5,11 > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
