Binary Search Tree

Question 1

Recursive Insert

Answer 1

Time Complexity O(n)

def insert(v)

@root = self.push(v, @root)

end

def push(v,n)

if n.nil?

@size += 1

return Node.new(v)

end

if n.value < v

n.right = self.push(v, n.right)

else

n.left = self.push(v, n.left)

end

return n

end

Question 2

Delete A Node

Answer 2

Hibbert Deletion

Time Complexity: O(N)​

def delete_node(v)

self.delete(@root,v)

end

def delete(node, v)

return node if node.nil?

if node.value == v

if node.left.nil? && node.right.nil?

node = nil;

else

min = self.min(node.right)

node. value =min.value
node. right = self.delete(node.right, min.value)

end

elsif node.value < v

node.right = self.delete(node.right, v)

else

node.left = self.delete(node.left, v)

end

return node;

end

end

Question 3

Find Minimum and Maximum

Answer 3

Time Complexity: O(n)

def get_min

return self.min(@root);

end

def get_max

returns elf.max(@root);

end

def min(n)

return n if n.left.nil?

return self.min(n.left);

end

def max(n)

return n if n.right.nil?

returnself.max(n.right);

end

Question 4

Binary Search Tree

Depth First Traversal

Traversal - preorder, inorder,postorder

Answer 4

• *Time Complexity: O(N)**
• *Space Complexity: O(N)**

def pre_order(n)
return if n.nil?
p n.value
self.pre_order(n.left)
self.pre_order(n.right)
end

def in_order(n)
return if n.nil?
self.in_order(n.left)
p n.value
self.in_order(n.right)
end

def post_order(n)
return if n.nil?
self.in_order(n.left)
self.in_order(n.right)
p n.value
end

Question 5

Binary Search Tree

Find Height

Answer 5

Time Complexity: O(N)

def height
self.get_height(@root)
end

def get\_height(n)
 return -1 if n.nil?
 return [self.get\_height(n.left),self.get\_height(n.right)].max + 1
end

Question 6

Binary Search Tree

Validate Binary Search Tree

Brute Force Solution

Answer 6

Time Complexity: O(N^2)

def bst_check_max_min
self.is_binary_search_tree_max_min(@root)
end

def is_binary_search_tree_max_min(node)
return true if node.nil?
if (self.find_max(node.left) <= node.value && self.find_min(node.right) > node.value && self.is_binary_search_tree(node.left) && self.is_binary_search_tree(node.right))
return true
else
return false
end
end

Question 7

Binary Search Tree

Validate Binary Search Tree

Effective Solution

Answer 7

Time Complexity: O(n)

def bst_check
self.is_binary_search_tree(@root, -@@inf, @@inf)
end

def is_binary_search_tree(node, l, g)
return true if node.nil?
if ( l <= node.value && node.value < g ) && self.is_binary_search_tree(node.left, l, node.value) && self.is_binary_search_tree(node.right, node.value, g)
return true
else
return false
end
end

Question 8

Binary Search Tree

In order successor

Answer 8

Time Complexity: O(h)

def inorder\_successor(v)
 node = self.find(v)
 return "Can Not Find node" if node.nil?

if node.right
successor = self.find_min(node.right);
else
ancestor = @root
successor = nil
while ancestor.value != v
if ancestor.value > v
successor = ancestor.value
ancestor = ancestor.left
else
ancestor = ancestor.right
end
end
end
return successor
end