0
$\begingroup$

I've been given the following values to add to a binary search tree (in the order given)

56, 35, 55, 58, 29, 15, 16, 5, 71, 92, 69, 95

and this is what my tree ended up like:

but apparently it's wrong?

enter image description here

$\endgroup$
  • 1
    $\begingroup$ You've edited your question - and it became not clear what you were asking and what was answered... You could keep the original picture and add a modified one. This question and answers might be helpful for others - that's the main purpose of this site, so we all have to think about others too $\endgroup$ – HEKTO Sep 30 '19 at 15:41
0
$\begingroup$

Yes, it's wrong... The node 29 must be a left child of the node 35, the node 5 must be a left child of the node 15, and the node 69 must be a left child of the node 71 etc. - so, your algorithm makes wrong decision when there is a need to create a left child.

$\endgroup$
1
$\begingroup$

The property that makes a binary tree a binary search tree is that for every branch labeled $x$, all of the labels in the left subtree are smaller than $x$ and all of the labels in the right subtree are greater than $x$.

If you look at your tree, that property is violated in many places. For example, $5$ is in the right subtree of the node labeled $15$, yet $15 \not < 5$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.