Search In BST

Posted: 7 Apr, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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

You are given a pointer to the root node of this BST, and an integer ‘X’. Print "True" if there is a node in BST having data equals to ‘X’, otherwise print "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. Both the left and right subtrees must also be binary search trees.
Note:
1.  It is guaranteed that all nodes have distinct data.
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case contains two positive integers ‘N and ‘X’, denoting the number of nodes in the BST and a given integer.

The second line contains the elements of the tree in the level order form separated by a single space. If any node does not have a 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 :

alt text

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

Explanation :
Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

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

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

Level 5 :
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 just 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:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
Output Format:
For each test case, print “True” if there is a node in BST having data equals 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 taken care of. Just implement the function.
Constraints:
1 <= T <= 50
1 <= N <= 10000
0 <= X <= 10^9
0 <= DATA <=10^9

Where ‘T’ is the number of test cases, ‘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
Approach 1

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.
Try Problem