BST Successor Search

bst-in-order-search.rb

# In a Binary Search Tree (BST), 
# an Inorder Successor of a node is defined as the node with the smallest key greater than the key of the input node. 
# Given a node inputNode in a BST, 
# you’re asked to write a function findInOrderSuccessor that returns the Inorder Successor of inputNode. 
# If inputNode has no Inorder Successor, return null.

class Node
  attr_reader :value
  attr_accessor :left, :right

  def initialize(value)
    @value = value
  end
end

def insertNode(root, val)
  pointer = root
  newNode = Node.new(val)
  # p val
  found = false
  while (!found)
    if val>pointer.value
      if pointer.right == nil
        pointer.right = newNode
        found = true
      else
        pointer = pointer.right
      end
    else
      if pointer.left == nil
        pointer.left = newNode
        found = true
      else
        pointer = pointer.left
      end
    end
  end
end

def createBST(arr)
  root = Node.new(arr.shift)
  arr.each{|val|
    insertNode(root, val)  
  }
  return root
end

def findInOrderSuccessor(root, value)
  parent = root;

  # track the parent while going left
  # find the node
  while (root.value != value)
    if value < root.value
      parent = root
      root = root.left
    else
      root = root.right
    end
  end
  
  # if right is empty return the parent otherwise 
  # find the the leaf at the utmost left of the first right
  if root.right == nil
    return parent.value
  else
    root = root.right
    while (root.left != nil)
      root = root.left
    end
    return root.value
  end
end

# Create the BST and the root
root = createBST([4,2,7,1,6,89,13,67,11,82,33,52,123,78,23,5])
# p root 
# p root.left, root.right
p findInOrderSuccessor(root, 7)