Find a value in a BST

Problem Statement

Given a Binary Search Tree (BST) and a value, find whether the value exists in the BST or not. Return the node containing the value if found, otherwise return null.

Example:

Approach 1: Brute Force (Traverse Entire Tree)

Intuition

Traverse the entire tree using any traversal method (preorder, inorder, or level order) and check each node's value against the target. This approach ignores the BST property.

Algorithm

1. Start from root and traverse all nodes
2. At each node, check if value matches target
3. If found, return the node
4. If traversal completes without finding, return null

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    // Brute force: Level order traversal (ignores BST property)
    public TreeNode searchBSTBruteForce(TreeNode root, int val) {
        if (root == null) return null;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            TreeNode curr = queue.poll();
            
            if (curr.val == val) return curr;
            
            if (curr.left != null) queue.offer(curr.left);
            if (curr.right != null) queue.offer(curr.right);
        }
        
        return null;
    }
}

Complexity Analysis

• Time Complexity: O(n) - May need to visit all nodes
• Space Complexity: O(n) - Queue can hold up to n/2 nodes at leaf level

Approach 2: Optimal (Using BST Property - Recursive)

Intuition

Leverage the BST property: all values in left subtree are smaller, and all values in right subtree are larger. This allows us to eliminate half the tree at each step.

Algorithm

1. If root is null, return null
2. If root's value equals target, return root
3. If target is less than root's value, search left subtree
4. If target is greater than root's value, search right subtree

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    // Optimal: Using BST property (Recursive)
    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);
    }
}

Complexity Analysis

• Time Complexity: O(h) where h is height - O(log n) for balanced, O(n) for skewed
• Space Complexity: O(h) - Recursion stack

Approach 3: Optimal (Using BST Property - Iterative)

Intuition

Same logic as recursive but using iteration to achieve O(1) space complexity.

Algorithm

1. Start with current node as root
2. While current is not null:
   • If current's value equals target, return current
   • If target < current's value, move to left child
   • Else move to right child
3. Return null if not found

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    // Optimal: Using BST property (Iterative)
    public TreeNode searchBSTIterative(TreeNode root, int val) {
        TreeNode curr = root;
        
        while (curr != null) {
            if (curr.val == val) {
                return curr;
            } else if (val < curr.val) {
                curr = curr.left;
            } else {
                curr = curr.right;
            }
        }
        
        return null;
    }
}

Complexity Analysis

• Time Complexity: O(h) where h is height - O(log n) for balanced, O(n) for skewed
• Space Complexity: O(1) - Only using a pointer

Key Takeaways

1. BST Property: Left subtree contains smaller values, right subtree contains larger values
2. Binary Search: Each comparison eliminates half the remaining tree
3. Iterative vs Recursive: Iterative saves O(h) space from recursion stack
4. Height matters: O(log n) for balanced BST, O(n) for skewed BST
5. This is LeetCode #700 - Search in a Binary Search Tree
6. Foundation for understanding BST operations (insert, delete, etc.)