Search in a Binary Search Tree - The Coding Shala

Last Updated: 26-Jan-2021

Home >> Data Structures >> Search in a Binary Search Tree

 In this post, we will learn how to search a given node in a Binary Search Tree and will implement its solution in Java.

Search in a Binary Search Tree

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node's value equals the given value. Return the subtree rooted with that node. If such a node doesn't exist, you should return NULL.

Example:

Given the tree:

        4

       / \

      2   7

     / \

    1   3

And the value to search: 2

You should return this subtree:

      2     

     / \   

    1   3

In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.

Search in a Binary Search Tree Java Program

Approach 1

we can check with root value if match then returns root. if the target value is less than the root node then the root move to the left subtree else right subtree.

Java Program: 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null) return null;
        while(root != null){
            if(root.val == val) return root;
            if(root.val > val) root = root.left;
            else root = root.right;
        }
        return null;
    }
}

Other Posts You May Like

• Introduction to Binary Search Tree
• Insert into Binary Search Tree
• Delete a Node in Binary Search Tree
• Introduction to N-ary Tree
• Introduction to Binary Tree

Please leave a comment below if you like this post or found some errors, it will help me to improve my content.