Last Updated: 7 Apr, 2021

Search In BST

Easy

Asked in companies

Solve now

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.

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 :

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.

Solve now

Approaches

01 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:

If the root node is NULL, then return “False”.
If the ‘DATA’ of the root node equals ‘X’, then return “True”.
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.
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.

Solve now

02 Approach

Approach: The basic idea is to iterate over BST using a pointer ‘PTR’. Initially keep ‘PTR’ at the root node of BST. If ‘X’ is larger than the data of the node pointed by ‘PTR’ we move ‘PTR’ to the right child of this node, and if ‘X’ is smaller than the data of node pointed by ‘PTR’ we move ‘PTR’ to its left child. We return true if the data of the node pointer by ‘PTR’ is ‘X’.

The steps are as follows:

Initialize ‘PTR’ with the address of the root node of the given BST.
Run a loop till ‘PTR’ is not NULL and in each step do the following -:
- If ‘DATA’ of the node pointed by ‘PTR’ equals ‘X’, then return “True”.
- If the ‘DATA’ of the node pointed by ‘PTR’ is greater than ‘X’, then update ‘PTR’ by the address of the left child of the node pointed by it.
- If the ‘DATA’ of the node pointed by ‘PTR’ is smaller than ‘X’, then update ‘PTR’ by the address of the right child of the node pointed by it
Return "False".

Solve now