How is the Binary Search Tree [3,2,1,5,4,6] correct but [3,4,5,1,2] is not Valid?

Viewed 29

How is the Binary Search Tree [3,2,1,5,4,6] correct but [3,4,5,1,2] is not Valid?

For the first one, the Binary Search Tree is drawn in this image here Image for the Binary Tree [3 2 1 5 4 6]

For the second one, the Binary Search Tree is drawn in this image here

Image for the Binary Tree [3 4 5 1 2]

So my question is, why is it for the first Binary Search Tree [3 2 1 5 4 6] the tree is broken to a right node after we reach 5 but in the second Binary search tree [3 4 5 1 2] the number 1 and 2 in red are not in the left node branch even though it less than the root node, in the first one [3 2 1 5 4 6] why isn't 5 at the right node of 1 after 3 2 1? When do we know the root node needs to split to the other side or when the root should not be split but should continue splitting in the already started path?

1 Answers

why is it for the first Binary Search Tree [3 2 1 5 4 6] the tree is broken to a right node after we reach 5

When 5 is inserted in the then-existing tree, it is found greater than the root (3), and so a right-child is created for it:

    3
   / \
  2   5
 /
1

Then 4 and 6 are added which are both also greater than the root, and so then they also end up at the right side of the tree.

but in the second Binary search tree [3 4 5 1 2] the number 1 and 2 in red are not in the left node branch even though it less than the root node

When 1 is inserted, it is less than the root node (which is 3), and so it should be inserted as a left-child. It could never end up in the right subtree, because the right subtree of the root is only allowed to have values which are not less than the root, and so 1 and 2 are not allowed there. When 1 is inserted, we should get this:

    3
   / \
  1   4
       \
        5

And when 2 is inserted, it also must end up in the left subtree of the root. But as it is greater than 1, it will become a right child of that node:

    3
   / \
  1   4
   \   \
    2   5

in the first one [3 2 1 5 4 6] why isn't 5 at the right node of 1 after 3 2 1?

Because the insertion process should always start from the top, from the root, and there we find that 5 is greater than the root, so it should certainly not end up in the left subtree.

When do we know the root node needs to split to the other side

This is not really "splitting", but getting a new child. So this really is a matter of comparing the new value with the root value. It is very easy: when the value is less than the root, it should go into the left subtree (if exists) or become the left child (if there is none yet). If the value is greater than the root, it should go right. If there is no right child yet, it should be created.

Related