Binary Trees

Overview

A binary tree consists of nodes connected by edges, where each node contains data and references to at most two child nodes, designated as left and right. The topmost node serves as the root, and nodes without children are leaves. This structure provides logarithmic time complexity for many operations when balanced, making binary trees fundamental to algorithm design and data organization.

Binary trees originated from mathematical graph theory and became central to computer science in the 1960s with the development of binary search trees. The structure maps naturally to hierarchical relationships and enables divide-and-conquer algorithms that split problems into left and right subtrees.

The basic binary tree node contains three elements: a data value, a reference to the left child, and a reference to the right child. Null references indicate the absence of a child. This simple structure supports various tree types through different insertion and balancing rules.

class TreeNode
  attr_accessor :value, :left, :right
  
  def initialize(value)
    @value = value
    @left = nil
    @right = nil
  end
end

# Creating a simple binary tree
root = TreeNode.new(10)
root.left = TreeNode.new(5)
root.right = TreeNode.new(15)
root.left.left = TreeNode.new(3)
root.left.right = TreeNode.new(7)
# => Tree structure:
#        10
#       /  \
#      5    15
#     / \
#    3   7

Binary trees serve as the foundation for more specialized structures including binary search trees, heaps, expression trees, and Huffman coding trees. Each variant applies specific ordering or structural properties to optimize particular operations.

Key Principles

Node Structure: Each node stores data and maintains references to left and right children. The absence of a child is represented by nil. This uniform structure enables recursive algorithms that process nodes identically regardless of their position in the tree.

Tree Traversal: Three standard depth-first traversal orders exist. Inorder traversal visits the left subtree, then the node, then the right subtree. Preorder traversal visits the node before its subtrees. Postorder traversal visits the node after its subtrees. Breadth-first traversal processes nodes level by level.

# Inorder: left, root, right
def inorder(node, result = [])
  return result if node.nil?
  inorder(node.left, result)
  result << node.value
  inorder(node.right, result)
  result
end
# => [3, 5, 7, 10, 15]

# Preorder: root, left, right
def preorder(node, result = [])
  return result if node.nil?
  result << node.value
  preorder(node.left, result)
  preorder(node.right, result)
  result
end
# => [10, 5, 3, 7, 15]

# Postorder: left, right, root
def postorder(node, result = [])
  return result if node.nil?
  postorder(node.left, result)
  postorder(node.right, result)
  result << node.value
  result
end
# => [3, 7, 5, 15, 10]

Height and Depth: Tree height measures the longest path from root to leaf. Node depth measures distance from the root. A balanced tree maintains height proportional to log(n) where n is the node count. Height directly impacts operation time complexity.

Complete and Full Trees: A complete binary tree fills all levels except possibly the last, which fills left to right. A full binary tree has nodes with either zero or two children. These properties enable array-based implementations and predict performance characteristics.

Binary Search Property: Binary search trees maintain the invariant that left children contain smaller values and right children contain larger values. This property enables O(log n) search in balanced trees through binary search logic.

Ruby Implementation

Ruby does not provide built-in binary tree classes, requiring custom implementation. The node-based approach using classes and instance variables provides clarity and matches object-oriented design principles.

class BinaryTree
  attr_reader :root
  
  def initialize
    @root = nil
  end
  
  def insert(value)
    @root = insert_recursive(@root, value)
  end
  
  private
  
  def insert_recursive(node, value)
    return TreeNode.new(value) if node.nil?
    
    if value < node.value
      node.left = insert_recursive(node.left, value)
    else
      node.right = insert_recursive(node.right, value)
    end
    
    node
  end
end

tree = BinaryTree.new
[10, 5, 15, 3, 7, 12, 17].each { |val| tree.insert(val) }

Search Implementation: Binary search trees support efficient lookup by comparing the target value with the current node and recursing left or right.

class BinaryTree
  def search(value)
    search_recursive(@root, value)
  end
  
  private
  
  def search_recursive(node, value)
    return nil if node.nil?
    return node if node.value == value
    
    if value < node.value
      search_recursive(node.left, value)
    else
      search_recursive(node.right, value)
    end
  end
end

tree.search(7)  # => TreeNode with value 7
tree.search(20) # => nil

Deletion Handling: Node deletion requires handling three cases: nodes with no children, one child, or two children. The two-child case replaces the node with its inorder successor.

class BinaryTree
  def delete(value)
    @root = delete_recursive(@root, value)
  end
  
  private
  
  def delete_recursive(node, value)
    return nil if node.nil?
    
    if value < node.value
      node.left = delete_recursive(node.left, value)
    elsif value > node.value
      node.right = delete_recursive(node.right, value)
    else
      # Node found
      return node.right if node.left.nil?
      return node.left if node.right.nil?
      
      # Two children: get inorder successor
      min_node = find_min(node.right)
      node.value = min_node.value
      node.right = delete_recursive(node.right, min_node.value)
    end
    
    node
  end
  
  def find_min(node)
    node = node.left while node.left
    node
  end
end

Level Order Traversal: Breadth-first traversal uses a queue to process nodes level by level, requiring iterative implementation.

def level_order(root)
  return [] if root.nil?
  
  result = []
  queue = [root]
  
  until queue.empty?
    node = queue.shift
    result << node.value
    
    queue << node.left if node.left
    queue << node.right if node.right
  end
  
  result
end
# => [10, 5, 15, 3, 7, 12, 17]

Tree Properties: Computing height, size, and balance information requires recursive traversal.

def height(node)
  return -1 if node.nil?
  1 + [height(node.left), height(node.right)].max
end

def size(node)
  return 0 if node.nil?
  1 + size(node.left) + size(node.right)
end

def balanced?(node)
  return true if node.nil?
  
  left_height = height(node.left)
  right_height = height(node.right)
  
  (left_height - right_height).abs <= 1 &&
    balanced?(node.left) &&
    balanced?(node.right)
end

Path Operations: Finding paths and checking for path sums requires tracking state during traversal.

def find_path(node, target, path = [])
  return nil if node.nil?
  
  path << node.value
  return path if node.value == target
  
  left_result = find_path(node.left, target, path.dup)
  return left_result if left_result
  
  find_path(node.right, target, path.dup)
end

def has_path_sum?(node, sum)
  return false if node.nil?
  return sum == node.value if node.left.nil? && node.right.nil?
  
  remaining = sum - node.value
  has_path_sum?(node.left, remaining) || has_path_sum?(node.right, remaining)
end

Implementation Approaches

Binary Search Tree (BST): Maintains sorted order with left children smaller and right children larger than the parent. Supports O(log n) operations when balanced but degrades to O(n) when skewed.

class BST
  def insert(value)
    @root = insert_node(@root, value)
  end
  
  def find_range(min, max, result = [])
    range_search(@root, min, max, result)
    result
  end
  
  private
  
  def range_search(node, min, max, result)
    return if node.nil?
    
    range_search(node.left, min, max, result) if node.value > min
    result << node.value if node.value >= min && node.value <= max
    range_search(node.right, min, max, result) if node.value < max
  end
end

AVL Tree: Self-balancing BST that maintains height difference of at most one between subtrees through rotation operations. Guarantees O(log n) operations with higher insertion overhead.

class AVLNode
  attr_accessor :value, :left, :right, :height
  
  def initialize(value)
    @value = value
    @left = nil
    @right = nil
    @height = 1
  end
end

class AVLTree
  def insert(value)
    @root = insert_with_balance(@root, value)
  end
  
  private
  
  def insert_with_balance(node, value)
    return AVLNode.new(value) if node.nil?
    
    if value < node.value
      node.left = insert_with_balance(node.left, value)
    else
      node.right = insert_with_balance(node.right, value)
    end
    
    node.height = 1 + [get_height(node.left), get_height(node.right)].max
    balance = get_balance(node)
    
    # Left-Left case
    if balance > 1 && value < node.left.value
      return rotate_right(node)
    end
    
    # Right-Right case
    if balance < -1 && value > node.right.value
      return rotate_left(node)
    end
    
    # Left-Right case
    if balance > 1 && value > node.left.value
      node.left = rotate_left(node.left)
      return rotate_right(node)
    end
    
    # Right-Left case
    if balance < -1 && value < node.right.value
      node.right = rotate_right(node.right)
      return rotate_left(node)
    end
    
    node
  end
  
  def rotate_left(z)
    y = z.right
    t2 = y.left
    
    y.left = z
    z.right = t2
    
    z.height = 1 + [get_height(z.left), get_height(z.right)].max
    y.height = 1 + [get_height(y.left), get_height(y.right)].max
    
    y
  end
  
  def rotate_right(z)
    y = z.left
    t3 = y.right
    
    y.right = z
    z.left = t3
    
    z.height = 1 + [get_height(z.left), get_height(z.right)].max
    y.height = 1 + [get_height(y.left), get_height(y.right)].max
    
    y
  end
  
  def get_height(node)
    node.nil? ? 0 : node.height
  end
  
  def get_balance(node)
    node.nil? ? 0 : get_height(node.left) - get_height(node.right)
  end
end

Heap Structure: Complete binary tree maintaining heap property where parent nodes are smaller (min-heap) or larger (max-heap) than children. Supports O(log n) insertion and O(1) minimum/maximum access.

class MinHeap
  def initialize
    @heap = []
  end
  
  def insert(value)
    @heap << value
    bubble_up(@heap.length - 1)
  end
  
  def extract_min
    return nil if @heap.empty?
    
    min = @heap[0]
    @heap[0] = @heap.pop
    bubble_down(0) unless @heap.empty?
    min
  end
  
  private
  
  def bubble_up(index)
    return if index == 0
    
    parent_index = (index - 1) / 2
    if @heap[index] < @heap[parent_index]
      @heap[index], @heap[parent_index] = @heap[parent_index], @heap[index]
      bubble_up(parent_index)
    end
  end
  
  def bubble_down(index)
    left = 2 * index + 1
    right = 2 * index + 2
    smallest = index
    
    smallest = left if left < @heap.length && @heap[left] < @heap[smallest]
    smallest = right if right < @heap.length && @heap[right] < @heap[smallest]
    
    if smallest != index
      @heap[index], @heap[smallest] = @heap[smallest], @heap[index]
      bubble_down(smallest)
    end
  end
end

Trie (Prefix Tree): Tree where each node represents a character and paths from root to nodes form strings. Optimizes prefix matching and autocomplete operations.

class TrieNode
  attr_accessor :children, :is_end_of_word
  
  def initialize
    @children = {}
    @is_end_of_word = false
  end
end

class Trie
  def initialize
    @root = TrieNode.new
  end
  
  def insert(word)
    node = @root
    word.each_char do |char|
      node.children[char] ||= TrieNode.new
      node = node.children[char]
    end
    node.is_end_of_word = true
  end
  
  def search(word)
    node = find_node(word)
    node && node.is_end_of_word
  end
  
  def starts_with?(prefix)
    !find_node(prefix).nil?
  end
  
  private
  
  def find_node(prefix)
    node = @root
    prefix.each_char do |char|
      return nil unless node.children[char]
      node = node.children[char]
    end
    node
  end
end

Practical Examples

Expression Tree Evaluation: Binary trees represent arithmetic expressions where internal nodes store operators and leaves store operands. Postorder traversal evaluates the expression.

class ExpressionNode
  attr_accessor :value, :left, :right
  
  def initialize(value, left = nil, right = nil)
    @value = value
    @left = left
    @right = right
  end
  
  def operator?
    ['+', '-', '*', '/'].include?(@value)
  end
end

def evaluate_expression(node)
  return node.value.to_f unless node.operator?
  
  left_val = evaluate_expression(node.left)
  right_val = evaluate_expression(node.right)
  
  case node.value
  when '+' then left_val + right_val
  when '-' then left_val - right_val
  when '*' then left_val * right_val
  when '/' then left_val / right_val
  end
end

# Build tree for: (5 + 3) * (8 - 2)
root = ExpressionNode.new('*')
root.left = ExpressionNode.new('+', 
  ExpressionNode.new(5), 
  ExpressionNode.new(3))
root.right = ExpressionNode.new('-', 
  ExpressionNode.new(8), 
  ExpressionNode.new(2))

evaluate_expression(root)
# => 48.0

File System Representation: Hierarchical directory structures map naturally to binary trees where each node represents a file or directory.

class FileNode
  attr_accessor :name, :is_directory, :size, :left, :right
  
  def initialize(name, is_directory: false, size: 0)
    @name = name
    @is_directory = is_directory
    @size = size
    @left = nil
    @right = nil
  end
end

def calculate_total_size(node)
  return 0 if node.nil?
  return node.size unless node.is_directory
  
  node.size + calculate_total_size(node.left) + calculate_total_size(node.right)
end

def find_files_by_extension(node, extension, results = [])
  return results if node.nil?
  
  results << node.name if node.name.end_with?(extension)
  find_files_by_extension(node.left, extension, results)
  find_files_by_extension(node.right, extension, results)
  results
end

# Directory structure
root = FileNode.new('root', is_directory: true)
root.left = FileNode.new('docs', is_directory: true)
root.left.left = FileNode.new('readme.md', size: 1024)
root.left.right = FileNode.new('guide.md', size: 2048)
root.right = FileNode.new('config.yml', size: 512)

Lowest Common Ancestor: Finding the lowest common ancestor of two nodes requires tracking paths or using parent pointers.

def lowest_common_ancestor(root, p, q)
  return nil if root.nil?
  return root if root.value == p || root.value == q
  
  left = lowest_common_ancestor(root.left, p, q)
  right = lowest_common_ancestor(root.right, p, q)
  
  return root if left && right
  left || right
end

# For BST, more efficient approach using value ordering
def lca_bst(root, p, q)
  return nil if root.nil?
  
  if p < root.value && q < root.value
    lca_bst(root.left, p, q)
  elsif p > root.value && q > root.value
    lca_bst(root.right, p, q)
  else
    root
  end
end

Tree Serialization: Converting trees to and from string format enables storage and transmission.

def serialize(node)
  return 'null' if node.nil?
  "#{node.value},#{serialize(node.left)},#{serialize(node.right)}"
end

def deserialize(data)
  values = data.split(',')
  index = 0
  
  build_tree = lambda do
    return nil if index >= values.length || values[index] == 'null'
    
    node = TreeNode.new(values[index].to_i)
    index += 1
    node.left = build_tree.call
    node.right = build_tree.call
    node
  end
  
  build_tree.call
end

tree = TreeNode.new(1, TreeNode.new(2), TreeNode.new(3))
serialized = serialize(tree)
# => "1,2,null,null,3,null,null"
restored = deserialize(serialized)

Common Patterns

Recursive Traversal Pattern: Most tree operations follow the pattern of processing a node and recursing on children. Base case checks for nil, recursive case processes subtrees.

def process_tree(node)
  return base_case_value if node.nil?
  
  # Process current node
  current_result = process_node(node)
  
  # Recurse on children
  left_result = process_tree(node.left)
  right_result = process_tree(node.right)
  
  # Combine results
  combine(current_result, left_result, right_result)
end

# Example: Sum all values
def sum_tree(node)
  return 0 if node.nil?
  node.value + sum_tree(node.left) + sum_tree(node.right)
end

# Example: Count nodes
def count_nodes(node)
  return 0 if node.nil?
  1 + count_nodes(node.left) + count_nodes(node.right)
end

Iterative Traversal with Stack: Stack-based traversal avoids recursion limits and provides explicit control over traversal order.

def iterative_inorder(root)
  result = []
  stack = []
  current = root
  
  while current || !stack.empty?
    while current
      stack << current
      current = current.left
    end
    
    current = stack.pop
    result << current.value
    current = current.right
  end
  
  result
end

def iterative_preorder(root)
  return [] if root.nil?
  
  result = []
  stack = [root]
  
  until stack.empty?
    node = stack.pop
    result << node.value
    
    stack << node.right if node.right
    stack << node.left if node.left
  end
  
  result
end

Level-by-Level Processing: Processing nodes level by level requires tracking level boundaries in the queue.

def level_order_groups(root)
  return [] if root.nil?
  
  result = []
  queue = [root]
  
  until queue.empty?
    level_size = queue.length
    current_level = []
    
    level_size.times do
      node = queue.shift
      current_level << node.value
      
      queue << node.left if node.left
      queue << node.right if node.right
    end
    
    result << current_level
  end
  
  result
end
# => [[10], [5, 15], [3, 7, 12, 17]]

Parent Tracking: Maintaining parent references enables upward traversal and ancestor queries.

class NodeWithParent
  attr_accessor :value, :left, :right, :parent
  
  def initialize(value)
    @value = value
    @left = nil
    @right = nil
    @parent = nil
  end
end

def build_with_parents(node, parent = nil)
  return if node.nil?
  
  node.parent = parent
  build_with_parents(node.left, node)
  build_with_parents(node.right, node)
end

def find_path_to_root(node)
  path = []
  current = node
  
  while current
    path << current.value
    current = current.parent
  end
  
  path
end

Mirror/Inversion Pattern: Creating mirror images or checking for symmetry involves swapping left and right subtrees.

def mirror_tree(node)
  return nil if node.nil?
  
  left = mirror_tree(node.left)
  right = mirror_tree(node.right)
  
  node.left = right
  node.right = left
  node
end

def is_symmetric?(root)
  return true if root.nil?
  check_symmetry(root.left, root.right)
end

def check_symmetry(left, right)
  return true if left.nil? && right.nil?
  return false if left.nil? || right.nil?
  
  left.value == right.value &&
    check_symmetry(left.left, right.right) &&
    check_symmetry(left.right, right.left)
end

Performance Considerations

Time Complexity Analysis: Balanced binary search trees provide O(log n) search, insertion, and deletion. Unbalanced trees degrade to O(n) for these operations. Tree height determines performance, with height h yielding O(h) operations.

Complete binary trees maintain height floor(log n), ensuring logarithmic performance. Skewed trees have height n-1, reducing to linear time. Self-balancing trees like AVL and Red-Black trees guarantee O(log n) height through rotation operations.

Space Complexity: Recursive traversal uses O(h) stack space where h is tree height. Balanced trees use O(log n) space for recursion, while skewed trees use O(n). Iterative implementations with explicit stacks have the same space requirements.

# Stack space demonstration
def max_depth_space(node, depth = 0)
  return depth if node.nil?
  
  left_depth = max_depth_space(node.left, depth + 1)
  right_depth = max_depth_space(node.right, depth + 1)
  
  [left_depth, right_depth].max
end

# Iterative version uses explicit stack
def max_depth_iterative(root)
  return 0 if root.nil?
  
  max = 0
  stack = [[root, 1]]
  
  until stack.empty?
    node, depth = stack.pop
    max = depth if depth > max
    
    stack << [node.left, depth + 1] if node.left
    stack << [node.right, depth + 1] if node.right
  end
  
  max
end

Cache Locality: Array-based heap implementations provide better cache performance than pointer-based trees due to contiguous memory layout. Node-based trees suffer from pointer chasing and cache misses.

# Array-based complete binary tree (heap)
class ArrayHeap
  def initialize
    @array = []
  end
  
  def parent_index(i)
    (i - 1) / 2
  end
  
  def left_child_index(i)
    2 * i + 1
  end
  
  def right_child_index(i)
    2 * i + 2
  end
  
  # Better cache locality than pointer-based tree
  # Sequential array access vs random memory jumps
end

Balancing Overhead: Self-balancing trees trade insertion speed for guaranteed search performance. AVL trees perform more rotations than Red-Black trees but maintain stricter balance. Choose based on operation frequency.

# AVL: Stricter balance (faster searches, slower insertions)
# Height difference <= 1
# 1-2 rotations per insertion

# Red-Black: Relaxed balance (faster insertions, slightly slower searches)
# Black height property
# 0-3 rotations per insertion

Batch Operations: Building balanced trees from sorted data uses O(n) time through divide-and-conquer construction instead of n O(log n) insertions.

def sorted_array_to_bst(arr, start = 0, finish = arr.length - 1)
  return nil if start > finish
  
  mid = (start + finish) / 2
  node = TreeNode.new(arr[mid])
  
  node.left = sorted_array_to_bst(arr, start, mid - 1)
  node.right = sorted_array_to_bst(arr, mid + 1, finish)
  
  node
end

# O(n) construction vs O(n log n) sequential insertion
sorted = [1, 2, 3, 4, 5, 6, 7]
tree = sorted_array_to_bst(sorted)

Memory Overhead: Each node requires memory for data, left pointer, right pointer, and potential metadata (height, color, parent). Structure overhead can exceed data size for small values.

# Node memory breakdown
class TreeNode
  attr_accessor :value        # 8 bytes (reference)
  attr_accessor :left         # 8 bytes (reference)
  attr_accessor :right        # 8 bytes (reference)
  # Ruby object overhead: ~40 bytes
  # Total: ~64 bytes per node minimum
end

# For storing integers, overhead >> data size
# Consider packed arrays for small, complete trees

Common Pitfalls

Off-by-One Errors in Height Calculation: Tree height definitions vary between maximum edge count and maximum node count. Consistently choose one definition.

# Edge-based height (leaf = 0)
def height_edges(node)
  return -1 if node.nil?  # Empty tree has height -1
  1 + [height_edges(node.left), height_edges(node.right)].max
end

# Node-based height (leaf = 1)
def height_nodes(node)
  return 0 if node.nil?   # Empty tree has height 0
  1 + [height_nodes(node.left), height_nodes(node.right)].max
end

Forgetting Nil Checks: Every recursive call must check for nil nodes before dereferencing. Missing checks cause NoMethodError exceptions.

# Wrong: crashes on nil
def count_wrong(node)
  1 + count_wrong(node.left) + count_wrong(node.right)
end

# Correct: checks nil first
def count_correct(node)
  return 0 if node.nil?
  1 + count_correct(node.left) + count_correct(node.right)
end

Modifying Tree During Iteration: Inserting or deleting nodes while traversing breaks iteration logic. Collect modifications and apply after traversal completes.

# Wrong: modifying during traversal
def double_values_wrong(node)
  return if node.nil?
  node.value *= 2
  insert(node.value)  # Breaks traversal
  double_values_wrong(node.left)
  double_values_wrong(node.right)
end

# Correct: collect then modify
def double_values_correct(node, values = [])
  return values if node.nil?
  values << node.value
  double_values_correct(node.left, values)
  double_values_correct(node.right, values)
  values
end

values = double_values_correct(root)
values.each { |v| insert(v * 2) }

Incorrect BST Invariant Validation: Checking only immediate children misses violations deeper in the tree. Track valid range during recursion.

# Wrong: only checks immediate children
def valid_bst_wrong?(node)
  return true if node.nil?
  return false if node.left && node.left.value >= node.value
  return false if node.right && node.right.value <= node.value
  valid_bst_wrong?(node.left) && valid_bst_wrong?(node.right)
end

# Correct: tracks valid range
def valid_bst?(node, min = -Float::INFINITY, max = Float::INFINITY)
  return true if node.nil?
  return false if node.value <= min || node.value >= max
  
  valid_bst?(node.left, min, node.value) &&
    valid_bst?(node.right, node.value, max)
end

Memory Leaks from Circular References: Parent pointers create cycles that prevent garbage collection in languages without automatic cycle detection. Break references explicitly.

def delete_subtree(node)
  return if node.nil?
  
  delete_subtree(node.left)
  delete_subtree(node.right)
  
  # Break references to enable GC
  node.left = nil
  node.right = nil
  node.parent = nil if node.respond_to?(:parent)
end

Stack Overflow from Deep Recursion: Ruby's default stack size limits recursion depth to around 10,000 levels. Convert to iteration for very deep trees.

# Recursive: hits stack limit
def sum_recursive(node)
  return 0 if node.nil?
  node.value + sum_recursive(node.left) + sum_recursive(node.right)
end

# Iterative: handles arbitrary depth
def sum_iterative(root)
  return 0 if root.nil?
  
  sum = 0
  stack = [root]
  
  until stack.empty?
    node = stack.pop
    sum += node.value
    stack << node.left if node.left
    stack << node.right if node.right
  end
  
  sum
end

Confusing Tree Types: Binary trees, BSTs, balanced trees, and heaps have different properties and operations. Applying BST search logic to unordered binary trees produces incorrect results.

# BST search (requires ordering)
def bst_search(node, target)
  return nil if node.nil?
  return node if node.value == target
  
  if target < node.value
    bst_search(node.left, target)
  else
    bst_search(node.right, target)
  end
end

# General tree search (no ordering assumption)
def tree_search(node, target)
  return nil if node.nil?
  return node if node.value == target
  
  tree_search(node.left, target) || tree_search(node.right, target)
end

Reference

Node Structure

Traversal Methods

Tree Properties

Common Tree Types

Operation Complexity

Rotation Operations

Ruby Implementation Patterns

Common Validation Checks