Algorithms 101: how to implement Tree Traversal in JavaScript

Understanding algorithms is important for every software developer to have. Algorithms are a common part of any coding interview, whether you are solving problems in JavaScript, Java, or Python. You can utilize algorithms to ace coding interviews, land a job, or solve peculiar problems at work.

Today’s tutorial would focus on algorithms for traversing elements in a tree. Tree traversal looks different in different programming languages; we will be using JavaScript. We start by refreshing our knowledge about trees. Next, we will learn some useful algorithms and look at some common interview questions.

This guide at a glance:

• What are trees?
• How to traverse trees
• Common interview questions

Get hands-on interview practice in JavaScript

In this curated learning path, you’ll cover everything from Data Structures to System Design.

Ace the JavaScript Coding Interview

What are trees?#

In computer science, trees are non-linear data structures represented as a collection of nodes connected by edges. Each node stores data of any type, and all nodes in a tree are the same data type.

Tree data structures are typically used to store information while preserving its hierarchy, for implementing quick searches, networking, and inheritance.

The basic components of a tree includes:

• The root, which is the top-most node (it has no parent node). This is typically the starting point of your tree.
• The parent node, which is connected downwards to one or two nodes.
• The child node, which has an incoming link (or connecting edge) from a parent node above it.
• Sibling nodes are nodes that share the same parent.
• The leaf nodes have parent nodes but no children nodes. They are typically the base/bottom nodes.
• A subtree is a tree held within a larger tree.
• The degree of a node refers to the number of subtrees within a tree.
• The depth of a tree refers to the number of edges between a specific node and the root.
• The height of a node refers to the number of edges in the longest path from a specified node to a leaf node.

Traversal in N-ary or General Trees#

Not all trees are binary — many real-world trees (like DOM structures or file systems) have multiple children per node. Traversing these general trees requires slightly different logic.

Recursive Preorder Traversal#

Here’s a basic recursive traversal in JavaScript:

function traverseGeneralTree(root) {
  if (!root) return;
  console.log(root.value); // Pre-order position
  for (const child of root.children) {
    traverseGeneralTree(child);
  }
}

To make it postorder, simply move the console.log after traversing the children.

Breadth-First Traversal (Level Order)#

Use a queue to traverse the tree level by level:

function breadthFirstGeneral(root) {
  const queue = [root];
  const result = [];
  while (queue.length) {
    const node = queue.shift();
    result.push(node.value);
    if (node.children) {
      for (const c of node.children) queue.push(c);
    }
  }
  return result;
}

Why It Matters#

Mastering traversal in general (N-ary) trees broadens your problem-solving ability beyond binary trees. It’s directly applicable to:

• DOM traversal
• File system hierarchies
• Organization charts
• Dependency graphs

These traversal patterns are building blocks for many real-world algorithms.

How to traverse trees#

A traversed tree is one in which every node on the tree has been visited. Traversal is a process involving iterating over all nodes in a certain manner.

Unlike linear data structures (such as Arrays, Linked Lists, or Queues) which have only one logical way to traverse them with recursion, trees can be traversed in different ways. Generally there are 2 iterative ways for traversing trees:

• Depth-first Search/Traversal (DFS)
• Breadth-first Search/Traversal (BFS)

Depth-first Traversal#

Depth-first traversal involves traversing a tree from top to bottom. They are implemented in a FILO manner (First In Last Out), like the stack data structure. The left sub-trees are traversed first, then the right sub-trees.

This is commonly seen when traversing a binary tree. Binary Trees are trees where each node has at most 2 child nodes. In the tree below, the node with the value 1 would be the first to be pushed into a stack, followed by the nodes with values 2, 3, and 4, then it goes back to the top to the node with the value 5 down.

When the end of the tree is reached, the values are popped off the stack back into the tree.

There are 3 types of Depth-first traversal:

1. In-Order Traversal#

In in-order traversal, we traverse the left child and its sub-tree(s), then we visit the root and then traverse the right child and its sub-tree(s). It takes a “left-root-right” order.

Before we take a look at a code sample for this algorithm, let’s try to outline the steps involved:

• Starting at the root node, we traverse the left node and its sub-trees recursively
• We start reading from the left leaf node, followed by its parent and sibling node
• We do this recursively until we get back to the root node, then we repeat the process for the right node, starting our reading from its leftmost leaf node

In our implementation, we create an object named BST of the BinarySearchTree class and insert some values into it. We will then pass the object’s root to the inOrderPrint() function as a starting point to the traversal.

If the node passed into the function is not null, this function calls inOrderPrint() recursively on the left child first, i.e., the left subtree, and then prints the value at the node. Then it calls the inOrderPrint() recursively on the right child, i.e., the right subtree.

The node will print its own value once all the subsequent calls to the left subtree have been executed.

When the recursive calls will hit the null nodes, they will return from the function without doing anything.

2. Pre-Order Traversal#

Pre-Order traversal reads the nodes in a tree in a level-by-level order, left-child before right-child. The elements are read in a “root-left-right” order.

The algorithm for pre-order traversal, starting from the root node, is as follows:

• Visit the currentNode and display the data
• Traverse the left subtree of currentNode recursively
• Traverse the right subtree of currentNode recursively

Now let’s review the code for pre-order traversal.

We create a new object of the BinarySearchTree class and insert values into it. We then pass the root node to the preOrderPrint() function.

This function prints the value of the node, then it is recursively invoked for the left child. When the nodes in the left sub-tree have been visited, it is recursively invoked for the right child and its sub-trees.

When the recursive calls reach the null nodes, they will return from the function without doing anything.

3. Post-Order Traversal#

The last strategy for traversing a tree is the Post-Order traversal. Here, we traverse the left sub-tree, then the right subtree before we visit the root node. It takes a “left-right-root” order.

The steps involved for post-order traversal are as follows:

• Traverse the left subtree of currentNode recursively
• Traverse the right subtree of currentNode recursively
• Visit the currentNode and print its value

Again, we create an object named BST and insert values into it. We will then pass the root node to the postOrderPrint() function as a starting point to the traversal.

If the node passed into the function is not null, this function calls postOrderPrint() on the left child first and then on the right child. Lastly, it prints the value of the currentNode.

The value of a parent node or the root node will only be printed once all the calls have been executed.

Iterative Traversal with Stack (Avoiding Recursion)#

While recursion is elegant, JavaScript’s call stack is limited, and for deep or skewed trees, recursion can lead to stack overflow. To handle such cases efficiently, you can use an explicit stack to perform preorder, inorder, or postorder traversals iteratively.

Example: Iterative In-Order Traversal#

function iterativeInOrder(root) {
  const stack = [];
  let current = root;
  const result = [];

  while (current !== null || stack.length) {
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    result.push(current.value);
    current = current.right;
  }
  return result;
}

Other Traversal Variants#

• Preorder traversal: Push the right child, then the left child, so the left is processed first.
• Postorder traversal: More complex — you can either:
  • Use a second stack to reverse the traversal order, or
  • Perform a modified preorder and reverse the result at the end.

Why It Matters#

Using iterative approaches helps your implementation:

• Scale to very deep trees without hitting recursion limits.
• Control the traversal stack explicitly for optimization or debugging.
• Stay compatible across runtimes where recursion depth is limited.

These patterns are especially useful in interview problems or production systems handling large or unpredictable tree structures.

Morris In-Order Traversal (Threaded, O(1) Space)#

If you want to push optimization further, you can traverse a binary tree in in-order without recursion and without extra memory (no stack). This is called Morris traversal. The idea is to temporarily “thread” null right pointers to their in-order successor, then revert those changes as you go.

Outline:

1. Initialize current = root.

2. If current.left is null, visit current and move to current.right.

3. Else, find the predecessor (rightmost node in current.left subtree).

   • If predecessor.right is null, set predecessor.right = current (thread), then current = current.left.

   • Else predecessor.right == current (thread exists), revert it (set predecessor.right = null), visit current, then current = current.right.

This gives you in-order traversal with O(1) extra space (apart from variables), though it mutates pointers temporarily.

Level-Order (Breadth-First) Traversal#

With level-order traversal, trees are traversed level-wise. This means that we visit every node on a level from left to right before going to a lower level. All child nodes are traversed before the next level of grandchildren nodes.

This is similar to breadth-first search from graph algorithms.

In level-order traversal, we utilize a queue to store a reference to the node(s) we want to visit. This ensures that we can traverse the tree left-to-right on the same level.

When traversing the tree above, the root node would be the first to be placed in a queue, then the node with the value 12, then 18, 14, 16 and 20. The output would be:

[10,12,18,14,16,20]

Use Cases, Complexity, and Pitfalls#

Knowing how to implement tree traversal in JavaScript is foundational, but knowing when and how well it works differentiates a good engineer.

• Time & Space Complexity: All standard traversals run in O(n) time (visit each node once). Recursive DFS uses O(h) auxiliary space (call stack depth), where h is tree height. Iterative stack methods also use O(h). Morris uses O(1) extra space (aside from output).

• Skewed Trees and Depth: If your tree is very unbalanced (degenerates to a list), recursion depth may lead to stack overflow. Prefer iterative or Morris in such cases.

• Handling nulls / missing children: Always check for null children before recursing or enqueueing.

• Mutable trees: If your traversal mutates the tree (as in Morris), be careful to revert changes so future operations aren’t broken.

• Use in algorithms: Traversals power tasks like validating BSTs (inorder must be sorted), serializing/deserializing trees, evaluating expression trees, searching hierarchies like DOM, or algorithms that depend on postorder calculations (e.g. computing subtree sizes).

By combining multiple techniques and understanding complexity and limitations, your toolkit for how to implement Tree Traversal in JavaScript becomes much stronger.

Common interview questions#

That concludes what we need to know about tree traversal algorithms. The following are common coding interview questions about tree traversals that you should study:

• Find Nodes at “k” Distance from the Root.
• Check if given Preorder, In-order and Post order traversals are of the same tree.
• Print postorder traversals from given Preorder traversals.
• Implement Pre-order traversal without using recursion
• Can you do iterative Preorder traversal of a binary tree without recursion?
• What are advantages and disadvantages of BST?

You can continue learning about algorithms in JavaScript by visiting Educative’s learning path Ace the JavaScript Coding Interview. JavaScript continues to This path will take you through all that you need to know to crack your JavaScript interviews with confidence.

Happy learning!

Continue learning about JavaScript and algorithms#

• Acing the JavaScript Interview: top questions explained
• Algorithms 101: how to use Merge Sort and Quicksort in JavaScript
• 7 JavaScript data structures you must know