CODEWITHSUNDEEP
javaalgorithmsearchdata-structuresbinary-search-tree
DaBulls33
DaBulls33

Reputation: 171

Inserting in a Binary search tree issues

I am getting confused on my binary search algorithm. I have to insert the following integers into an empty binary tree in the given order using put(): 4,1,3,5,2. Im not 100 percent sure if I went about the right way in doing this. Here is what I did.. My main part of confusion came up when I had to insert the 2. I just want to make sure I am doing this correctly. Thanks all.

       4
      / \
     1   5
    /\   
      3
      /
     2

Upvotes: 1

Views: 90

Answers (1)

Josh Engelsma
Josh Engelsma

Reputation: 2646

You are spot on, 2 < 4 and 2 > 1 and finally 2 < 3

The Rules for Binary Search Tree Insertion are as follows:

If the key to insert is smaller than the current value, insert the key into the current values left subtree.

If the key to insert is larger than the current value, insert the key into the current values right subtree.

If the key is a duplicate value you will not insert.

It may seem to you that your answer is wrong because you may think it looks weird to you as a human to have 2 as a child of 3. Dont worry about that oddity. Just trust the algorithm, follow the rules all the time, and your insertion will work.

I am posting a link you should take a look at. It gives an excellent visualization of many data structures, and will help you if you run into a problem like this again. The site allows you to build your own binary search tree in whatever order you would like to insert.

As a side note: The site also offers many other data structure visualizations should you have a similar question on a different data structure in the future.

Binary Search Tree Visualization

Upvotes: 2

Related Questions