Kth Smallest Element in a BST
- 1 min read
- DFS
- Tree
- Blind75
- LC-Medium
- Binary Tree
- Binary Search Tree
3 years ago
Approach: Iterative DFS
- Do iterative DFS, and keep counter
i. - Increment
iwhenever current left-most node is reached - Return value of current node when
i == k
def kthSmallest(root: Optional[TreeNode], k: int) -> int:
i = 0
cur = root
stack = []
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
i += 1
if i == k:
return cur.val
cur = cur.right