Kth Smallest Element in Binary Search Tree
- 1 min read
- LC-Medium
- Binary-search-tree
3 years ago
Solution
- Naive way is to do an In-order Traversal, append values to a list, and after we've traversed the whole tree, return the appropriate value
-
If we don't want to use this extra array, then we'll have to do an Iterative Tree Traversal
| Time | Space | Explanation |
|---|---|---|
O() | O() |
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
cur = root
stack = []
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
node = stack.pop()
k -= 1
if k == 0:
return node.val
cur = node.right