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.

If !tree - return.
Print root value.
Traverse root.left
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.

If !tree - return.
Traverse root.left
Traverse root.right
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.

If !tree - return.
Traverse root.left
Print root value.
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

#tree #Recursion #Tree Traversal #Google #Youtube #Salesforce #Intuit

Practice all the solutions below

JavaScript (Node.js 12.14.0)

Algochurn Theme

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

00:00:00

Expand Solution

BST Traversal

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

Consider the following Binary Tree

Binary Search Tree
                10
              /   \
            5       18
          /   \       \
        1       7      21

Preorder Traversal

When you traverse a tree in root->left->right fashion, it is called a preorder traversal. In the above example, the preorder traversal of the tree will be

10 5 1 7 18 21

Postorder Traversal

Here, the traversal order will be left->right->root. That is, left subtree is traversed first, then the the right subtree is traversed, and finally the root value is printed.

The postorder traversal of the above tree will be

1 7 5 21 20 18 10

Inorder Traversal

Here, the traversal order will be left->root->right. That is, left subtree is traversed first, then the root value is printed, and finally the right subtree is printed.

The postorder traversal of the above tree will be

1 5 7 10 18 21

The inorder traversal of a BST always returns value in a sorted order.

Constraints

0 <= N <=1000;
N = Node value in a Binary Tree.

Stuck? Check out hints

Recursion is your best friend. The easiest way to solve this problem is to use recursion and finalize the order in which the recursion will happen. When do you think the value should be printed in each case?

Pay attention to the printing order. For example, in preorder, you have to print the value first, then traverse the left subtree and finally the right subtree. How do you use recursion to accomplish this?

Uploaded by: Manu Arora

Share this problem on

#tree #Recursion #Tree Traversal #Google #Youtube #Salesforce #Intuit

BST Traversal

Recursive approach

Preorder traversal.

Postorder traversal.

Inorder traversal.

Time Complexity

Practice all the solutions below

BST Traversal

Consider the following Binary Tree

Preorder Traversal

Postorder Traversal

Inorder Traversal

Constraints

Stuck? Check out hints

Pages

Algochurn

Frontend Churn

Friends

Links