Skip to main content

Traverse

Minimum element in BST​

Basic·
3 Approaches
FIG. MINIMUM ELEMENT BST● INTERACTIVE
visualization loads as you reach it
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 Approaches
FIG. INORDER SUCCESSOR IN BST● INTERACTIVE
visualization loads as you reach it
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 Approaches
FIG. RANGE SUM OF BST● INTERACTIVE
visualization loads as you reach it
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
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

235. Lowest Common Ancestor of a Binary Search Tree​

Medium·
4 Approaches
FIG. LOWEST COMMON ANCESTOR BST COUNT● INTERACTIVE
visualization loads as you reach it
class Solution:
def lowestCommonAncestor(self, root: "TreeNode", p: "TreeNode", q: "TreeNode") -> "TreeNode":
def rec(node):
nonlocal lca
if not node:
return 0
left = rec(node.left) if node.left else 0
right = rec(node.right) if node.right else 0
found = left + right + int(node == p) + int(node == q)
if not lca and found == 2:
lca = node
return found
 
lca = None
rec(root)
return lca