Binary Search Tree: Program to traverse using Inorder recursive approach

In this article, we will be going to write a program to Display the Inorder Traversal of a Binary Search Tree.
The Inorder of a Binary Search Tree: left subtree, root, right subtree

Applications of Inorder Traversal

1. Inorder traversal is a very important concept in BST as it can be used to solve many Recursion and Dp-related Problems.
2. Inorder has the property that it travels the Binary Search Tree in Sorted order.

Inorder recursive requires two functions

1. inorder(): The function is used to call the inorderCallback function and pass root as a parameter
2. inorderCallback(node): The Main Recursive callback function which uses the below algorithm to traverse
and print the nodes in Inorder.

Algorithm

1. If the node is null, return from the function
2. Call the inorderCallback function recursively with the left of the node as a parameter
3. Print the data of the node
4. Call the inorderCallback function recursively with the right of the node as a parameter

Complexity

Time Complexity: O(N)
Auxiliary Space Complexity: O(Height of Tree)

The Time Complexity will be O(N) as visit every node once, and the space complexity will be O(Height of Tree)
which is O(logN) for a perfect binary tree, the Space Complexity is because of the stack memory consumed
by the recursive calls.

Java Code

class BinarySearchTree {
        class Node {
          // Node class for Binary Search Tree
          int data;
          Node left, right;
        
          // Constructor to set the value of the node
          Node(int data) {
            this.data = data;
            this.left = null;
            this.right = null;
          }
        }
        
        private Node root = null;
        
        // Function to print the inorder traversal of the tree
        public void inorder() {
          // Inorder traversal: left root right
          inorderCallback(root);
        }
        
        public void inorderCallback(Node node) {
          // If node is null return
          if (node == null) {
            return;
          }
        
          // Go to the left
          inorderCallback(node.left);
        
          // Print the value of node
          System.out.print(node.data + " ");
        
          // Go to the right
          inorderCallback(node.right);
        }
        
        // Insert array of num into the BST
        public void insertArray(int nums[]) {
          for (int i = 0; i < nums.length; i++) {
            insert(nums[i]);
          }
        }
        
        // Insert a value in BST Iteratively
        public void insert(int data) {
          // Check if root is null,
          // if null then create a node and make it root
          if (root == null) {
            root = new Node(data);
            return;
          }
        
          // Start traversing from the root and find the position of node to insert
          Node current = root;
          while (current != null) {
            if (data < current.data) {
              // Insert the node if the position is empty
              if (current.left == null) {
                current.left = new Node(data);
                return;
              }
              current = current.left;
            } else {
              if (current.right == null) {
                // Insert the node if the position is empty
                current.right = new Node(data);
                return;
              }
              current = current.right;
            }
          }
        }
        
        public static void main(String[] args) {
          int[] nums = { 8, 2, 6, 12, 11, 10 };
        
          BinarySearchTree bst = new BinarySearchTree();
          bst.insertArray(nums);
        
          // To check if inorder is right:
          // Check that if the data is printed in ascending order
          System.out.print("Inorder traversal: ");
          bst.inorder();
       }
 }

OLutput

Inorder traversal: 2 6 8 10 11 12