Tree Traversal: In-Order, Pre-Order, Post-Order | Skilled.dev
Learn

Tree Traversal: In-Order, Pre-Order, Post-Order

Course launching November 17, 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓
Loading...

There are two methods to traverse trees: depth-first search (DFS) and breadth-first search (BFS).

DFS is the most common way, and it is performed by traversing to the leaf nodes. It goes as deep as it can and then moves on to the next branch. DFS is implemented using a stack or recursion.

BFS on the other hand traverse the tree by level and can also be called level-order traversal. So it will go all the way through level 1, then level 2, and follow this path until it reaches the last level. DFS is used to find the shortest path to a node.

DFS is much more common with trees, so we will discuss how it's done here, and then go into DFS vs BFS in more depth in the graph data structure section.

There are three ways to traverse a tree using DFS: in-order traversal, pre-order traversal, and post-order traversal. Each of these implementations are DFS and explore down a path fully. The only difference is the order in which they use the current node's data.

In this article, we'll use the recursive solution to teach the concept, and then in the interview questions, you'll get exposure to the iterative solutions as well.

Traversal Implementations

For all the cases, we will only consider a binary search tree that has a left and right pointer. The iterative solution is long and does not provide much additional insight, so we will only use the recursive solution.

You will notice that all the solutions look very similar - almost identical. The only difference is when we "visit" a node which is when we use the current node's data in our solution algorithm.

Since we are using recursion, we are building up a stack of function calls and it will unwind when we reach the leaf nodes. What determines the order is if we "visit" the node before the recursive call, after visiting the left node recursively, or after visiting both the left and right nodes recursively.

The input function will be the following node implementation:

class BinaryTreeNode {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

In our case we will consider visiting the node just printing its data:

function visitNode(node) {
  console.log(node.data);
}

In-Order Traversal

In-order traversal is the most common and visits the nodes in ascending order. This will start with the smallest value at the left-most node and end at the largest value at the right-most node.

Use in-order traversal if you need to treat as (or check if) the nodes are in a sorted linear order.

function inOrderTraversal(node) {
  if (node !== null) {
    inOrderTraversal(node.left);
    visitNode(node);
    inOrderTraversal(node.right);
  }
}

Pre-Order Traversal

Pre-order traversal will always visit the current node before visiting its children. The root is the first node visited. The it follows the left path and visits each node as it encounters them. Afterwards, it follows the right paths and still visits the nodes as it encounters them before continuing on with the path.

Use this if you want to explore a given level before reaching the leaf node of a path.

function preOrderTraversal(node) {
  if (node !== null) {
    visitNode(node);
    preOrderTraversal(node.left);
    preOrderTraversal(node.right);
  }
}

Post-Order Traversal

For post-order traversal, you visit a node's children before visiting that node. This means that you will use it when you want to reach the leaves first. You visit the entire left subtree, then the entire right subtree, and then the root node of the subtree.

function postOrderTraversal(node) {
  if (node !== null) {
    postOrderTraversal(node.left);
    postOrderTraversal(node.right);
    visitNode(node);
  }
}

Breadth-First Search

With breadth-first search (BFS) you use a queue data structure instead of a stack. It traverses across each level before going deeper into the graph.

We'll explore BFS further in the graph section as well.

// Using a dynamic array as a queue
// unshift == enqueue
// pop == dequeue
function breadthFirstSearch(root) {
  let currentNode = root;
  let queue = [currentNode];

  while(queue.length > 0){
    currentNode = queue.pop();

    visitNode(currentNode)

    if(currentNode.left !== null) {
      queue.unshift(currentNode.left);
    }

    if(currentNode.right !== null) {
      queue.unshift(currentNode.right);
    }
  }
}
Prev
Trees
Next
Binary Search Trees
Loading...

Table of Contents