DEV Community

Cover image for Tree traversal techniques in JavaScript
Anish Kumar
Anish Kumar

Posted on • Updated on

Tree traversal techniques in JavaScript

Tree is an interesting data structure. It has wide variety of applications in all sorts of fields.
For example:

  • DOM is a tree data structure
  • Directory and files in our OS can be represented as trees
  • A family hierarchy can be represented as a tree.

There are bunch of variations of tree (such as heaps, BST etc.) which can be used in solving problems related to scheduling, image processing, databases etc. Many of complex problems may not seem related to tree on a quick look, but can actually be represented as one. We'll walk through such problems as well (in later parts of this series) to see how trees can make seemingly complex problems much easier to comprehend and solve.

Introduction

Implementing a Node for a binary tree is pretty straightforward.

function Node(value){
  this.value = value
  this.left = null
  this.right = null
}
// usage
const root = new Node(2)
root.left = new Node(1)
root.right = new Node(3)

Enter fullscreen mode Exit fullscreen mode

So these few lines of code would create a binary tree for us which looks like this:

        2  
      /  \
     1    3
   /        \
null       null
Enter fullscreen mode Exit fullscreen mode

Cool! So that was easy. Now, how do we put this to use?

Traversal

Let's start with trying to walk through these connected tree nodes (or a tree). Just as we can iterate through an array, it would be cool if we can 'iterate' through tree nodes as well. However, trees are not linear data structures like arrays, so there isn't just one way of traversing these. We can broadly classify the traversal approaches into following:

  • Breadth first traversal
  • Depth first traversal

Breadth First Search/Traversal (BFS)

In this approach, we traverse the tree level by level. We would start at the root, then cover all of it's children, and we cover all of 2nd level children, so on and so forth.
For example for the tree above, traversal would result in something like this:

2, 1, 3
Enter fullscreen mode Exit fullscreen mode

Here's an illustration with slightly complex tree to make this even simpler to understand:

BFS.png

To achieve this form of traversal we can use a queue (First In First Out) data structure. Here's how the overall algorithm would look like:

  1. Initiate a queue with root in it
  2. Remove the first item out of queue
  3. Push the left and right children of popped item into the queue
  4. Repeat steps 2 and 3 until the queue is empty

Here's how this algorithm would look like post implementation:

function walkBFS(root){
  if(root === null) return

  const queue = [root]
  while(queue.length){
      const item = queue.shift()
      // do something
      console.log(item)

      if(item.left) queue.push(item.left)
      if(item.right) queue.push(item.right)
   }
}
Enter fullscreen mode Exit fullscreen mode

We can modify above algorithm slightly to return an array of arrays, where each inner array represents a level with elements within in:

function walkBFS(root){
  if(root === null) return

  const queue = [root], ans = []

  while(queue.length){
      const len = queue.length, level = []
      for(let i = 0; i < len; i++){
          const item = queue.shift()
          level.push(item)
          if(item.left) queue.push(item.left)
          if(item.right) queue.push(item.right)
       }
       ans.push(level)
   }
  return ans
}
Enter fullscreen mode Exit fullscreen mode

Depth First Search/Traversal (DFS)

In DFS, we take one node and keep exploring it's children until the depth the fully exhausted. It can be done in one of following ways:

 root node -> left node -> right node // pre-order traversal
 left node -> root node -> right node // in-order traversal
 left node -> right node -> root node // post-order traversal
Enter fullscreen mode Exit fullscreen mode

All of these traversal techniques can be implemented recursively as well as iteratively. Let's jump into the implementation details:

Pre-Order traversal

Here's how PreOrder traversal looks like for a tree:

 root node -> left node -> right node 
Enter fullscreen mode Exit fullscreen mode

PreOrder visual.png

Trick:

We can use this simple trick to find out the PreOrder traversal of any tree manually: traverse the entire tree starting from the root node keeping yourself to the left.

preOrderTrick.png

Implementation:

Let's dive into actual implementation for such a traversal.
Recursive approach is fairly intuitive.

function walkPreOrder(root){
  if(root === null) return

  // do something here
  console.log(root.val)

  // recurse through child nodes
  if(root.left) walkPreOrder(root.left)
  if(root.right) walkPreOrder(root.left)
}

Enter fullscreen mode Exit fullscreen mode

Iterative approach for PreOrder traversal is very similar to BFS, except we use a stack instead of a queue and we push the right child first into the queue:

function walkPreOrder(root){
  if(root === null) return

  const stack = [root]
  while(stack.length){
      const item = stack.pop()

      // do something
      console.log(item)

      if(item.right) stack.push(item.right)
      if(item.left) stack.push(item.left)
   }
}
Enter fullscreen mode Exit fullscreen mode

In-Order traversal

Here's how InOrder traversal looks like for a tree:

root node -> left node -> right node 
Enter fullscreen mode Exit fullscreen mode

InOrder visual.png

Trick:

We can use this simple trick to find out InOrder traversal of any tree manually: keep a plane mirror horizontally at the bottom of the tree and take the projection of all the nodes.

Inorder trick.png

Implementation:

Recursive:

function walkInOrder(root){
  if(root === null) return

  if(root.left) walkInOrder(root.left)

 // do something here
  console.log(root.val)

  if(root.right) walkInOrder(root.right)
}
Enter fullscreen mode Exit fullscreen mode

Iterative:

function walkInOrder(root){
  if(root === null) return

  const stack = []
  let current = root

  while(stack.length || current){
      while(current){
         stack.push(current)
         current = current.left
      }
      const last = stack.pop()

      // do something
      console.log(last)

      current = last.right
   }
}
Enter fullscreen mode Exit fullscreen mode

Post-Order traversal

Here's how postOrder traversal looks like for a tree:

 left node -> right node -> root node 
Enter fullscreen mode Exit fullscreen mode

PostOrder visual.png

Trick:

For quick manual PostOrder traversal of any tree: pluck all the leftmost leaf nodes one by one.

PostOrder trick.png

Implementation:

Let's dive into actual implementation for such a traversal.

Recursive:

function walkPostOrder(root){
  if(root === null) return

  if(root.left) walkPostOrder(root.left)
  if(root.right) walkPostOrder(root.right)

  // do something here
  console.log(root.val)

}
Enter fullscreen mode Exit fullscreen mode

Iterative:

function walkPostOrder(root){
  if(root === null) return []

  const tempStack = [root], mainStack = []

  while(tempStack.length){
      const last = tempStack.pop()

      mainStack.push(last)

      if(last.left) tempStack.push(last.left)
      if(last.right) tempStack.push(last.right)
    }

    return mainStack.reverse()
}
Enter fullscreen mode Exit fullscreen mode

Bonus: JavaScript tip

How nice it would be if we could traverse the tree in one of following ways:

 for(let node of walkPreOrder(tree) ){
   console.log(node)
 }
Enter fullscreen mode Exit fullscreen mode

Looks really nice and pretty simple to read, isn't it? All we've got to do is use a walk function, which would return an iterator.

Here's how we can modify our walkPreOrder function above to behave as per the example shared above:


function* walkPreOrder(root){
   if(root === null) return

  const stack = [root]
  while(stack.length){
      const item = stack.pop()
      yield item
      if(item.right) stack.push(item.right)
      if(item.left) stack.push(item.left)
   }
}
Enter fullscreen mode Exit fullscreen mode

This article has been originally published at StackFull.dev. If you'd like to be notified when I drop more such articles, consider subscribing to the newsletter.

Discussion (0)