BST In Order Traversal

BST Construction is covered here.

Sample tree:

           5
        /     \
       2       9
    /     \      \
    1     3       10

In Order traversal

The root element will be between the left and the right elements respectively.

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

Note: In order traversal of a BST results in a sorted list.

Recursive solution:

var traversal = []

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

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

Iterative solution:

Depth first search, using a stack.

var traversal = []

var stack = []

while (stack.length != 0 || root != null) {
  while (root != null) {
    stack.push(root)
    root = root.left
  }

  var node = stack.pop()
  traversal.push(node.val)
  root = node.right
}

Other BST traversals:


Written by Gagandeep Rangi who likes to talk about himself in third person. Twitter Instagram