Preorder traversal

1. Visit root node
2. Then go to all the nodes in the left subtree
3. Visit all the nodes in the right subtree

When to use? You can use pre-order traversal to create a copy of the tree, since you can access each node before its subtrees. It's also used to get expressions on an expression tree.

1display(root.data)
2preorder(root.left)
3preorder(root.right)

Note: This algorithm is equivalent to the famous graph algorithm Depth First Search (DFS).

xxxxxxxxxx

function preorderTraversal(root) {

  let res = [];

  helper(root, res);

  return res;

}

​

function helper(root, res) {

  if (!root) {

    return res;

  }

  res.push(root.val);

  helper(root.left, res);

  helper(root.right, res);

  return res;

}

​

const root = {

  val: 1,

  left: {

    val: 2

  },

  right: {

    val: 3

  }

};

​

console.log(preorderTraversal(root));