# 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:

![](https://2254094223-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M66b4KsHxRGUQlYomYk%2Fsync%2Fbf10d572c4cb721fb4a7ba0ffeeccee4fe0fa8cb.png?generation=1588191938335815\&alt=media)

Insert 2: 2 is < 4 so it goes left

![](https://2254094223-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M66b4KsHxRGUQlYomYk%2Fsync%2Fed8a044d332b47a17eb4c742b9e83c386de486b4.png?generation=1588191938791866\&alt=media)

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

![](https://2254094223-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M66b4KsHxRGUQlYomYk%2Fsync%2F97d023fe3ef06a0b36fc925aa7a596bc1075b997.png?generation=1588191938476420\&alt=media)

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

![](https://2254094223-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M66b4KsHxRGUQlYomYk%2Fsync%2Fd7e4b21e414f804e0da7ee25deef6e65d41b1e45.png?generation=1588191938605320\&alt=media)

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

![](https://2254094223-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M66b4KsHxRGUQlYomYk%2Fsync%2F6a0b5df7bd605966589a82f0af8f2c96d575058e.png?generation=1588191938765597\&alt=media)

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

![](https://2254094223-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M66b4KsHxRGUQlYomYk%2Fsync%2Fa4011bb9d967004b9547d4a3f00de5e06f57e189.png?generation=1588191938436200\&alt=media)