Tree data structures in JavaScript

Subscribe to my newsletter and don’t miss my upcoming articles

  • Trees are an interesting data structure. It has a wide range of applications in various fields. Such as:
    • The DOM is a tree-like data structure
    • Directories and files in our operating system can be represented as trees
    • A family hierarchy can be represented as a tree.

Many variants of trees (such as heap, BST, and so on) can be used to solve problems related to scheduling, image processing, databases, and so on. Many complex problems that at first glance seem unrelated to trees can actually be represented as a tree. We will also tackle these issues (later in this series) to see how trees can be used to make seemingly complex problems easier to understand and solve.

If you want more posts in this series, don’t forget to subscribe to my message (subscription should be at the top of this article).

introduce

The implementation of nodes in a binary tree is very simple

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)
Copy the code

So these lines of code will create a binary tree for us, as follows:

           2  
        /      \
       /         \
     1            3
   /   \        /    \
null  null   null   null

Copy the code

Good job! So it’s easy. Now, how do we use it?

traverse

Let’s start by trying to traverse these connected tree nodes (or trees). Just as we can iterate over a set of numbers, it would be interesting if we could “iterate” over a tree node. However, trees are not linear data structures like arrays, so there is more than one way to traverse these. We can roughly divide traversal methods into the following categories:

  • Breadth-first traversal
  • Depth-first traversal

Breadth-first search/traversal (BFS)

In this approach, we walk the tree layer by layer. We’ll start at the root, then cover all of its children, then cover all of its 2 children, and so on. For example, for the tree above, traversal would result in the following:

2,1,3
Copy the code

Here’s an illustration of a slightly more complex tree to make it easier to understand:

To achieve this form of traversal, we can use a queue (first-in, first-out) data structure. Here’s what the whole algorithm looks like:

  1. Start a queue containing root
  2. Removes the first item from the queue
  3. Queues the left and right children of the pop-up item
  4. Repeat steps 2 and 3 until the queue is empty

Here is the algorithm after 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)
   }
}
Copy the code

We can slightly modify the above algorithm to return an array array, where each inner array represents a level containing elements:

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
}

Copy the code

Depth-first search/Traversal (DFS)

In DFS, we take a node and continue exploring its children until we run out of depth. It can be done in one of the 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
Copy the code

All of these traversal techniques can be implemented recursively and iteratively. Let’s get into the implementation details:

The former sequence traversal

This is what a tree traversal looks like:

Tip:

We can use this simple technique to manually find the prior traversal of any tree: Walk the entire tree from the root node, keeping yourself to the left.

Implementation:

Let’s delve into a practical implementation of this traversal. The recursive approach is pretty straightforward.

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.right)
}

Copy the code

The iterative approach to sequential traversal is very similar to BFS, except that we use a stack instead of a queue and we push the right child onto the stack first:

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.right)
}
Copy the code

Orderly traversal

Here’s what the InOrder traversal of a tree looks like:

root node -> left node -> right node
Copy the code

Tip:

We can manually find the InOrder traversal of any tree using this simple technique: place a plane mirror horizontally at the bottom of the tree and get a projection of all the nodes.

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)
}
Copy the code

Iteration: This algorithm may seem a little mysterious at first. But it’s pretty straightforward. Let’s look at it this way: in the InOrder traversal, the leftmost child is printed first, then the root, then the child on the right. So the first thought was to come up with something like this:

const curr = root

while(curr){
  while(curr.left){
    curr = curr.left // get to leftmost child
  }

  console.log(curr) // print it

  curr = curr.right // now move to right child
}

Copy the code

In the above method, we cannot backtrack, that is, return the parent that caused the leftmost node. So we need a stack to keep track of this. Therefore, our revised methodology may look like this:

const stack = []
const curr = root

while(stack.length || curr){
  while(curr){
    stack.push(curr) // keep recording the trail, to backtrack
    curr = curr.left // get to leftmost child
  }
  const leftMost = stack.pop()
  console.log(leftMost) // print it

  curr = leftMost.right // now move to right child
}

Copy the code

Now we can use the above method to formulate the final iterative algorithm:

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

Copy the code

After the sequence traversal

Here’s what a back-order traversal of the tree looks like:

 left node -> right node -> root node
Copy the code

Tip:

Quick manual post-order traversal for any tree: Extract all leftmost leaf nodes one by one.

Implementation:

Let’s delve into a practical implementation of this 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)

}
Copy the code

Iteration: We already have an iterative algorithm for prior traversal. Can we use that? Since the post-order traversal seems to be the opposite of the pre-order traversal. Let’s take a look:

// PreOrder:
root -> left -> right

// Reverse of PreOrder:
right -> left -> root

// But PostOrder is:
left -> right -> root
Copy the code

Ah! So it’s a little bit different. But we can do this by modifying our pre-order traversal a little bit, and then reversing it should give us the post-order traversal. The overall algorithm will be:

// record result using 
root -> right -> left

// reverse result
left -> right -> root
Copy the code
  • Using a similar approach to the iterative preOrder algorithm above, use temporarystack.
    • The only exception is that we goroot -> right -> leftRather thanroot -> left -> right
  • Continue recording the traversal sequence in the arrayresult
  • reverseresultGive a post-order traversal
function walkPostOrder(root){
  if(root === null) return []

  const tempStack = [root], result = []

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

      result.push(last)

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

    return result.reverse()
}
Copy the code

Finally: JavaScript tips

If only we could traverse the tree as follows:

for(let node of walkPreOrder(tree) ){
   console.log(node)
 }
Copy the code

It looks really nice and easy to read, doesn’t it? All we need to do is use a walk function, which returns an iterator.

Here’s how we modified the functions above walkPreOrder to work with the shared example 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)
   }
}

Copy the code