Find a value in BST

Easy
0/40
Average time to solve is 15m
profile
Contributed by
9 upvotes
Asked in companies
AdobeSAP LabsNVIDIA

Problem statement

You have been given a Binary Search Tree and a key value ‘X’, find if a node with value ‘X’ is present in the BST or not.

Note: 
You may assume that duplicates do not exist in the tree.
For example : 
For the given tree shown below:

Example

For the binary tree shown in the figure, if ‘X’ = 6, the output will be 1 as node value 6 is present in the BST.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T' which denotes the number of test cases.

The first line of each test case contains elements of the tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.

The second line of each test case contains an integer ‘X’ which denotes the key value to be searched in the binary search tree.
Output Format: 
For each test case, return true if the given key value exists in the binary search tree else return false.
Note: 
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
0 <= DATA <= 10^4
0 <= X <= 10^4

Where 'DATA' is the value of the binary tree node.

Time limit: 1 sec
Sample Input 1:
1
8 5 10 3 6 -1 14 -1 -1 -1 -1 13 -1 -1 -1
6
5 -1 -1
5
Sample Output 1:
1
1
Explanation of Sample Output 1:
In test case 1, the tree after the construction is shown below.

Example

Thus we can see that 6 is present in the tree.

In test case 2, there is only one node and we need to find the node with value 5 and thus it is present.
Sample Input 2:
 2
79 42 80 36 49 -1 90 -1 -1 -1 -1 85 100 -1 -1 -1 -1
49
710 340 800 210 390 -1 810 -1 -1 350 -1 -1 900 -1 -1 -1 -1
100
Sample Output 2:
1 
0
Explanation of Sample Input 2:
In test case 1, node value 49 is present in the tree hence output is 1.

In test case 2, node value 100 is not present in the tree so output is 0.
Hint

Make use of the properties of a Binary Search Tree.

Approaches (1)
Recursion

As we know, a Binary Search Tree has the following properties:

 

  • The left subtree of a node contains only nodes with values lesser than the node's value.
  • The right subtree of a node contains only nodes with values greater than the node's value.

 

Let findNode(TreeNode* <int> ‘ROOT’, int ‘KEY’) be a function which returns true if a node with value ‘KEY’ is present in the subtree rooted at the ‘ROOT’ node.

 

Now consider the following steps to implement the function :

 

  1. If the ‘ROOT’ is NULL, then return 0.
  2. Compare the target value with the ‘ROOT’ of the tree.
  3. If the value is matched then return true.
  4. Otherwise check if the ‘KEY’ is less than the element present on the root, if so then move to the left sub-tree.
  5. If not, then move to the right sub-tree.
Time Complexity

O(N), Where ‘N’ is the number of nodes in the given BST.

 

Since if the binary search tree is left skewed or right skewed then the algorithm will make ‘N’ computations. Thus the time complexity will be O(N).

Space Complexity

O(N), Where ‘N’ is the number of nodes in the given binary tree.

 

Since we are doing a recursive tree traversal and in the worst case (Skewed Trees), all nodes of the given tree can be stored in the call stack. Thus the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Find a value in BST
Full screen
Console