csanim.com .Depth First Traversal: Inorder, Preorder and Postorder tree traversals - Animated guide
I mostly write about cs algorithms, data structures and code challenges.

Depth First Traversal: Inorder, Preorder and Postorder tree traversals - Animated guide

Implement common Depth-First Traversal (DFS) patterns with recursion and learn about the call stack in this visual guide.

DFS and Recursion

Depth-first-search utilizes a stack (LIFO, last-in-first-out) data structure to traverse by depth-first. We can utilize the call stack through recursion OR we could go with an iterative approach using our own stack. DFS is extremely simple and elegant to implement with recursion on the call stack, while the iterative approach is significantly more verbose.

Time Complexity: O(n) where n is the number of nodes in the tree

Space Complexity: O(d) where d is the max depth of the tree

Trees have several ways to be traversed, the most common DFS traversals being:

In-order

in_order(root.left)
print(root.val)
in_order(root.right)

Post-order

post_order(root.left)
post_order(root.right)
print(root.val)

Pre-order

print(root.val)
pre_order(root.left)
pre_order(root.right)

Breakdown of recursive DFS tree traversals

DFS tree traversals are fairly simple once you understand how recursive methods push/pop frames onto the call stack.

In simple terms:

Every time we recursively call one of our traversal methods (e.g., in_order(root.left)) we add a frame to the call stack.

When calculations within the frame have been completed, that frame is popped off the call stack and the next line of code is run on the previous frame in the stack.

Let's use the in-order traversal as our main example

Simple one node tree

For explanation purposes we are going to assume we have a tree with a single root node with no leaves since the same functionality is repeated across every recursion.

Our full code snippet:

In-order traversal

def in_order(root):
   if root:
      in_order(root.left)
      print(root.val)
      in_order(root.right)
   # end

# Initialize the tree
root = Node(1)
in_order(root)

We first initialize our Binary Search Tree with a single node at line 9:

In-order traversal

Expand code
def in_order(root):
   if root:
      in_order(root.left)
      print(root.val)
      in_order(root.right)
   # end

# Initialize the tree
root = Node(1)
in_order(root)

We then call in_order(root) which pushes the very first frame onto our call stack, so the stack would look like so:

Call stack

10

After calling in_order(root) we now have a single frame pushed onto the call stack.

Node representation

We're showing nodes as bracketed objects (e.g., {val:1,left:None,right:None}) for brevity, the actual python representation of a class object isn't naturally represented this way.

Next we will handle each method inside of this first frame:

In-order traversal

Expand code
def in_order(root):
   if root:
      in_order(root.left)
      print(root.val)
      in_order(root.right)
   # end

# Initialize the tree
root = Node(1)
in_order(root)

*Just remember, every time we call a method (e.g., in_order()) a new frame is added to the call stack.

line 3 pushes a second frame onto the stack with the left node (in this case root.left is None):

Call stack

Ø1

After calling in_order(root.left) another frame is added to the stack.

In our second frame we don't get past the if statement since root is None, which of course means no new frames are added:

In-order traversal

Expand code
def in_order(root):
   if root:
      in_order(root.left)
      print(root.val)
      in_order(root.right)
   # end

# Initialize the tree
root = Node(1)
in_order(root)

Since no code was run, frame 2 is popped off the stack immediately after being called and we're back to a single frame on the stack:

Call stack

Ø011

frame2 is popped off the stack and we can run the next line of code in frame1, which would be the print statement.

We have completed the left node branch and returned to frame one which means the print statement will now be run on line 4.

After the print statement we move to the in_order(root.right) method which pushes a new frame onto the call stack (again with a null value):

In-order traversal

Expand code
def in_order(root):
   if root:
      in_order(root.left)
      print(root.val)
      in_order(root.right)
   # end

# Initialize the tree
root = Node(1)
in_order(root)

Call stack

Ø011

We call the in_order(root.right) method which adds another frame to the stack.

Since the right node is also empty, frame2 immediately pops back off just like with the empty left node previously.

Call stack

Ø011

We have popped back to just a single frame on the stack since there are no left or right children.

In-order traversal

Expand code
def in_order(root):
   if root:
      in_order(root.left)
      print(root.val)
      in_order(root.right)
   # end

# Initialize the tree
root = Node(1)
in_order(root)

And finally after traversing all left/right nodes, the first call to in_order(root) finishes running and the final frame (frame1) pops off, giving us an empty call stack and wrapping up our recursive tree traversal.

Call stack

10

Last frame removed from the call stack.

As you can see, once we understand how the call stack works, recursive DFS traversals are actually quite easy to implement.

Looking for additional tree traversal visualizations? Check the breadth-first article & visualization here.

Note on iterative DFS tree traversals

Though iterative traversals function essentially the same as recursive traversals, it is significantly more complex to code as we have to manually implement the work that the call stack automatically does with the recursive method. As a personal challenge, try thinking through what exactly the call stack is automatically handling for you and try implementing a custom stack instead.

Author:

headshot-lg.jpg
Japhia
*no spam, just fresh content