Binary Search Trees

Problem Statement

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null. (Link)

Example 1:

Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]

Example 2:

Input: root = [4,2,7,1,3], val = 5
Output: []

Constraints:

• The number of nodes in the tree is in the range [1, 5000].

• 1 <= Node.val <= 10<sup>7</sup>

• root is a binary search tree.

• 1 <= val <= 10<sup>7</sup>

Solution

A binary search tree follows one simple condition: left < Node < right. This means that for any node you pick, this rule is followed.

Properties of a BST:

• Each left and right subtree is also a BST.

• Any subtree is also a BST.

• If we assume that 10 is the root, then we can only find the element 5 in the left subtree. If it's not there, we can be sure it is not present in the entire tree.

Recursive Approach

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null || root.val==val){
            return root;
        }

        if(val<root.val){
            return searchBST(root.left, val);
        }
        return searchBST(root.right, val);
    }
}

Iterative Approach

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

        while(temp!=null){

            if(val<temp.val){
                temp = temp.left;
            }
            else if(val>temp.val){
                temp = temp.right;
            }
            else{
                break;
            }

        }
        return temp;
    }
}