{"inorder":{"time":"O(n)","space":"O(h) recursive, O(n) iterative worst"},"preorder":{"time":"O(n)","space":"O(h)"},"postorder":{"time":"O(n)","space":"O(h)"},"level_order":{"time":"O(n)","space":"O(w) where w = max width"}}
Tree Traversal Skill
Atomic Responsibility: Execute tree traversal algorithms with correct order and optimal space.
Tree Node Definition
from typing importOptional, Listfrom collections import deque
classTreeNode:
"""Standard binary tree node."""def__init__(self, val: int = 0, left: 'TreeNode' = None, right: 'TreeNode' = None):
self.val = val
self.left = left
self.right = right
DFS - Inorder (Left, Root, Right)
definorder_recursive(root: Optional[TreeNode]) -> List[int]:
"""
Inorder traversal - gives sorted order for BST.
Time: O(n), Space: O(h) where h = height
Args:
root: Root of binary tree
Returns:
List of values in inorder sequence
"""
result = []
defdfs(node: Optional[TreeNode]) -> None:
ifnot node:
return
dfs(node.left)
result.append(node.val)
dfs(node.right)
dfs(root)
return result
definorder_iterative(root: Optional[TreeNode]) -> []:
result = []
stack = []
current = root
current stack:
current:
stack.append(current)
current = current.left
current = stack.pop()
result.append(current.val)
current = current.right
result
List
int
"""
Iterative inorder using explicit stack.
Time: O(n), Space: O(h)
Use when: Recursion depth might exceed limit.
"""
while
or
# Go left as far as possible
while
# Process current node
# Move to right subtree
return
DFS - Preorder (Root, Left, Right)
defpreorder_recursive(root: Optional[TreeNode]) -> List[int]:
"""
Preorder traversal - useful for tree serialization.
Time: O(n), Space: O(h)
"""ifnot root:
return []
return ([root.val] +
preorder_recursive(root.left) +
preorder_recursive(root.right))
defpreorder_iterative(root: Optional[TreeNode]) -> List[int]:
"""
Iterative preorder using stack.
Note: Push right first, then left (LIFO).
"""ifnot root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
# Right first (so left is processed first)if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
DFS - Postorder (Left, Right, Root)
defpostorder_recursive(root: Optional[TreeNode]) -> List[int]:
"""
Postorder traversal - useful for deletion, expression evaluation.
Time: O(n), Space: O(h)
"""ifnot root:
return []
return (postorder_recursive(root.left) +
postorder_recursive(root.right) +
[root.val])
defpostorder_iterative(root: Optional[TreeNode]) -> List[int]:
"""
Iterative postorder using two stacks or modified preorder.
Trick: Modified preorder (root, right, left) then reverse.
"""ifnot root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
# Left first (so right is processed first after reverse)if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return result[::-1] # Reverse to get postorder
BFS - Level Order Traversal
deflevel_order(root: Optional[TreeNode]) -> List[List[int]]:
"""
Level-by-level traversal using queue.
Time: O(n), Space: O(w) where w = max width
Returns:
List of levels, each level is a list of values
"""ifnot root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
level = []
for _ inrange(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
defzigzag_level_order(root: Optional[TreeNode]) -> List[List[int]]:
"""
Level order with alternating direction.
Time: O(n), Space: O(w)
"""ifnot root:
return []
result = []
queue = deque([root])
left_to_right = Truewhile queue:
level_size = len(queue)
level = deque()
for _ inrange(level_size):
node = queue.popleft()
if left_to_right:
level.append(node.val)
else:
level.appendleft(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(list(level))
left_to_right = not left_to_right
return result
BST Validation
defis_valid_bst(root: Optional[TreeNode]) -> bool:
"""
Validate if tree is a valid Binary Search Tree.
Time: O(n), Space: O(h)
Property: All left descendants < node < all right descendants
"""defvalidate(node: Optional[TreeNode],
min_val: float,
max_val: float) -> bool:
ifnot node:
returnTrueifnot (min_val < node.val < max_val):
returnFalsereturn (validate(node.left, min_val, node.val) and
validate(node.right, node.val, max_val))
return validate(root, float('-inf'), float('inf'))
□ Null root handled?
□ Base case returns correct value?
□ Both children processed?
□ Return value accumulated correctly?
□ Stack/queue order correct?
□ Tested with single node and empty tree?
