Search in a Binary Search Tree

You are given the root of a binary search tree (BST) and an integer val. Find the node in the BST where the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

Approach 1

class Solution {
    public TreeNode searchBST(TreeNode root, int x) {
        while (root != null && root.val != x) {
            root = root.val > x ? root.left : root.right;
        }
        return root;
    }
}
        

Approach 2: Iterative Approach

Iterative Approach in detail

import java.util.Stack;

class Solution {
    public TreeNode searchBST(TreeNode root, int x) {
        if (root == null) return null;

        Stack stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();

            if (node.val == x) {
                return node;
            }

            // Push right child first to maintain order
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }

        return null;
    }
}
        

Approach 3

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