Find a value in BST
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

Question

Find a value in BST

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.

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

Accepted Answer

The task is to find if a given value is present in a Binary Search Tree (BST).

Start from the root node and compare the value with the target value.
If the value matches, return true.
If the target value is less than the current node value, move to the left child.
If the target value is greater than the current node value, move to the right child.
Repeat the process until a match is found or a leaf node is reached.
If a leaf node is reached and no match is found, return false.

Accepted Answer

Easy approach, solved with log(n) complexity

Accepted Answer

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* ‘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.

Space Complexity: O(n)Explanation:

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).

Time Complexity: OtherExplanation:

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).

Python (3.5)

"""
    Time complexity: O(N)
    Space complexity: O(N)

    Where 'N' is the number of nodes in the given binary tree.
"""

def findNode(root, key):
    # If root is none.
    if (root == None):
       return False

    # If key value is found.
    if(root.data == key):
        return True

    # If key is greater than root's key then check in right subtree.
    if (root.data < key):
       return findNode(root.right, key)

    # If key is smaller than root's key then check in left subtree.
    return findNode(root.left, key)

Java (SE 1.8)

/*
    Time complexity: O(N)
    Space complexity: O(N)

    Where 'N' is the number of nodes in the given binary tree.
*/

public class Solution {
	public static boolean findNode(TreeNode root, int key) {
		// If root is null.
		if (root == null) {
			return false;
		}

		// If key value is found.
		if (root.data == key) {
			return true;
		}

		// If key is greater than root's key then check in right subtree.
		if (root.data < key) {
			return findNode(root.right, key);
		}

		// If key is smaller than root's key then check in left subtree.
		return findNode(root.left, key);
	}
}

C++ (g++ 5.4)

/*
    Time complexity: O(N)
    Space complexity: O(N)

    Where 'N' is the number of nodes in the given binary tree.
*/

bool findNode(TreeNode  * root, int key){
    // If root is null.
    if (root == NULL)
       return false;

    // If key value is found.
    if(root->data == key)
        return true;

    // If key is greater than root's key then check in right subtree.
    if (root->data < key)
       return findNode(root->right, key);

    // If key is smaller than root's key then check in left subtree.
    return findNode(root->left, key);
}

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:

For example :

Input Format:

Output Format:

Note:

Constraints:

Top Nvidia Software Developer interview questions & answers

Popular interview questions of Software Developer