A binary search tree, nodes are ordered. So if you go to the left subtree the data in all of the nodes is less than the data in current node. Going to right subtree all the data will be greater than the data in current node.
In short we need to define an order in that tree (how is the data arranged if at all. Or else it could potentially be O(n) - the number of nodes in the tree.) On Apr 10, 11:56 am, Himanshu Aggarwal <[email protected]> wrote: > Hi, > > The book on data structures by Langsam and Tanenbaum gives an alternate > representation of trees as : > > struct treenode { > int data; > struct treenode * son; > struct treenode * sibling; > > }; > > Such type of nodes can be used to make trees in which each node can have any > number of siblings. > > I am unable to understand the algorithmic complexity of searching for a node > in such a tree? > > While a simple binary search tree gives search complexity as log_2(n), where > 'n' are the number of nodes in the tree, does such a tree also gives > logarithmic complexity? In case it gives a logarithmic complexity, what > would be the base of logarithm in this case. Would it be 2 or some number > 'k' where 'k' might be dependent on certain factors? > > Also, what might be the exact searching algo in this kind of a tree? Some > pseudo code would be really appreciated. > > Thanks for your help in understanding this problem. > > With Regards, > Himanshu -- 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.
