Search in a Binary Search Tree Leetcode Solution

In this problem, we are given a Binary Search Tree and an integer. We need to find the address of a node with value same as the given integer. As a check, we need to print the preorder traversal of the sub-tree that has this node as root. If there is no value same as the given integer in the tree, we need to return NULL, i.e, an empty tree.

Table of Contents

Example

     2
    
  /     \

1         3

             \

               4


Target Value = 3

3 4

     5

  /      \

1         10 


Target Value = 4

Empty BST

Explanation #1

BST contains a node with value 3, so we return its sub-tree and print its preorder traversal.

Explanation #2

BST doesn’t contain any node with value 4, so we return NULL and print “Empty BST”.

Approach(Recursive)

Let us think of how a problem depends on subproblem in this case. Let say our function returns the address of node with target value, if found. We start from the root of the tree. If this node is NULL, it is obvious we have reached the end of the binary search tree and hence there is no node with target value. So, we return NULL. Similarly, we the node value is equal to the target value, we return this node. Otherwise, we know that the target-valued node will either be in left subtree or right subtree of current root. We can decide the direction(left or right) by comparing root.value and target value. So, we call the same recursive function with root as root.left or root.right.

Algorithm

Create a function searchBST() to return target address
If root is equal to null OR root has same value as that of the target:
- Return root
If root.value is greater than target value:
1. return searchBST(root.left , val)
Return searchBST(root.right , val)
Print the preorder traversal of target node

Implementation of Search in a Binary Search Tree Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int val)
    {
        value = val;
        left = right = NULL;
    }
};

void preorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    cout << root->value << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
    return;
}

BSTNode* searchBST(BSTNode* root , int val)
{
    if(root == NULL)
        return root;
    if(val == root->value)
        return root;
    if(val < root->value)
        return searchBST(root->left , val);
    return searchBST(root->right , val);
}

int main()
{
    BSTNode* root = new BSTNode(2);
    root->left = new BSTNode(1);
    root->right = new BSTNode(3);
    root->right->right = new BSTNode(4);
    int val = 3;
    BSTNode* targetNode = searchBST(root , val);
    if(targetNode == NULL)
    {
        cout << "Empty Tree" << '\n';
        return 0;
    }
    preorderTraversal(targetNode);
    return 0;
}

Java Program

class BSTNode
{
    int value;
    BSTNode left , right;
    BSTNode(int val)
    {
        value = val;
        left = right = null;
    }
}

class search_in_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(2);
        root.left = new BSTNode(1);
        root.right = new BSTNode(3);
        root.right.right = new BSTNode(4);
        int val = 3;
        BSTNode targetNode = searchBST(root , val);
        if(targetNode == null)
        {
            System.out.println("Empty Tree");
            System.exit(0);
        }
        preorderTraversal(targetNode);
    }

    static BSTNode searchBST(BSTNode root , int val)
    {
        if(root == null)
            return root;
        if(val == root.value)
            return root;
        if(val < root.value)
            return searchBST(root.left , val);
        return searchBST(root.right , val);
    }

    static void preorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        System.out.print(root.value + " ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return;
    }
}

3 4

Complexity Analysis of Search in a Binary Search Tree Leetcode Solution

Time Complexity

O(H), H = logN = Height of BST in average cases and O(N), N = size of the BST in worst cases. We traverse the tree once in the worst case which occurs when the BST in skewed.

Space complexity

O(H) in average cases as we use recursive calls to traverse every node. O(N) in worst case. One important note is that some compilers enable tail-recursion and in those cases, the space complexity becomes O(1).

Approach(Iterative)

Similar to the above approach, we can jump to left or right subtree if the target value is not present in current node, we can do it iteratively by assigning root = root.left or root = root.right at every iteration until root becomes null. If we find that the value of root is equal to target value at any iteration, we return that root. Otherwise, we return null.