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!

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!

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.

def in_order(node):
    if node == None:
        return
    in_order(node.left)
    print(node.val)
    in_order(node.right)

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.

def dfs(node):
    if node == None:
        return
    print(node.val)
    dfs(node.left)
    dfs(node.right)

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.

def post_order(node):
    if node == None:
        return
    post_order(node.left)
    post_order(node.right)
    print(node.val)

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!

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

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!

Here's a sneak peek 😃