Trees

BST Insert

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

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this Ruby DSA implementation can be compared directly with the rest of the DSA track.

binary search tree Values smaller than a node go left; larger values go right.

Visual walkthrough

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

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)

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.