Insertion

To insert into a binary search tree, we must maintain the nodes in sorted order. There is only one place an item can go. Example Insert the numbers 4,2,3,5,1, and 6 in to an initially empty binary search tree in the order listed. Insertions always occur by inserting into the first available empty subtree along the search path for the value:

Insert 4:

Insert 2: 2 is < 4 so it goes left

Insert 3: 3 is less than 4 but more than 2 so it goes to left of 4, but right of 2

Insert 5: 5 is > 4 so it goes right of 4

Insert 1: 1 is < 4 so it goes to left of 4. 1 is also < 2 so it goes to left of 2

Insert 6: 6 is > 4 so it goes to right of 4. 6 is also > 5 so it goes to right of 5