Recall & Review
beginner
What is a Binary Search Tree (BST)?
A Binary Search Tree is a tree data structure where each node has at most two children. The left child's value is less than the parent's value, and the right child's value is greater than the parent's value.
Click to reveal answer
beginner
In a BST, where is the maximum element located?
The maximum element in a BST is located at the rightmost node because values increase as you move right.
Click to reveal answer
beginner
Why do we keep moving right to find the maximum element in a BST?
Because in a BST, all right children have values greater than their parents, so moving right leads to larger values until the largest is found.
Click to reveal answer
intermediate
What is the time complexity of finding the maximum element in a BST?
The time complexity is O(h), where h is the height of the BST. In the worst case (skewed tree), it can be O(n), and in a balanced tree, it is O(log n).
Click to reveal answer
intermediate
Show the Go code snippet to find the maximum element in a BST.
func findMax(root *Node) *Node {
if root == nil {
return nil
}
current := root
for current.Right != nil {
current = current.Right
}
return current
}
Click to reveal answer
Where do you find the maximum element in a BST?
✗ Incorrect
The maximum element is always at the rightmost node in a BST.
What is the first step to find the maximum element in a BST?
✗ Incorrect
You start from the root and keep moving to the right child to find the maximum.
If a BST has only one node, what is the maximum element?
✗ Incorrect
With only one node, that node is both minimum and maximum.
What is the time complexity to find the maximum element in a balanced BST with n nodes?
✗ Incorrect
In a balanced BST, height is log n, so finding max is O(log n).
What happens if you call findMax on an empty BST?
✗ Incorrect
If the BST is empty (root is nil), the function returns nil.
Explain how to find the maximum element in a Binary Search Tree.
Think about the BST property where right children are greater.
You got /4 concepts.
Write a simple Go function to find the maximum element in a BST and explain its steps.
Use a loop to move right until no more right child.
You got /4 concepts.