Search in a Binary Search Tree

How it works

Instead of using the call stack for recursion, we can use a simple loop. At each step, we compare the target with the current node and move left or right accordingly. This avoids recursion overhead and keeps space usage constant.

Steps

1. While root is not null and root.val does not equal the target:
   • If the target is less than root.val, move to root.left.
   • Otherwise, move to root.right.
2. Return root (either the found node or null).

Complexity

• Time complexity: O(H)
• Space complexity: O(1) extra space.

Where H is the height of the given tree.

Things to watch for

Ignoring the BST Property

Treating this problem like a general binary tree search by checking both left and right children at every node defeats the purpose of the BST structure. The BST property guarantees that the target can only be in one subtree, so always compare the target with the current node value to decide which direction to go.

Not Handling the Null Case

Forgetting to check if root is null before accessing root.val will cause a null pointer exception. This check is essential both as a base case for recursion and as a loop termination condition for the iterative approach.

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        while root and root.val != val:
            root = root.left if val < root.val else root.right
        return root

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while (root && root->val != val) {
            root = val < root->val ? root->left : root->right;
        }
        return root;
    }
};