Binary Search Tree: Program to traverse using Preorder recursive approach

 Write a program to display the Preorder Traversal of a Binary Search Tree.
The Preorder of a Binary Search Tree: root, left subtree, right subtree

Applications of Preorder Traversal

1. Preorder traversal is a very important concept in BST as it can be used to solve many Recursion and Dp-related Problems.
2. And It can also be used in the Problems where we have to traverse the tree in the preorder Condition, such as Binary Expression Tree.

Preorder recursive requires two functions

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

Algorithm

1. If the node is null, return from the function
2. Print the data of the node
3. Call the preOrderCallback function recursively with the left of the node as a parameter
4. Call the preOrderCallback 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 preOrder traversal of the tree
        public void preOrder() {
          // preOrder traversal: root left right
          preOrderCallback(root);
        }
        
        public void preOrderCallback(Node node) {
          // If node is null return
          if (node == null) {
            return;
          }
        
          // Print the value of node
          System.out.print(node.data + " ");
         
          // Go to the left
          preOrderCallback(node.left);
        
          // Go to the right
          preOrderCallback(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 preOrder is right:
          // Check that if the data is printed in ascending order
          System.out.print("Pre Order traversal: ");
          bst.preOrder();
        }
        
  }

Output

Pre Order traversal: 8 2 6 12 11 10