Binary Search Tree

gistfile1.rb

class Node
  attr_accessor :left, :right, :parent, :key
  def initialize(key)
    @parent = @left = @right = nil
    @key = key
  end
end

class BST

  attr_accessor :root

  def initialize(key)
    @root = Node.new(key)
  end

  def insert(key)
    z = Node.new(key)
    y = nil
    x = @root 

    until x.nil?
      y = x # maintain the trailer
      if z.key > x.key
        x = x.right
      else
        x = x.left
      end
    end

    z.parent = y # Set parent.

    if y.nil?  # The table was empty
      @root = z
    elsif z.key > y.key
      y.right = z 
    else
      y.left = z 
    end 

    z
  end

  def successor(key)
    x = search(key)

    unless x.nil? || x.right.nil?
      return min(x.right)
    end

    y = x.parent
    while y != nil && y.right == x
      x = y
      y = y.parent
    end 

    y
  end

  def inorder_traversal(x=@root)
    unless x.nil?
      inorder_traversal(x.left)
      puts x.key
      inorder_traversal(x.right)
    end
  end

  def search(key)
    x = @root

    until x.nil? || x.key == key
      if key > x.key
        x = x.right
      else
        x = x.left
      end
    end 
    x
  end

  def min(x=@root)
    until x.left.nil?
      x = x.left
    end
    x
  end

  def max(x=@root)
    until x.right.nil?
      x = x.right
    end 
    x 
  end

  def depth(x=@root)
    return 0 if x.nil?

    left_height = depth(x.left)
    right_height = depth(x.right)

    [left_height, right_height].max + 1
  end


end