BST Traversal

Given a Binary Search Tree, Traverse the tree in Preorder, Postorder, and inorder traversal.

Recursive approach

The traversal mechanism are simple and straightforward. We are going to take a recursive approach and print the traversals accordingly.

The base case in each of the traversing mechanisms will be when there is no tree to traverse, i.e. tree === null. This ensures that we are at the leaf nodes (since we are going to backtrack from here and going to proceed with the subsequent calls).

Preorder traversal.

Since the traversal has to be in a root-left-right manner, we are going to print the root value first.

  1. If !tree - return.
  2. Print root value.
  3. Traverse root.left
  4. Traverse root.right

Postorder traversal.

Since the traversal has to be in a left-right-root manner, we are going to print the root value first.

  1. If !tree - return.
  2. Traverse root.left
  3. Traverse root.right
  4. Print the root value

Inorder traversal.

Since the traversal has to be in a left-root-right manner, we are going to print the root value first.

  1. If !tree - return.
  2. Traverse root.left
  3. Print root value.
  4. Traverse root.right

In all the above mentioned traversal methods, it's the order in which the values are printed. The printing and recursion order will determine which traversing mechanism is applied in place.

Time Complexity

  • O(n) - In all the cases since we are going to visit each node atleast once.
Solve BST Traversal on Algochurn

Practice all the solutions below

Practice the most popular front-end questions asked in coding interviews with   Frontend Churn