How to construct binary search tree

Question

I'm currently learning binary search tree, if I insert these value into my tree:

13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18

Then my binary search tree would look like this:

If I add another number 15 to my tree:

13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18, 15

My question is whether this first one:

13
  \
   14
    \
     15
      \
       18

or second one:

13
  \
   14
     \
      18
      /
     15

is the correct way to insert 15 into above binary search tree?

Answer 1

Both ways would work, but the first one would be inconsistent with the way that your current tree is built.

Specifically, look at the 4-12-10 section:

4
 \
 12
 /
10

The level at which the data appears in the tree is fixed at insertion, and does not change as more items get added. That's why the second approach is what you are looking for.

Answer 2

The second output is the correct one if you are "usual" BST. However, if you are using balanced BSTs, then there is a possibility that it can lea to a rearrangement of the relative position of the nodes in the tree. I am pretty sure that the book (or reference) that you are following must have the explanation for such question. In general, no modification is made to the previous structure (i.e., the previous positions of the nodes )of a BST when a node is added. However, this can lead to "unbalanced" or "skewed" trees. This can lead to longer search times for a node. To remedy this problem, "balanced trees" such as red-black tree, avl trees etc. are used. In such trees, a modification to the tree structure is usually reuired when a node is added. Refer the following for more information:

https://en.wikipedia.org/wiki/Binary_search_tree?oldformat=true

https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree?oldformat=true