4 Ways To Traverse Binary Trees (with animations!)
Tags: computerscience, programming, career
Published: 2020-09-07 02:41:37

---
title: 4 Ways To Traverse Binary Trees (with animations!)
published: true
description: in-order, depth-first-search, breadth-first-search, and post-order
tags: computerscience, programming, career
series: The Binary Tree Interview
cover_image: https://dev-to-uploads.s3.amazonaws.com/i/cdgl7fif7ut6hyhg3emw.jpg
---
# Brush up with Tree Data Structure
Here's a Binary Search Tree (BST). Every circle is called a node and each node can be connected to 2 other nodes -- one on the left and right. That's why they're called Binary Trees, they have 2 "child" nodes and it looks like a tree!

![A Binary Tree](https://dev-to-uploads.s3.amazonaws.com/i/4t1sycs1xsvt4qqs1m57.png)

The left child node is always smaller or equal in value than the parent, and the right is always greater or equal. Some implementations allow only the left or right node to be equal to the parent. Personally, I like putting equal nodes, to the left side 😁

BTW, here's a Binary Search Tree using python3!

```python
class TreeNode:
  def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
```
The default values for the left and right tree are null/None and default val is 0.

# Traversals

For each traversal I'm going to give a brief description of how it moves through the binary tree, starting from the root (the top). Then show the code for traversal using python and lastly a GIF visualizing how the program moves through the tree! Also all of the gifs will end early without going through the entire tree because the gif sizes were getting too big and I had to cut it short 🤷‍♂️.

The first 3 are very similar and only differ by one line of code but give very different results! I call them the traversal triplets.

## In Order
This method moves through the tree "in order". Meaning that it will print every node’s value in order from smallest to greatest.

Using recursion, the function will call itself on the left sub-tree, then print the current value, and then call itself on the right sub-tree.
The result is that it prints the tree's values.... in order. 

```python
def in_order(node):
    if node == None:
        return
    in_order(node.left)
    print(node.val)
    in_order(node.right)
```
![In Order Traversal Animation](https://dev-to-uploads.s3.amazonaws.com/i/w0z2pz1f7th1k0ut8rbr.gif)

# Depth-First Search (also known as pre-order)
Depth-First Search is the classic traversal method for trees and also graphs. This method is also known as the pre-order traversal because it first operates on the current node, then the left and right child nodes.

Depth first search is very popular for general traversal as well as making copies of the tree.

```python
def dfs(node):
    if node == None:
        return
    print(node.val)
    dfs(node.left)
    dfs(node.right)
```
![Pre Order Traversal Animation](https://dev-to-uploads.s3.amazonaws.com/i/qpsgkhgccjrjn9ybxb6l.gif)

# Post Order
The last of the traversal triplets. It first operates on the left and right child nodes then the current node.

Post Order is very useful for deleting a tree, as it goes from the bottom up.

```python
def post_order(node):
    if node == None:
        return
    post_order(node.left)
    post_order(node.right)
    print(node.val)
```
![Post Order Traversal Animation](https://dev-to-uploads.s3.amazonaws.com/i/zv1x6vo9p8cqopqzod0n.gif)

# Breadth-First Search (also Level Order)
This one is a little more tricky and can only be done using a  queue. It might be possible with recursion but it's easier to understand iteratively. It uses a queue when traversing so it goes through the tree as nodes are added to it. As a result, it goes through the tree, level by level. This makes breadth-first search a popular search algorithm in graphs as well.

Although I couldn't make an animation for this one, I created a numbered diagram to show what order the nodes would be printed!

```python
# deque is a python queue library
from collections import deque

def bfs(root):
    q = deque([root])
    while len(q) > 0:
        node = q.popleft()
        print(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
```
![Numbered Level Order Traversal](https://dev-to-uploads.s3.amazonaws.com/i/eijg2o9eo8xtqk40q91d.png)

# Conclusion
By understanding these 4 traversal methods, you can demystify most interview problems involving binary trees. A lot of them can be broken down into easily solvable chunks if you know the right traversal method to use! If you're curious about the exact methodology, I've got a guide coming out soon! I hope it'll be the only resource needed for solving binary tree problems.

Also, all animations were courtesy of http://btv.melezinek.cz/binary-search-tree.html. Make sure to check them out if you want to play around with the animations! 

# By The Way I'm Making a Guide
I'm making a guide on how to solve almost any Binary Tree problem on LeetCode (and therefore in an interview)! Join me on my journey by [following me on Twitter!](https://twitter.com/abdisalan_js)

Here's a sneak peek 😃
{% twitter 1300153885642776576 %}