Binary Tree (Recursive) traversal methods

There are three ways to traverse or visit all the nodes in a tree. They are:

In-order Traversal

This form of traversal works by visiting the left branch of the tree, then the current node, and then the right branch.

Below is an implementation of in-order traversal:

function inOrder(treeNode) {
  if (treeNode) {
    // explore left branch
    inOrder(treeNode.left);

    // visit/print current node
    console.log(treeNode.value);

    // explore right branch
    inOrder(treeNode.right);
  }
}

If we had a simple tree like the one above, with in-order traversal, the node values will be printed in this order:

[40, 20, 50, 10, 60, 30, 70]

Pre-order Traversal

This form of traversal works by first visiting the current node, then the left branch, and finally, the right branch.

Below is an implementation of pre-order traversal:

function preOrder(treeNode) {
  if (treeNode) {
    // visit/print current node
    console.log(treeNode.value);

    // explore left branch
    preOrder(treeNode.left);

    // explore right branch
    preOrder(treeNode.right);
  }
}

If we had a simple tree like the one above, with pre-order traversal, the node values will be printed in this order:

[10, 20, 40, 50, 30, 60, 70]

Post-order Traversal

This form of traversal works by exploring child nodes before the current node.

Below is an implementation of post-order traversal:

function postOrder(treeNode) {
  if (treeNode) {
    // explore left branch
    postOrder(treeNode.left);

    // explore right branch
    postOrder(treeNode.right);

    // visit/print current node
    console.log(treeNode.value);
  }
}

If we had a simple tree like the one above, with post-order traversal, the node values will be printed in this order:

[40, 50, 20, 60, 70, 30, 10]

In the example above, the values of the left and right sub-trees are printed before the root node

Thanks 👍 for making it to the end 👨‍💻 and I really hope you found the content useful.

Leave a comment below or tweet me @ElishaChibueze if you have any questions or suggestions