BST Inorder Sucessor

October 18th, 2017

Getting back to blogging after a long time. Whatever be the reasons, just want to share a quick insight I had yesterday.

Finding an in-order successor to a BST node is a pretty popular problem. While trying to think of it, I realized I could create a more elegant solution than what I could find online. I don’t know if similar solutions exist but here is a ruby implementation anyway (explanation within the comments):

# let's quickly create a tree
class Node < Struct.new(:val, :left, :right); end
root = Node.new(4)
root.left = Node.new(2)
root.left.left = Node.new(1)
root.left.right = Node.new(3)
root.right = Node.new(6)
root.right.left = Node.new(5)
root.right.right = Node.new(7)

# finding min in a tree, simple to do
def find_min(node)
  return if node.nil?
  if node.left.nil?
    node
  else
    find_min(node.left)
  end
end

def find_successor(node, val, possible_successor = nil)
  return if node.nil?
  if val == node.val && node.right
  # if found and node has right, then successor is min in right
    find_min(node.right)
  elsif val == node.val
  # if found and node has no right, then it is one of the ancestors
    possible_successor
  elsif val < node.val
  # if the value is on the left subtree,
  # then current node is possible successor.
  # Pass it as possible_successor
    find_successor(node.left, val, node)
  else
  # if the value is on the right subtree,
  # then current node can't be possible successor.
  # Pass along ancestor which could be successor
    find_successor(node.right, val, possible_successor)
  end
end

# test by calling find_successor method
find_successor(root, 3).val
=> 4

I’ll be more frequent with new posts now. I promise :)