How to traverse a tree in Python

Tree traversal is a fundamental process for any tree-based data structure. It lets you visit each node in a specific order. Python provides powerful ways to handle this task efficiently.

In this article, you'll explore various traversal techniques and their real-world applications. You'll also get practical tips and effective debugging advice to help you confidently navigate any tree structure.

Recursive depth-first traversal

class TreeNode:
   def __init__(self, val=0, left=None, right=None):
       self.val = val
       self.left = left
       self.right = right

def traverse_dfs(root):
   if root:
       print(root.val, end=' ')  # Visit node first (preorder)
       traverse_dfs(root.left)    # Visit left subtree
       traverse_dfs(root.right)   # Visit right subtree

root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
traverse_dfs(root)--OUTPUT--1 2 4 5 3

The traverse_dfs function offers a classic recursive solution for depth-first search. It works by diving as deep as possible down one path before backtracking. This specific order—visiting the node, then its left subtree, then its right—is known as preorder traversal.

• The function first processes the current root node.
• It then calls itself on the left child, repeating the process until it can go no further.
• Finally, it backtracks and explores the right subtree.

Common tree traversal techniques

While recursion is a natural fit for tree traversal, iterative approaches using queues and stacks give you more explicit control over the process.

Using a queue for breadth-first traversal

from collections import deque

def traverse_bfs(root):
   queue = deque([root])
   while queue:
       node = queue.popleft()
       print(node.val, end=' ')
       if node.left: queue.append(node.left)
       if node.right: queue.append(node.right)

root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
traverse_bfs(root)--OUTPUT--1 2 3 4 5

The traverse_bfs function uses a queue to explore the tree level by level. It starts by adding the root node to a deque, a highly efficient queue implementation. The process then unfolds in a loop that continues as long as the queue has nodes.

• It removes the node at the front of the queue using popleft().
• After processing the node, it adds its left and right children to the back of the queue.

This first-in, first-out approach ensures you visit all nodes at one level before moving to the next.

Iterative depth-first traversal with a stack

def traverse_dfs_iterative(root):
   stack = [root]
   while stack:
       node = stack.pop()
       print(node.val, end=' ')
       if node.right: stack.append(node.right)  # Right first (LIFO)
       if node.left: stack.append(node.left)

root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
traverse_dfs_iterative(root)--OUTPUT--1 2 4 5 3

The traverse_dfs_iterative function swaps recursion for a stack, giving you manual control over the traversal. This approach avoids recursion depth limits and can be more efficient for unbalanced trees. It works by managing nodes with a Last-In, First-Out (LIFO) strategy.

• A node is popped from the top of the stack and processed.
• The function then pushes the right child onto the stack, followed by the left child.
• Because the left child is added last, it’s the next one to be processed, ensuring the traversal dives deep down the left side first.

Implementing different DFS orders

def inorder(root):
   if root:
       inorder(root.left)         # Left first
       print(root.val, end=' ')   # Then node
       inorder(root.right)        # Then right

root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
inorder(root)--OUTPUT--4 2 5 1 3

The inorder function showcases a different DFS order. Unlike the preorder traversal you saw earlier, inorder traversal processes the left subtree, then the current node, and finally the right subtree. This sequence is particularly useful for binary search trees, as it retrieves nodes in sorted order.

• The function first calls itself on the left child, going as deep as possible.
• After the left subtree is fully explored, it processes the current node.
• Finally, it moves on to the right subtree.

Advanced tree traversal approaches

Moving beyond the foundational stack and queue approaches, you'll find advanced methods that offer unique advantages like memory optimization and lazy evaluation.

Morris traversal for constant space complexity

def morris_traversal(root):
   curr = root
   while curr:
       if not curr.left:
           print(curr.val, end=' ')
           curr = curr.right
       else:
           pred = curr.left
           while pred.right and pred.right != curr:
               pred = pred.right
           if not pred.right:
               pred.right = curr  # Create temporary link
               curr = curr.left
           else:
               pred.right = None  # Remove the link
               print(curr.val, end=' ')
               curr = curr.right

root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
morris_traversal(root)--OUTPUT--4 2 5 1 3

The morris_traversal function offers a unique way to perform an inorder traversal without recursion or a stack. This approach achieves constant space complexity by temporarily modifying the tree's structure, making it incredibly memory-efficient for large or unbalanced trees.

• Before visiting a node's left subtree, it finds the rightmost node of that subtree—its inorder predecessor.
• It then creates a temporary link from the predecessor back to the current node, essentially creating a breadcrumb trail to return.
• After traversing the left side, it follows the link back, processes the node, and removes the temporary link to restore the tree.

Using yield for lazy tree traversal

def tree_generator(root):
   if root:
       yield from tree_generator(root.left)
       yield root.val
       yield from tree_generator(root.right)

root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
for val in tree_generator(root):
   print(val, end=' ')--OUTPUT--4 2 5 1 3

The tree_generator function uses the yield keyword to create a generator. This provides a memory-efficient way to traverse the tree by producing values one at a time, only when you ask for them. This approach is known as lazy evaluation, as it avoids building a complete list of nodes in memory.

• The function pauses its execution at each yield statement, returning a single value.
• The yield from expression elegantly delegates to the recursive calls, passing along values from the left and right subtrees without extra boilerplate code.
• This structure results in an inorder traversal, but you can process each node as it's generated instead of waiting for the entire traversal to finish.

Level-wise traversal with node information

from collections import deque

def level_order_info(root):
   queue = deque([(root, 1)])  # (node, level)
   while queue:
       node, level = queue.popleft()
       print(f"{node.val} at level {level}")
       if node.left: queue.append((node.left, level + 1))
       if node.right: queue.append((node.right, level + 1))

root = TreeNode(1, TreeNode(2), TreeNode(3))
level_order_info(root)--OUTPUT--1 at level 1
2 at level 2
3 at level 2

The level_order_info function builds on breadth-first traversal to also track each node's depth. It achieves this by storing (node, level) tuples in the queue instead of just the nodes. This simple tweak gives you more contextual information with each step.

• The traversal begins with the root node at level 1.
• As you process each node, you add its children to the queue with an incremented level, level + 1.
• This approach lets you know the exact depth of every node, which is useful for level-specific logic.

Move faster with Replit

Replit is an AI-powered development platform that transforms natural language into working applications. Describe what you want to build, and Replit Agent creates it, complete with databases, APIs, and deployment.

For the tree traversal techniques covered in this article, Replit Agent can turn them into production-ready tools:

• Build a file system navigator that displays directories and files in sorted order, using an inorder traversal approach.
• Create an interactive organizational chart viewer that visualizes employee hierarchies level by level, applying the logic from level_order_info.
• Deploy a mathematical expression evaluator that parses and calculates formulas represented as an expression tree, similar to a preorder traversal.

Turn your own concepts into a working application. Describe your idea to Replit Agent, and it will write the code, test it, and handle deployment for you.

Common errors and challenges

Even with the right approach, you can run into a few common pitfalls when traversing trees in Python.

A frequent mistake is failing to handle None nodes. Recursive traversals rely on a base case to stop, and if your code tries to access an attribute like .left on a node that doesn't exist, you'll get an error.

• Always start your recursive function with a check, like if not root: return, to gracefully handle empty subtrees.
• This prevents your program from crashing when it reaches a leaf node's child.

Deep or unbalanced trees can cause a RecursionError, also known as a stack overflow. Each recursive call adds a new frame to Python's call stack, and if the tree is too deep, you'll hit the system's limit. The iterative depth-first traversal is your best defense against this—by managing your own stack in memory, you bypass the recursion limit entirely.

It's also surprisingly easy to forget to traverse all possible branches. A simple logic error, like omitting the recursive call for the right child, will cause your function to ignore an entire section of the tree. This bug can be hard to find, as the code runs without errors but produces incorrect results, so always double-check that your traversal function accounts for both subtrees.

Handling None nodes in recursive traversals

One of the most common ways this error appears is when you're performing calculations. A function might work perfectly on a valid node but will crash when it receives a None value. Consider the following sum_tree_values function, which attempts to add up all node values.

def sum_tree_values(root):
   return root.val + sum_tree_values(root.left) + sum_tree_values(root.right)

# This will fail when encountering None nodes

The function crashes because it doesn't have a base case for None nodes. The expression root.val fails when a recursive call reaches an empty branch. See how a simple check makes the function work correctly.

def sum_tree_values(root):
   if root is None:
       return 0
   return root.val + sum_tree_values(root.left) + sum_tree_values(root.right)

The fix is simple but powerful. The updated sum_tree_values function now checks if root is None and returns 0. This base case prevents the function from trying to access attributes on a non-existent node. It ensures that empty branches contribute nothing to the sum, allowing the recursion to complete without errors. This pattern is essential for any recursive function that aggregates values or performs calculations on a tree, so it's a good habit to build.

Avoiding stack overflow with iterative depth-first traversal

Recursive functions are elegant but have a hidden limit. Each call adds to Python's call stack, and a very deep tree can exhaust this memory, causing a stack overflow. The find_max_depth function below, which recursively finds a tree's depth, demonstrates this vulnerability.

def find_max_depth(root):
   if root is None:
       return 0
   return 1 + max(find_max_depth(root.left), find_max_depth(root.right))

# Will cause stack overflow for very deep trees

The find_max_depth function's design requires a new stack frame for each level of the tree. With a deep enough tree, this exhausts available memory and crashes the program. An iterative approach gets around this limitation.

def find_max_depth(root):
   if root is None:
       return 0
   
   stack = [(root, 1)]  # (node, depth)
   max_depth = 0
   
   while stack:
       node, depth = stack.pop()
       max_depth = max(max_depth, depth)
       if node.right: stack.append((node.right, depth + 1))
       if node.left: stack.append((node.left, depth + 1))
   
   return max_depth

The iterative find_max_depth function trades recursion for a manually managed stack, preventing stack overflow errors. It works by storing (node, depth) tuples. This approach gives you direct control over memory, making it a robust solution for deep or unbalanced trees where recursion would fail.

• As it processes each node, it updates a max_depth variable.
• It then adds the node’s children to the stack with an incremented depth, ensuring the entire tree is explored safely.

Forgetting to traverse all branches

This type of bug can be tricky because the code runs without any errors. It just returns the wrong output. Consider a function like collect_all_values, which is meant to gather every node's value. The implementation below contains a subtle omission.

def collect_all_values(root):
   result = []
   
   def inorder(node):
       if node:
           inorder(node.left)
           result.append(node.val)
           # Forgot to traverse right subtree!
   
   inorder(root)
   return result

The inorder helper function omits the recursive call for the right child. As a result, it only collects values from the left side of the tree, leading to an incomplete list. See how the corrected version fixes this.

def collect_all_values(root):
   result = []
   
   def inorder(node):
       if node:
           inorder(node.left)
           result.append(node.val)
           inorder(node.right)  # Don't forget the right subtree!
   
   inorder(root)
   return result

The corrected collect_all_values function fixes the bug by adding the missing inorder(node.right) call. This simple addition ensures the traversal doesn't just stop after visiting the left side. It now correctly explores the right subtree, gathering all node values as intended. This kind of logic error is easy to make but hard to spot since the code runs without crashing. Always double-check that your recursive functions visit every branch to avoid incomplete results.

Real-world applications

Moving past the common errors, you'll find that tree traversal is fundamental to many real-world applications you interact with daily.

Traversing file systems with depth-first search

Depth-first search is a natural fit for navigating a file system, as its recursive approach mirrors the way you'd explore nested directories one by one.

import os

def traverse_directory(path, level=0):
   for item in os.listdir(path):
       item_path = os.path.join(path, item)
       print('  ' * level + item)
       if os.path.isdir(item_path):
           traverse_directory(item_path, level + 1)

# Example usage with a sample directory
traverse_directory('./sample_dir')

The traverse_directory function uses Python's os module to map out a directory's structure. It works by stepping through each item found by os.listdir() and printing its name.

• The level parameter controls the indentation, which creates a visual hierarchy of files and folders.
• When the function finds a directory, it calls itself on that new path. This is how it explores nested subdirectories.
• This process continues until it's visited every item, giving you a complete, tree-like view of the directory's contents.

Evaluating mathematical expressions with tree traversal

By representing a mathematical formula as an expression tree, you can solve it using a postorder traversal, which calculates the result from the operands up to the operators.

class ExprNode:
   def __init__(self, value, left=None, right=None):
       self.value = value
       self.left = left
       self.right = right

def evaluate_expression_tree(node):
   if node is None:
       return 0
   
   if not node.left and not node.right:  # Leaf node (operand)
       return int(node.value)
       
   left_val = evaluate_expression_tree(node.left)
   right_val = evaluate_expression_tree(node.right)
   
   if node.value == '+': return left_val + right_val
   if node.value == '-': return left_val - right_val
   if node.value == '*': return left_val * right_val
   if node.value == '/': return left_val / right_val

# Create expression tree for: (3 + 2) * 5
expr_tree = ExprNode('*',
                   ExprNode('+', ExprNode('3'), ExprNode('2')),
                   ExprNode('5'))
result = evaluate_expression_tree(expr_tree)
print(f"Expression result: {result}")

The evaluate_expression_tree function recursively calculates an expression's final value. It solves the problem by breaking it down into its simplest parts—the numbers themselves.

• The function first travels down to the leaf nodes, which represent numbers, and converts their values to integers.
• As it moves back up the tree, it applies the operator at each parent node, like + or *, to the results returned from its children.

This process continues until it reaches the root, yielding the expression's final answer.

Get started with Replit

Turn what you've learned into a real tool. Tell Replit Agent to build “a web-based calculator that solves math problems by parsing them into an expression tree” or “a tool that visualizes a file directory as an interactive tree.”

Replit Agent writes the code, tests for errors, and deploys the app for you. Turn your idea into a live application. Start building with Replit.