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 <, :left, :right); end
root =
root.left =
root.left.left =
root.left.right =
root.right =
root.right.left =
root.right.right =

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

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
  elsif val == node.val
  # if found and node has no right, then it is one of the ancestors
  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)
  # 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)

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

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

blog comments powered by Disqus