Traverse
Minimum element in BST
- DFS (Recursive)
- DFS (Iterative)
- BFS
Explanation
In a BST, the leftmost node contains the minimum value. We only need to traverse left children until we reach a leaf node.
Analysis
- Python
def minValue(self, root):
def dfs(node):
if not node:
return float("inf")
return min(node.data, dfs(node.left))
return dfs(root)
Analysis
- Python
def minValue(self, root):
stack = [root]
mini = float("inf")
while stack:
node = stack.pop()
if node:
mini = min(mini, node.data)
stack.append(node.left)
return mini
Analysis
- Python
import collections
def minValue(self, root):
queue = collections.deque([root])
mini = float("inf")
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node:
mini = min(mini, node.data)
queue.append(node.left)
return mini