Search in a Binary Search Tree

Binary Search Tree (BST) is an excellent data structure for search operations and this question is an excellent one to practice its basics.

BST Properties

The left sub-tree will always have values less than the root.
The right sub-tree will always have values greater than the root.

Iterative approach

The first step is just checking if the root node is null or if its value is equal to val. If that's the case we just return our root node because it satisfies our condition.

After that, we jump into our while loop and do the following

Check for the same base condition in every iteration.
If the current node's value is greater than val we move to the left subtree.
If the current node's value is lesser than val we move to the right subtree.

After we're out of the loop our node's value is either null or equal to val. So we simply return that node.

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {

        if(root == null || root.val == val) return root;

        while(root != null && root.val != val) {

            root = root.val > val ? root.left : root.right;

        }

        return root;
    }
}

Recursive approach

We are performing the following three operations for a recursive solution -

Return the current node if its value is equal to val or null.
If val is greater than the value of the current node we go to the right subtree.
If val is lesser than the value of the current node we go to the left subtree.

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {

        if(root == null || root.val == val) return root;

        if(val > root.val)
            return searchBST(root.right, val);
        else 
            return searchBST(root.left, val);
    }
}

Thank you for reading and if you've any doubts/suggestions please do share them in the comments.

Search in a Binary Search Tree - LeetCode

Comments

More from this blog

Atomic Habits

Mongo DB Basics

MongoDB Data-Types

Persevering Through Trials and Tribulations as a Developer: Dev Retro 2022

Shiny Object Syndrome in Tech

BST Properties

Iterative approach

Recursive approach

Command Palette

Comments

More from this blog

BST Properties

Iterative approach

Recursive approach