All Traversals¶
Traversal¶
285. Inorder Successor in BST (Medium)¶
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
def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:
stack = [root]
successor = None
while stack:
node = stack.pop()
if node:
if node.val <= p.val:
stack.append(node.right)
else:
successor = node
stack.append(node.left)
return successor
510. Inorder Successor in BST II (Medium)¶
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
938. Range Sum of BST (Easy)¶
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
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
total = 0
stack = [(root, False)]
while stack:
node, visited = stack.pop()
if node:
if visited:
if low <= node.val <= high:
total += node.val
else:
if node.val < high:
stack.append((node.right, False))
if node.val > low:
stack.append((node.left, False))
stack.append((node, True))
return total