algoadvance

Leetcode 700. Search in a Binary Search Tree

Problem Statement

Given the root node of a binary search tree (BST) and an integer value, write a function to search for a node in the BST that matches the given value. Return the node that contains the value, or nullptr if such a node does not exist.

Example:

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

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

Constraints:

1. The number of nodes in the tree is in the range [1, 5000].
2. 1 <= Node.val <= 10^7
3. root is a binary search tree.

Clarifying Questions

1. Should the search be implemented iteratively, recursively, or either is acceptable?
2. What should the function signature look like?

For the sake of this implementation, I will use a recursive approach. The function signature will be:

TreeNode* searchBST(TreeNode* root, int val);

Code

/**
 * 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) {
        if (root == nullptr || root->val == val) {
            return root;
        } else if (val < root->val) {
            return searchBST(root->left, val);
        } else {
            return searchBST(root->right, val);
        }
    }
};

Strategy

1. Base Case:
   • If the current node is nullptr, return nullptr indicating the node with the given value was not found.
   • If the current node’s value matches the search value, return the current node.
2. Recursive Case:
   • If the search value is less than the current node’s value, recursively call searchBST on the left subtree.
   • If the search value is greater than the current node’s value, recursively call searchBST on the right subtree.

By dividing the problem this way, we efficiently reduce the search space by half on every recursive call, taking advantage of the properties of a binary search tree.

Time Complexity

• Average Case: O(log N), where N is the number of nodes in the tree. Since we halve the search space at each step, the depth of the tree (log N) operations are required in the best and average cases.
• Worst Case: O(N) when the tree is highly unbalanced (e.g., a linked list).

This recursive approach is simple and leverages the properties of a binary search tree effectively.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?