Last active
May 17, 2022 10:14
-
-
Save damdafayton/7563048dfa56dbb448e6b7120d0f95c9 to your computer and use it in GitHub Desktop.
BST Successor Search
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment