Binary Tree Traversal in JS— Preorder, Postorder and Inorder

Three common ways to traverse a binary tree (which according to Cracking the Coding Interview you should know how to implement prior to your interviews) are preorder, inorder, and postorder traversal.

At a high level the definitions of each of these types of traversal are as follows:

Preorder:

1. Visit (often process or print) the root node
2. Traverse the left subtree
3. Traverse the right subtree

Inorder (most common):

1. Traverse the left subtree
2. Visit the root node
3. Traverse the right subtree

Postorder:

1. Traverse the left subtree
2. Visit the root node
3. Traverse the right subtree

You can find a really intuitive explanation of these 3 traversals in Back to Back SWE’s Youtube video Binary Tree Bootcamp: Full, Complete, & Perfect Trees Preorder, Inorder, & Postorder Traversal here:

One of the explanations that made it really click for me is the idea that each of these relationships (preorder, inorder and postorder) simply explains the order at which you “visit” the current node. If we are using a recursive function, these relationships can be thought of as a policy executed at each successive node.

For example, consider the below tree:

Input: root = [1,null,2,3]
Output: [1,3,2]

If we were to do an in order traversal of the above, our input and expected output would look like this:

Input: root = [1,null,2,3]
Output: [1,3,2]

How? Well let’s walk through the inorder traversal:

• start at node 1: check if there is a left node. There is not, so visit node 1 and then travel to right node, node 2.
• node 2: check if there is a left node. There is. travel to left node, node 3.
• node 3: check if there is a left node. There is not. visit node 3. check if there is a right node. There is not. travel back to node 2, which was not yet visited.
• node 2: we already traveled to node 2’s left node, so now we visit node 2. Check if there is a right node. There is not and our output / traversal is complete.

After completing these steps, you can see that we get an output of the order of our visited nodes [1, 3, 2].

As you can start to see in the above walk through, the general idea in the traversal is choosing when to visit a node and when to travel to a neighboring one. The traversal becomes a recursive process of checking “is there a left node?” If so, travel to it. If no left node, visit current node [and in the above case, add it to the output]. Then check if there is a right node, if there is, travel to it and repeat the above process (this is where you can think of the process as a sort of rule or policy executed recursively at each node).

Recursive preorder and post order traversals will follow a similar check and visit sequence, just in different orders.

Putting these all into code, below are solutions to the leetcode problems for preorder, inorder and postorder traversal of a binary tree.

You can see how similar each solution is, with the difference consisting of simply changing the order of the lines in the traversal function. The following implementations all pass Leetcode’s version of these traversal problems:

Each of these can also be solved iteratively with a stack data structure instead of a recursive function.

Hope this helps!