Binary Search Tree: Program to search a node using recursive approach

Find a node with a given data in a BST and return it if the node with the data exists else we return NULL.

We use the BST Properties

All Nodes to the left of the current node has lower data than the current node
All Nodes to the right of the current node has greater data than the current node

Searching a node in a BST recursively requires two functions

1. Used to pass the initial data to the Recursive Function
  The Recursive callback function is called and the root and dataToSearch is passed to it as parameters
2. Main Recursive callback function which will be used to compare and find the node having dataToSearch,
this function implements the below algorithm and returns the node having data equal to dataToSearch

Algorithm

findNodeCallback(dataToSearch, node):

1. If node is null return null
2. If dataToSearch is equal to data, then dataToSearch is found and so return the node
3. If dataToSearch is less than data of node return callback(dataToSearch, left of node)
4. Else return callback(dataToSearch, right of node)

In the Above Algorithm, the findNodeCallback is called by passing dataToSearch and the root of the tree.

Complexity

Average Case Time Complexity: O(LogN)
Worst Case Time Complexity: O(N)
Auxiliary Space Complexity: O(Height of Tree)

The Time Complexity heavily depends on the structure of the given tree,
if the given tree is balanced then the time complexity will be O(logN) and for a skew tree the time complexity will be O(N)

Space Complexity is O(Height of Tree) 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;
        
        // 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;
            }
          }
        }
        
        Node findNodeRecursively(int dataToSearch) {
          // For recursive function, we generally require a call back function
          // The call back function is used to pass required parameters
          // In below we pass dataToSearch and root as parameter for the recursive function
          return findNodeRecursivelyCallBack(dataToSearch, root);
        }
        
        Node findNodeRecursivelyCallBack(int dataToSearch, Node root) {
          // If root is null it means that dataToSearch does not exist in the given tree
          if (root == null) {
            return null;
          }
        
          // If dataToSearch is equal to the root data then return the root
          // if dataToSearch is less than the root data then recursively go to left and return the value of it
          // if dataToSearch is greater than the root data then recursively go to right and return the value of it
          if (dataToSearch == root.data) {
            return root;
          } else if (dataToSearch < root.data) {
            return findNodeRecursivelyCallBack(dataToSearch, root.left);
          } else {
            return findNodeRecursivelyCallBack(dataToSearch, root.right);
          }
        }
        
        public static void main(String[] args) {
          int[] nums = { 8, 2, 6, 12, 11, 10 };
        
          BinarySearchTree bst = new BinarySearchTree();
          bst.insertArray(nums);
        
          if (bst.findNodeRecursively(12) != null) {
            System.out.println("Data 12 found in the BST");
          } else {
            System.out.println("Data 12 not found in the BST");
          }
        
          if (bst.findNodeRecursively(9) != null) {
            System.out.println("Data 9 found in the BST");
          } else {
            System.out.println("Data 9 not found in the BST");
          }
       }
  } 

Output

Data 12 found in the BST
Data 9 not found in the BST