Search in a Binary Search Tree Leetcode Solution


Difficulty Level Easy
Frequently asked in Apple IBM
Binary Search Tree

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.

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.

Search in a Binary Search Tree Leetcode Solution

Algorithm

  1. Create a function searchBST() to return target address
  2. If root is equal to null OR root has same value as that of the target:
    • Return root
  3. If root.value is greater than target value:
    1. return searchBST(root.left , val)
  4. Return searchBST(root.right , val)
  5. 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.

Algorithm

  1. Create a similar function searchBST() that returns address of target node
  2. While root is not null:
    • if root.value is equal to target value
      • return root
    • if root.val is greater than target value
      • Move to the right subtree as: root = root.right
    • else
      • Move to the left subtree as: root = root.left
  3. Return null
  4. 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)
{
    while(root != NULL)
    {
        if(root->value == val)
            return root;
        if(root->value > val)
            root = root->left;
        else
            root = root->right;
    }
    return NULL;
}

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)
    {
        while(root != null)
        {
            if(root.value == val)
                return root;
            if(root.value > val)
                root = root.left;
            else
                root = root.right;
        }
        return null;
    }

    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 = logN) in average cases and O(N) in worst cases(skewed BST) , same as the above approach.

Space complexity

O(1) as we use only constant memory space.

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions