# insertion order for complete binary search tree

• 10-20-2011, 01:02 PM
scottmulla
insertion order for complete binary search tree
what would be the insertion order for the integers 1-26 (inclusive) be in order to come out with a complete binary search tree?
• 10-20-2011, 01:21 PM
JosAH
Re: insertion order for complete binary search tree
Quote:

Originally Posted by scottmulla
what would be the insertion order for the integers 1-26 (inclusive) be in order to come out with a complete binary search tree?

The left sub tree doesn't just have to be complete, it has to be full, i.e. no more nodes 'fit' in it. A full tree contains 2^n-1 nodes so your left search tree contains 15 nodes. So your right tree contains 10 nodes (the root node is one node too). Your left tree contains the nodes 1 ... 15 so your root node is node 16 and your right sub tree contains the nodes 17 ... 26. Now that you know the value of the root node, apply the above reasoning to the left and right sub trees.

kind regards,

Jos
• 10-20-2011, 01:42 PM
scottmulla
Re: insertion order for complete binary search tree
sssssssssssssssssss
• 10-20-2011, 01:47 PM
scottmulla
Re: insertion order for complete binary search tree
cheers mate got it sussed