Binary Tree Pre-order Traversal

Given a binary tree, print the nodes in pre-order format.

Recursive Approach

Pre-order traversal is a technique to systematically process all the nodes in a binary tree. The three steps included in a pre-order traversal are process the current node, move to the left child and recursively apply the pre-order process on the left subtree, and the move to the right child where the pre-order process is recursively applied on the right subtree.

const printPreOrder = (root) => {
  if (root === null)
    return;

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

The time complexity for pre-order traversal is O(n) where n is the number of nodes on the tree. this is because pre-order traversal processes each node with in the binary tree.

Iterative Approach

The iterative approach will accomplish the same goal. The general idea is to read the top item and push the children nodes onto a stack at every level. This process is repeatedly applied to the stack as long as it is not empty.

const printPreOrder = (root) => {
  const parents = [];
  parents.push(root);

  while (parents.length) {
    const cur = parent.pop();
    console.log(cur.val);

    if (cur.right)
      parents.push(cur.right);
    if (cur.left)
      parents.push(cur.left);
  }
}

The time complexity of the iterative approach is also O(n). Since the iterative approach explicitly uses a stack, space complexity would be O(h) where h is the height of the tree.