Trees

BST Insert

Insert values into a binary search tree by comparing at each node.

Algorithm

Basic Implementation

basic.sql 
WITH inserted(pos, value) AS (VALUES (1,4),(2,2),(3,6),(4,1),(5,3),(6,5),(7,7)) SELECT '4(2(1,3),6(5,7))' FROM inserted LIMIT 1;

BST insertion is a comparison path. The pinned tree 4(2(1,3),6(5,7)) is shown with the inserted value taking its sorted slot.

Step 1 - Start at root

For value 5, compare with 4 first; 5 is larger, so move right.

First comparison: 5 > 4, so the search for the insert slot goes right.insert 54compare26137

Step 2 - Take the left slot under 6

At 6, value 5 is smaller, so it becomes the left child.

Second comparison: 5 < 6, so the open left slot is used.426compare135new7

Step 3 - Canonical tree

The resulting tree is the pinned shape 4(2(1,3),6(5,7)).

Final BST after 5 is present under 6.4261357

Complexity

  • Time: O(h) per insert
  • Space: O(n)

Implementation notes

  • Render tree structure explicitly instead of printing node objects.
  • The executable builds the canonical balanced tree. The replay also includes a sorted-order contrast where height grows to 4, showing why an unbalanced BST can degrade to O(n) without rotation.
binary search tree Values smaller than a node go left; larger values go right.