0
$\begingroup$

I am studying binary trees and I am failing to see what numbers can be inserted into this specific node position. The values to pick from are : 16, 24, 36, 45, 49, 51, 58.

Binary Tree

I have tried values 24, 36, 45, and 16, 24, 36. I have tried these values because going from left to right, they go in increasing order. Though this is not working and I'm not quite sure why. I'm not sure why what I am selecting is wrong. Any help trying to solve my confusion is appreciated.

$\endgroup$
  • 1
    $\begingroup$ We're more likely to be able to help you if you edit the question to share your thoughts and your reasoning, what you think the answer should be, and why. $\endgroup$ – D.W. Jul 24 '18 at 2:34
  • $\begingroup$ Is the answer 36, 45, 49? These three are higher than everything to the left and lower than everything to the right. $\endgroup$ – J. Daniel Rutz Jul 24 '18 at 3:37
2
$\begingroup$

Binary trees can serve many different purposes. They don't necessarily need to be in an ordering like such.

Note that below, I hid key parts of the solution. You can view them by hovering over with your mouse, but I encourage you to try to solve it using clues from my response without seeing the actual answer.

For your particular problem, it appears that the ordering of the tree is such that all nodes to the 'right' have a value greater than our root (global or local root, doesn't matter) and all nodes to the 'left' have a value less than our root.

With this in mind, $u$ must be greater than our root node, so

$16$

is ruled out. Then, by taking $u$ to be our next (local) root node, $u$ must be greater than the maximum value of its left subtree and $u$ must be less than the minimum value of its right subtree. From this, we can see that

$28 < u < 50$.

This rules out

$24, 51, 58$.

Therefore, the answer to your problem is

$36, 45, 49$

$\endgroup$
  • $\begingroup$ Thanks so much for the helpful response! Great explanation and now I understand my mistake. $\endgroup$ – Tyler Jul 24 '18 at 23:12

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.