BST Pre Order Traversal

BST Construction is covered here.

Sample tree:

           5
        /     \
       2       9
    /     \      \
    1     3       10

Pre Order traversal

The root element will come first, then the left child, then the right child.

[5, 2, 1, 3, 9, 10]

Recursive solution:

var traversal = []

function preorder(root) {
  if (root == null) return

  traversal.push(root.val)
  preorder(root.left)
  preorder(root.right)
}

Iterative solution:

Depth first search, using a stack.

var traversal = []

var stack = []
stack.push(root)

while (stack.length != 0) {
  var node = stack.pop()

  traversal.push(node.val)

  if (root.right) stack.push(root.right)
  if (root.left) stack.push(root.left)
}

Other BST traversals:

“If you only read the books that everyone else is reading, you can only think what everyone else is thinking.” - Murakami