In-order Traversal

Lets look at the 4 options to traverse a binary tree:

• Depth First Search

  • Pre-order
  • In-order
  • Post-order

• Breadth First Search

  • Level-order

In this post, let’s explore In-order traversal.

Visualise how it traverse

We first visit the Left Subtree, then the Root and lastly, the Right subtree.

               20
             /    \
          /         \
        100         3
      /     \     /   \
    50      15  250   35
  /
222

r = root
lt = left subtree
rt = right subtree

1. (lt)r(rt)
2. (lt)20(rt)
3. ((lt)r(rt))20(rt)
4. ((lt)100(rt))20(rt)
5. (((lt)r(rt))100(rt))20(rt)
6. (((lt)50(rt))100(rt))20(rt)
7. (((222)50)100(rt))20(rt)
8. (((222)50)100(15))20(rt)
9. (((222)50)100(15))20((lt)r(rt))
10. (((222)50)100(15))20((lt)3(rt))
11. (((222)50)100(15))20((250)3(35))

Answer: 222, 50, 100, 15, 20, 250, 3, 35

Code Algorithm

Here’s the code example to implmenent a In-ordertraversal.

type BinaryNode = {
  val: string;
  left?: BinaryNode;
  right?: BinaryNode;
};

function inOrder(root: BinaryNode): void {
  if (!root) throw new Error();

  inOrder(root.left);
  console.log(root.val);
  inOrder(root.right);
}