Skip to main content

Traverse

Minimum element in BST​

Basic·
3 Approachesclick to switch
FIG. MINIMUM ELEMENT BST● INTERACTIVE
visualization loads as you reach it
Time
O(h)
  • dfs only ever recurses into node.left, never node.right, so it walks the left spine down to the leftmost node - the tree's height h.
Space
O(h)
  • The recursion stack depth equals the length of that left spine, h.
def minValue(self, root):
def dfs(node):
if not node:
return float("inf")
return min(node.data, dfs(node.left))
 
return dfs(root)

285. Inorder Successor in BST​

Medium·
2 Approachesclick to switch
FIG. INORDER SUCCESSOR IN BST● INTERACTIVE
visualization loads as you reach it
Time
O(h)
  • recursion moves to node.right or node.left exactly once per level based on the comparison with p.val, so it follows a single root-to-leaf path of length h.
Space
O(h)
  • The recursion call stack grows one frame per level, so it never exceeds the tree's height h.
def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:
def recursion(node):
if node:
if node.val <= p.val:
recursion(node.right)
else:
successor = node
recursion(node.left)
 
successor = None
recursion(root)
return successor

938. Range Sum of BST​

Easy·
2 Approachesclick to switch
FIG. RANGE SUM OF BST● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • rec visits each of the n nodes at most once, pruning subtrees whose values fall entirely outside [low, high].
Space
O(h)
  • The recursion call stack grows one frame per level, up to the tree height h.
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
def rec(node):
nonlocal total
if not node:
return
if low <= node.val <= high:
total += node.val
if node.val >= low:
rec(node.left)
if node.val <= high:
rec(node.right)
 
total = 0
rec(root)
return total

510. Inorder Successor in BST II​

Medium·
FIG. INORDER SUCCESSOR IN BST II● INTERACTIVE
visualization loads as you reach it
Time
O(h)
  • Case 1 descends to the right subtree's leftmost node; case 2 climbs p.parent toward an ancestor. Both are bounded by the tree's height h.
Space
O(1)
  • Only the pointer variable p is tracked; no recursion or auxiliary structure.
def inorderSuccessor(self, node: "Node") -> "Optional[Node]":
# case 1
if node.right:
p = node.right
while p.left:
p = p.left
return p
# case 2
else:
p = node
while p and p.val <= node.val:
p = p.parent
return p