Binary Tree — DFS Traversing

A Binary tree is a data structure composed of nodes, each having at most two children. It is widely used in computer science and programming for various applications.

So In this article, we are going to learn how can we traverse a Binary tree.

There are various ways to traverse a Binary Tree. But we are going to focus on DFS which stands for Depth-First Search which is nothing but just a simple traversal algorithm used to explore or traverse a binary tree. It starts from the root node and explores as far as possible along each branch before backtracking.

There are three common ways to perform DFS on a binary tree:

• pre-order (Left subtree, root, right subtree)
• in-order traversal (Root, left subtree, right subtree)
• post-order traversal (Left subtree, right subtree, root)

Each traversal has its own specific use cases and can provide different orderings of node visits. The choice of traversal depends on the requirements of the specific problem or operation being performed on the binary tree.

So as we know much about a Binary Tree. We need to have a node to work on. So let’s quickly create a class for our Node Class

class MyNode {
  constructor(key) {
    this.key = key;
    this.left = this.right = null;
  }
}

1. In-order Traversal: In in-order traversal, the left subtree is visited first, then the root node, and finally the right subtree. This traversal results in the nodes being visited in ascending order when applied to a binary search tree (BST). In other words, in-order traversal visits nodes in their natural, sorted order.

Here is an example of In-order Traversal

/**
* @param {MyNode} node
*/
const printInorder = (node) => {
  if (node === null) {
    return;
  }
  printInorder(node.left);
  console.log(node.key, ' ');
  printInorder(node.right);
};

1. Pre-order Traversal: In pre-order traversal, the root node is visited first, followed by the left subtree, and then the right subtree. This traversal order is useful for creating a copy of a tree, as the root node is encountered first and can be easily replicated. Pre-order traversal is commonly used to create a prefix expression (also known as Polish notation) for mathematical expressions.

/**
 * @param {MyNode} node
*/
const printPreorder = (node) => {
  if (node === null) {
    return;
  }
  console.log(node.key, ' ');
  printPreorder(node.left);
  printPreorder(node.right);
};

1. Post-order Traversal: In post-order traversal, the left subtree is visited first, followed by the right subtree, and finally the root node. Post-order traversal is often used when deleting nodes from a tree, as it ensures that a node’s children are deleted before the node itself. It is also employed in evaluating postfix expressions.

/**
 * @param {MyNode} node
*/
const printPostorder = (node) => {
  if (node === null) {
    return;
  }
  printPreorder(node.left);
  printPreorder(node.right);
  console.log(node.key, ' ');
};

Yeah 🙌 !! we have covered all the DFS traversing algorithms.

Checkout this working example for what we just learn. https://stackblitz.com/edit/stackblitz-starters-ihubjf?file=index.js