Search In BST

Easy
0/40
Average time to solve is 15m
profile
Contributed by
88 upvotes
Asked in companies
LinkedInAckoErnst & Young (EY)

Problem statement

There is a Binary Search Tree (BST) consisting of ‘N’ nodes. Each node of this BST has some integer data.


You are given the root node of this BST, and an integer ‘X’. Return true if there is a node in BST having data equal to ‘X’, otherwise return false.


A binary search tree (BST) is a binary tree data structure that has the following properties:

1. The left subtree of a node contains only nodes with data less than the node’s data.

2. The right subtree of a node contains only nodes with data greater than the node’s data.

3. The left and right subtrees must also be binary search trees.
Note: 
It is guaranteed that all nodes have distinct data.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains two positive integers ‘N and ‘X’, denoting the number of nodes in the BST and a given integer.

The second line contains the tree elements separated by a single space in the level order form. If any node has no left or right child, we take -1 in its place. Refer to the example below for further clarification.

For example, the input for the tree depicted in the below image would be :

image

4
2 6
1 3 5 7
-1 -1 -1 -1 -1 -1 -1 -1

Explanation :

Level 1 :
The root node of the tree is 4

Level 2 :
Left child of 4 = 2
Right child of 4 = 6

Level 3 :
Left child of 2 = 1
Right child of 2 = 3
Left child of 6 = 5
Right child of 6 = 7

Level 4 :
Left child of 1 = null (-1)
Right child of 1 = null (-1)
Left child of 3 = null (-1)
Right child of 3 = null (-1)
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null (-1).
Note: 
The above format was to provide clarity on how the input is formed for a given tree. 

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

4 2 6 1 3 5 7 -1 -1 -1 -1 -1 -1 -1 -1
Output Format: 
Print “True” if there is a node in BST having data equal to ‘X’, otherwise, print “False”.

Output for every test case will be printed in a separate line.
Note: 
You don’t need to print anything; It has already been handled. Just implement the function.
Sample Input 1:
7 8
4 2 6 1 3 5 7 -1 -1 -1 -1 -1 -1 -1 -1
Sample Output 1:
False
Explanation For Sample Input 1:
There is no node having data 8. See the problem statement for the picture of this BST.
Sample Input 2:
4 1
3 1 5 -1 2 -1 -1 -1 -1
Sample Output 2:
True
Explanation For Sample Input 1:
There is a left node, and it has data 1. Thus, we should print ‘True’.
Constraints:
1 <= N <= 10000
0 <= X <= 10^9
0 <= DATA <=10^9

Where ‘N’ is the number of nodes in the BST, ‘X’ is a given integer and ‘DATA’ is the data contained in each node of BST.

Time limit: 1 sec
Hint

Can you use the property of the binary search tree to solve this problem ?

Approaches (2)
Recursive Approach

Approach: If the root node has data smaller than ‘X’. then by properties of BST, ‘X’ cannot be in its left subtree, so we recursively check for the right subtree. 

If the root node has data larger than ‘X’. then by properties of BST, ‘X’ cannot be in its right subtree, so we recursively check for the left subtree.

If the root node has data equal to ‘X’, then we return “True”. 

 

The steps are as follows:

  1. If the root node is NULL, then return “False”.
  2. If the ‘DATA’ of the root node equals ‘X’, then return “True”.
  3. If the ‘DATA’ of the root node is smaller than ‘X’, then recur for the right subtree by calling this method on the right child of the root.
  4. If the ‘DATA’ of the root node is larger than ‘X’, then recur for the left subtree by calling this method on the left child of the root.
Time Complexity

O(H), where 'H' is the height of the given BST.


 

In each recursive step, the height of the BST pass in method will reduce by 1. Thus if ‘H’ is the height of this BST then at most it takes O(H) times.  Note ‘H’ can be ‘N’ if the tree is completely skewed, and log(N) if the tree is balanced.

Space Complexity

O(H),  where 'H' is the height of the given BST.


Recursion stack takes O(H) space.

Code Solution
(100% EXP penalty)
Search In BST
Full screen
Console