Basic Data Structures in Ruby - Binary Search Tre

Creating A Binary Search Tree in Ruby

A detailed, general tutorial on the binary tree data structure ( with a C Program ) is available here : Binary Search Trees - Tutorial with C Program Source Code and Documentation.

Over here, we take a quick look at a Ruby program to construct and traverse through a Binary Tree. Hopefully the documentation and the comments will enable you to figure out the important ideas involved over here.

# Example of Self-Referential Data Structures - A Binary Tree

class TreeNode
attr_accessor :value, :left, :right

  # The Tree node contains a value, and a pointer to two children - left and right
  # Values lesser than this node will be inserted on its left
  # Values greater than it will be inserted on its right
  def initialize val,left,right
  @value = val
  @left = left
  @right = right
  end
end

class BinarySearchTree

  # Initialize the Root Node
  def initialize val
  puts "Initializing with: " + val.to_s
  @root = TreeNode.new(val,nil,nil)
  end

  # Pre-Order Traversal
  def preOrderTraversal(node= @root)
  return if (node == nil)
preOrderTraversal(node.left)
preOrderTraversal(node.right)
  puts node.value.to_s
  end

  # Post-Order Traversal
  def postOrderTraversal(node = @root)
  return if (node == nil)
  puts node.value.to_s
postOrderTraversal(node.left)
postOrderTraversal(node.right)
  end

  # In-Order Traversal : Displays the final output in sorted order
  # Display smaller children first (by going left)
  # Then display the value in the current node
  # Then display the larger children on the right
  def inOrderTraversal(node = @root)
  return if (node == nil)
inOrderTraversal(node.left)
  puts node.value.to_s
inOrderTraversal(node.right)
  end

  # Inserting a value
  # When value > current node, go towards the right
  # when value < current node, go towards the left
  # when you hit a nil node, it means, the new node should be created there
  # Duplicate values are not inserted in the tree
  def insert(value)
  puts "Inserting :" + value.to_s
current_node = @root
  while nil != current_node
  if (value < current_node.value) && (current_node.left == nil)
current_node.left = TreeNode.new(value,nil,nil)
  elsif  (value > current_node.value) && (current_node.right == nil)
current_node.right = TreeNode.new(value,nil,nil)
  elsif (value < current_node.value)
current_node = current_node.left
  elsif (value > current_node.value)
current_node = current_node.right
  else
  return
  end
  end
  end
end

bst = BinarySearchTree.new(10)
bst.insert(11)
bst.insert(9)
bst.insert(5)
bst.insert(7)
bst.insert(18)
bst.insert(17)
# Demonstrating Different Kinds of Traversals
puts "In-Order Traversal:"
bst.inOrderTraversal
puts "Pre-Order Traversal:"
bst.preOrderTraversal
puts "Post-Order Traversal:"
bst.postOrderTraversal

=begin

Output :
Initializing with: 10
Inserting :11
Inserting :9
Inserting :5
Inserting :7
Inserting :18
Inserting :17
In-Order Traversal:
5
7
9
10
11
17
18
Pre-Order Traversal:
7
5
9
17
18
11
10
Post-Order Traversal:
10
9
5
7
11
18
17

=end

Check out some of our other Ruby Tutorials :

Introduction to Ruby

Introduction to Ruby and some playing around with the Interactive Ruby Shell (irb) Introduction to Ruby - Conditional statements and Modifiers: If-then, Unless, Case Introduction to Ruby Comments - Single and Multi-Line comments Introduction to Ruby Loops - Using While, Until, For, Break, Next , Redo, Retry
Introduction to Ruby - Arrays - Sorting, Filtering (Select), Transforming, Multi-Dimensional Arrays Introduction to Ruby - Strings Introduction to Ruby - Making a Script Executable Introduction to Ruby - Regular Expressions, Match, Scan
Introduction to Ruby - Computing Factorials Recursively : An Example of Recursion Introduction to Ruby - Binomial Coefficients (nCr) : An Example of Recursion Introduction to Ruby - Computing a Power Set : An Example of Recursion Introduction to Ruby - Towers of Hanoi : An Example of Recursion
Introduction to Ruby - Strings: Substitution, Encoding, Built-In Methods

Basic Data Structures With Ruby

Basic Data Structures in Ruby - Insertion Sort Basic Data Structures in Ruby - Selection Sort Basic Data Structures in Ruby - Merge Sort Basic Data Structures in Ruby - Quick Sort Functional Programming with Ruby
Basic Data Structures in Ruby - Stack Basic Data Structures in Ruby - The Queue Basic Data Structures in Ruby - Linked List - ( A Simple, Singly Linked List) Basic Data Structures in Ruby - Binary Search Tree