Last Updated: 14 Feb, 2021
Find a value in BST
Easy
Asked in companies
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:
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.
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
Approaches
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 :
- If the ‘ROOT’ is NULL, then return 0.
- Compare the target value with the ‘ROOT’ of the tree.
- If the value is matched then return true.
- Otherwise check if the ‘KEY’ is less than the element present on the root, if so then move to the left sub-tree.
- If not, then move to the right sub-tree.