Traversing a Binary Search Tree in JS

You can find many articles and videos explaining how to traverse a tree but I couldn't find a good one. Especially one explaining how to do it in JavaScript. I hope that this article will prevent you from wasting countless hours on research.

Foundation

You can skip this section if you are already familiar with trees.

So what is a tree? A tree is simply a collection of nodes following special rules:

• Every tree has one root node (it's possible that they don't have one in theory but you'll never see it unless you decide to do get a Ph.D. in algorithms and data structure 😊)
• The root node has 0 or more children
• Each child also has 0 or more children
• A tree can't contain a cycle

You now know the basics of how trees work. You're maybe asking yourself "But what is a binary search tree?". A binary search tree is a specific tree that follows an extra rule: every child on the left of a node is smaller than the root node and every child on the right is bigger than the root node.
Here is an example:

You can see that when looking at the node with the value 3 that its left child's value is 1 which is smaller than 3. The root node's right child has the value 6 which is larger than 3.

Okay, let's go to the fun part now: the traversal algorithms🥰. There are three of them:

In-Order Traversal

This gif is awesome for explaining what in-order traversals are:

As you can see the principle is to first look at the left branch, then the node, and finally the right branch. Also, note that the resulting array is sorted in ascending order.

Here is what the code to do an in-order traversal looks like when using JavaScript:

var inorderTraversal = function(root) {
//Creating the array that will store the results from our traversal
    let result= []
    function traverse(root){
//return if there are no root node
        if(!root) return 
//Traverse the left branch to find the "leftest" node
        traverse(root.left)
//Once you found the "leftest" node add it to the array
        stack.push(root.val)
//Traverse the right branch 
        traverse(root.right)
    }
    traverse(root)
    return result
};

I hope this clarified things for you. If you want to check if you understood the code properly you can test yourself and do leetcode#94.

Pre-Order Traversal

Here is another awesome gif:

As you can see pre-order Traversals are similar to in-order traversals but they are different in that they first look at the root then at its child nodes (from left to right again).

Here is the code for pre-order Traversals:

var preorderTraversal = function(root) {
    let result  = []
    function traverse(root) {
        if(!root) return
        result.push(root.val)
        traverse(root.left)            
        traverse(root.right)

    }
    traverse(root)
    return result
};

As you can see almost nothing has changed besides the order of operations in our traversal. Again you can check your skills using leetcode.

Post-Order Traversals

Our final great gif:

Post-order traversals start with the right branch, then look at the left branch, and finally at the root.

Here is the code:

var postorderTraversal = function(root) {
    let result  = []
    function traverse(root) {
        if(!root) return
        traverse(root.left)
        traverse(root.right)
        result.push(root.val)
    }
    traverse(root)
    return result

};

The code is again very similar besides that we now look at the root last. You can check your understanding with this leetcode link.

Summary

The best way to remember the names of the different traversals is to remember that:
In-order traversals are: Left-Root-Right
Pre-order traversals are: Root-Left-Right
Post-order traversals are: Left-Right-Root

You can find me on Twitter if you have any questions or want to connect.

Comments

[Andrea Giammarchi]

let's make it like it's December 2021, shall we?

In-Order

const inorderTraversal = root => traverse(root, []);
const traverse = (root, stack) => {
  if (root) {
    traverse(root.left, stack);
    stack.push(root.val);
    traverse(root.right, stack);
  }
  return stack;
};

Pre-Order

const preorderTraversal = root => traverse(root, []);
const traverse = (root, stack) => {
  if (root) {
    stack.push(root.val);
    traverse(root.left, stack);
    traverse(root.right, stack);
  }
  return stack;
};

Post-Order

const postorderTraversal = root => traverse(root, []);
const traverse = (root, stack) => {
  if (root) {
    traverse(root.left, stack);
    traverse(root.right, stack);
    stack.push(root.val);
  }
  return stack;
};

[Richard Knoche (He/Him)]

Any feedback is welcome!

[Richard Knoche (He/Him)]

Should I add an iterative approach?