The pseudo-code shown below illustrates how TREE_INSERT works. The procedure starts at the root of the tree and traces a recursive path downward. The if statement at line 3 tests if the value to be inserted is less than the actual value in the node pointed by T. If this condition is true, the procedure calls itself recursively, but this time it passes the left subtree of T as a parameter. The reason for that follows straight from the Binary Search Tree property, which states that smaller values should always be left-descendents of their respective ancestors. Conversely, if value is greater than the value of T, it passes the right subtree of T as a parameter for the next recursive call in line 5. TREE_INSERT terminates after it finds a NIL child (a new leaf is always created as a result of this procedure) and it backtracks from its recursive calls, updating the tree structure.
TREE_INSERT (T, value) begin 1. if (T = NIL) then 2. T = alloc_node(NIL); 3. else if (val < T->value) then 4. TREE_INSERT (T->left, val); 5. else TREE_INSERT(T->right, val); 6. end.
