Trees

BST Insert

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

Algorithm

Basic Implementation

basic.rb 
class Node
  attr_accessor :value, :left, :right
  def initialize(value, left = nil, right = nil)
    @value = value
    @left = left
    @right = right
  end
end
def render(node)
  return "_" if node.nil?
  return node.value.to_s if node.left.nil? && node.right.nil?
  "#{node.value}(#{render(node.left)},#{render(node.right)})"
end
def sample_tree
  Node.new(4, Node.new(2, Node.new(1), Node.new(3)), Node.new(6, Node.new(5), Node.new(7)))
end
def insert(root, value); return Node.new(value) if root.nil?; value < root.value ? root.left = insert(root.left, value) : root.right = insert(root.right, value); root; end
root = nil
[4, 2, 6, 1, 3, 5, 7].each { |value| root = insert(root, value) }
puts 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

  • Node is a Ruby class with attr_accessor :value, :left, :right, so child links are mutable object fields.
  • initialize(value, left = nil, right = nil) uses nil for empty children; there is no sentinel node.
  • insert(root, value) returns Node.new(value) when the current subtree root is nil.
  • Otherwise it compares value < root.value and recursively assigns either root.left = insert(root.left, value) or root.right = insert(root.right, value).
  • Equal values would take the right-side branch because the code uses a ternary with only the strict < case on the left.
  • The top-level root = insert(root, value) reassignment is what installs the first inserted node as the root.
  • The trace inserts 4, 2, 6, 1, 3, 5, 7, ending at 4(2(1,3),6(5,7)).
  • render prints nil links as _ and nested nodes as value(left,right).
  • The replay also includes sorted inserts [1, 2, 3, 4], producing 1(_,2(_,3(_,4))) with height 4 and O(n) unbalanced behavior.
binary search tree Values smaller than a node go left; larger values go right.