# 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:

## 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:

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

:

## 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 then call `in_order(root)`

which pushes the very first frame onto our call stack, so the stack would look like so:

## Call stack

*0*

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

```
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

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

```
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

*0*1

*1*

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

```
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

*0*1

*1*

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

*0*1

*1*

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

## 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)
```

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

*0*

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.