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
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

New Year Chaos Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala