Binary Tree Traversal: Recursive and Iterative Approaches
Tech
1
Binary Tree Fundamentals
A binary tree node consists of a value, a left child, and a right child:
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
Recursive Traversal
Three steps define recursion:
- Define function parameters and return type
- Establsih base case conditions
- Implement single-level recursive logic
Preorder Traversal (Root → Left → Right)
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
if not root:
return result
result.append(root.val)
result += self.preorderTraversal(root.left)
result += self.preorderTraversal(root.right)
return result
Inorder Traversal (Left → Root → Right)
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
if not root:
return result
result += self.inorderTraversal(root.left)
result.append(root.val)
result += self.inorderTraversal(root.right)
return result
Postroder Traversal (Left → Right → Root)
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
if not root:
return result
result += self.postorderTraversal(root.left)
result += self.postorderTraversal(root.right)
result.append(root.val)
return result
Iterative Traversal with Stack
Stack operations can simulate recursion behavior.
Preorder Traversal
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
stack = []
if not root:
return result
stack.append(root)
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
Postorder Traversal
Modify preorder by processing left before right, then reverse the result:
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
stack = []
if not root:
return result
stack.append(root)
while stack:
node = stack.pop()
result.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return result[::-1]
Inorder Traversal
Inorder requires tracking both traversal and processing. Use a pointer to traverse down to the leftmost node, then pop from stack to get the root, then move to the right subtree.
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = []
stack = []
current = root
if not root:
return result
while current or stack:
if current:
stack.append(current)
current = current.left
else:
current = stack.pop()
result.append(current.val)
current = current.right
return result
Level Order Traversal with Queue
import collections
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
result = []
queue = collections.deque()
if not root:
return result
queue.append(root)
while queue:
level_size = len(queue)
level_vals = []
for _ in range(level_size):
node = queue.popleft()
level_vals.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level_vals)
return result
LeetCode Problems
Problem 107: Binary Tree Level Order Traversal II
import collections
class Solution:
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
result = []
queue = collections.deque()
if not root:
return result
queue.append(root)
while queue:
level_vals = []
for _ in range(len(queue)):
node = queue.popleft()
level_vals.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level_vals)
return result[::-1]
Problem 199: Binary Tree Right Side View
import collections
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
result = []
queue = collections.deque()
if not root:
return result
queue.append(root)
while queue:
level_size = len(queue)
for i in range(level_size):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if i == level_size - 1:
result.append(node.val)
return result
Problem 637: Average of Levels in Binary Tree
import collections
class Solution:
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
result = []
queue = collections.deque()
if not root:
return result
queue.append(root)
while queue:
level_size = len(queue)
level_sum = 0
for _ in range(level_size):
node = queue.popleft()
level_sum += node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level_sum / level_size)
return result
Problem 429: N-ary Tree Level Order Traversal
import collections
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
result = []
queue = collections.deque()
if not root:
return result
queue.append(root)
while queue:
level_size = len(queue)
level_vals = []
for _ in range(level_size):
node = queue.popleft()
level_vals.append(node.val)
if node.children:
queue.extend(node.children)
result.append(level_vals)
return result
Problem 515: Find Largest Value in Each Tree Row
import collections
class Solution:
def largestValues(self, root: Optional[TreeNode]) -> List[int]:
result = []
queue = collections.deque()
if not root:
return result
queue.append(root)
while queue:
level_size = len(queue)
level_max = float('-inf')
for _ in range(level_size):
node = queue.popleft()
level_max = max(level_max, node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level_max)
return result
Problem 116: Populating Next Right Pointers in Each Node
import collections
class Solution:
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
if not root:
return root
queue = collections.deque([root])
while queue:
prev = None
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
if prev:
prev.next = node
prev = node
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return root
Problem 117: Populating Next Right Pointers in Each Node II
import collections
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return root
queue = collections.deque([root])
while queue:
prev = None
for _ in range(len(queue)):
node = queue.popleft()
if prev:
prev.next = node
prev = node
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return root
Problem 104: Maximum Depth of Binary Tree
import collections
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
queue = collections.deque([root])
depth = 0
while queue:
depth += 1
for _ in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return depth
Problem 111: Minimum Depth of Binary Tree
import collections
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
queue = collections.deque([root])
depth = 0
while queue:
depth += 1
for _ in range(len(queue)):
node = queue.popleft()
if not node.left and not node.right:
return depth
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return depth
Key Takeaways
- Preodrer, inorder, and postorder traversals differ in when the root node is processed
- Stack-based iterative approaches avoid recursion overhead
- For inorder traversal, a pointer tracking current node combined with stack enables non-recursive traversal
- Level order traversal requires queue and processing nodes per level
- Problems extending level order typically involve modifying output format or adding extra node properties
