Trees

BST Insert

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

Algorithm

Basic Implementation

basic.go 
package main

import (
    "fmt"
    "strings"
)

type Node struct { value int; left *Node; right *Node }
func render(node *Node) string {
    if node == nil { return "_" }
    if node.left == nil && node.right == nil { return fmt.Sprintf("%d", node.value) }
    return fmt.Sprintf("%d(%s,%s)", node.value, render(node.left), render(node.right))
}
func sampleTree() *Node {
    return &Node{4, &Node{2, &Node{1, nil, nil}, &Node{3, nil, nil}}, &Node{6, &Node{5, nil, nil}, &Node{7, nil, nil}}}
}
func listString(values []int) string {
    parts := []string{}
    for _, value := range values { parts = append(parts, fmt.Sprintf("%d", value)) }
    return "[" + strings.Join(parts, ", ") + "]"
}
func insert(root *Node, value int) *Node { if root == nil { return &Node{value: value} }; if value < root.value { root.left = insert(root.left, value) } else { root.right = insert(root.right, value) }; return root }
func main() { var root *Node; for _, value := range []int{4, 2, 6, 1, 3, 5, 7} { root = insert(root, value) }; fmt.Println(render(root)) }

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

  • Go models each tree entry as type Node struct { value int; left *Node; right *Node }, so child links are nullable pointers.
  • insert(root *Node, value int) *Node is recursive. A nil root allocates a new node with &Node{value: value}; otherwise the function assigns the returned pointer into root.left or root.right.
  • main starts with var root *Node and reassigns root = insert(root, value) for each value in []int{4, 2, 6, 1, 3, 5, 7}, allowing the first insert to replace the nil root.
  • The branch uses value < root.value; equal values would follow the else path into the right subtree, though this replay has no duplicates.
  • The trace records paths and tree states after each insert: 4, 4(2,_), 4(2,6), 4(2(1,_),6), 4(2(1,3),6), 4(2(1,3),6(5,_)), then 4(2(1,3),6(5,7)).
  • render prints _ for nil children and value(left,right) for interior nodes; fmt.Println(render(root)) emits 4(2(1,3),6(5,7)).
  • The replay also includes a sorted-insert contrast, 1(_,2(_,3(_,4))), showing the Go pointer version still degrades without rotations.
binary search tree Values smaller than a node go left; larger values go right.