Pre-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 Pre-order traversal.

Visualise how it traverse

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

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

r = root
lt = left subtree
rt = right subtree

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

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

Code Algorithm

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

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

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

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