-
Notifications
You must be signed in to change notification settings - Fork 237
BST In order Successor
Unit 8 Session 2 (Click for link to problem statements)
- 💡 Difficulty: Easy to Medium
- ⏰ Time to complete: 15 mins
- 🛠️ Topics: Trees, Binary Search Trees, Successor Finding
Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
- Question: How should the function handle cases where there is no in-order successor in the tree?
- Answer: Return None if there is no in-order successor (e.g., when the given node is the rightmost node).
HAPPY CASE
Input: BST with nodes [20, 9, 25, 5, 12], find in-order successor of 12
Output: 20
Explanation: 20 is the next node in in-order traversal after 12.
EDGE CASE
Input: BST with nodes [20, 9, 25, 5, 12], find in-order successor of 25
Output: None
Explanation: 25 is the rightmost node, and there is no successor.
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
This problem is primarily a tree navigation problem, specifically dealing with the properties of binary search trees to find the in-order successor.
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Utilize the BST properties to efficiently find the in-order successor.
1) If the node has a right subtree, the successor is the leftmost node in that subtree.
2) If the node has no right subtree, the successor is one of its ancestors; specifically, the nearest ancestor for which the given node is in its left subtree.
- Failing to check both cases: node has a right subtree or no right subtree, leading to incorrect or incomplete results.
Implement the code to solve the algorithm.
def inorder_successor(root, node):
"
Find the in-order successor of a given node in a binary search tree.
"
if node.right:
# The successor is the leftmost node of the right subtree
return find_min(node.right)
# Traverse up the ancestors
successor = None
while root:
if node.val < root.val:
successor = root
root = root.left
elif node.val > root.val:
root = root.right
else:
break
return successor
def find_min(node):
"
Find the smallest node in a subtree.
"
while node.left:
node = node.left
return node
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
- Test with a variety of tree configurations and node positions to ensure that the successor is correctly identified.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
-
Time Complexity:
O(h)
where h is the height of the tree. This operation requires traversal up to the root or down to a leaf. -
Space Complexity:
O(1)
as it only requires a few pointers without additional data structures.