DSA Patterns (Multi-Lang)•Part 7: Binary Trees, BSTs & Traversals (53 - 64)
Kth Smallest Element in a BST.
In Simple Words:
In-order traversal (left -> root -> right) of a BST visits elements in strictly sorted ascending order. Stop and return the $K$-th visited element.
- Time: $O(H + K)$ | Space: $O(H)$
Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++
Switch tabs or choose Alldef kthSmallest(root: TreeNode | None, k: int) -> int:
stack = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
k -= 1
if k == 0:
return curr.val
curr = curr.right
return -1