October
18th,
2017

blog comments powered by Disqus
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 :)