How to Search for a Node in a Binary Search Tree (BST) – Efficient Solutions Explained

When working with Binary Search Trees (BSTs), one of the most common operations is searching for a node with a specific value. This operation is fundamental to many algorithms and data structures that rely on trees. In this blog post, we will explore how to search for a node in a Binary Search Tree (BST), explain the step-by-step approach, and optimize it for better performance.

What is a Binary Search Tree (BST)?

Before diving into the search algorithm, let's quickly define a Binary Search Tree (BST). A BST is a type of binary tree where each node has at most two children: a left child and a right child. The key property of a BST is that for each node:

• All values in the left subtree are less than or equal to the node’s value.
• All values in the right subtree are greater than or equal to the node’s value.

This property allows for efficient searching, as we can eliminate half of the remaining search space at each step, just like binary search in an array.

---

The Problem: Search in a Binary Search Tree (LeetCode Problem 700)

Problem Statement:

Given the root of a Binary Search Tree and a value val, we need to find the node in the BST where the node's value equals val. If such a node exists, return the subtree rooted at that node. If the node is not found, return NULL.

---

Solution Overview

The key to solving this problem efficiently lies in the properties of the Binary Search Tree (BST). Since the tree is sorted, the search for any value val can be done in O(h) time, where h is the height of the tree.

We have two main approaches to solve this problem:

1. Recursive Approach
2. Iterative Approach

Let's break down both approaches and see how they work.

---

1. Recursive Approach

The recursive approach leverages the structure of the BST to search for the desired value. We start at the root of the tree and check whether the value is equal to the current node’s value. Based on the value comparison, we move either left or right.

Step-by-Step Explanation:

1. If the root is NULL, the tree is empty, and the value is not found. Return NULL.
2. If the value at the current node matches the target value, return the node.
3. If the target value is smaller than the current node’s value, recursively search the left subtree.
4. If the target value is larger, recursively search the right subtree.

This recursive approach works because, at each node, we either search the left or right subtree based on the BST property.

Recursive Code Example:

class Solution {

public:

    TreeNode* searchBST(TreeNode* root, int val)

    {

        // Base case: If the node is NULL or the value matches the current node's value

        if (!root || root->val == val)

        {

            return root;

        }

        // If the target value is smaller, search in the left subtree

        if (val < root->val)

        {

            return searchBST(root->left, val);

        }

        // If the target value is larger, search in the right subtree

        return searchBST(root->right, val);

    }

};

Time Complexity: O(h), where h is the height of the tree. In the worst case (unbalanced tree), the time complexity could be O(n), where n is the number of nodes.

Space Complexity: O(h), where h is the height of the tree. This is due to the recursive stack. In the worst case of an unbalanced tree, the space complexity could be O(n).

---

2. Iterative Approach

The iterative approach eliminates recursion and uses a loop to traverse the tree. We can search for the target value in a similar manner to the recursive approach but without the overhead of recursive function calls.

Step-by-Step Explanation:

1. Start at the root node.
2. While the current node is not NULL, compare the target value with the node’s value.
3. If the value is found, return the current node.
4. If the target value is smaller than the current node’s value, move to the left child.
5. If the target value is larger, move to the right child.
6. If you reach a NULL node, return NULL, indicating the value does not exist in the tree.

Iterative Code Example:

class Solution {

public:

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

        while (root != NULL) {

            if (root->val == val) {

                return root;

            }

            // Move to the left or right subtree based on the value

            root = (val < root->val) ? root->left : root->right;

        }

        return NULL;  // If the value was not found

    }

};

Time Complexity: O(h), where h is the height of the tree. Similar to the recursive approach, the time complexity can be O(n) in the worst case for an unbalanced tree.

Space Complexity: O(1). Since we’re not using the recursion stack, the space complexity is constant, making this approach more space-efficient.

---

Which Approach Should You Use?

Both approaches (recursive and iterative) solve the problem effectively, but they come with different trade-offs:

• Recursive Approach: Easier to understand and write, but the recursion stack can consume extra space in deep trees (unbalanced trees).
• Iterative Approach: More space-efficient because it avoids recursion, but the code might be slightly less intuitive.

In practice, the iterative approach is often preferred when dealing with very deep trees (to avoid stack overflow issues) or when minimizing space usage is critical.

---

Optimizing for Balanced Trees

In a balanced Binary Search Tree (BST), the height h is logarithmic relative to the number of nodes (h = O(log n)). In such cases, both time and space complexities for both the recursive and iterative approaches are O(log n), which is highly efficient.

However, if the tree is unbalanced, the height h can become linear in the number of nodes (h = O(n)), and both approaches could degrade to O(n) time and space complexity.

To optimize the search in unbalanced trees, consider using self-balancing trees (such as AVL trees or Red-Black trees) that guarantee logarithmic height.

In this blog post, we explored how to search for a node in a Binary Search Tree (BST). We looked at two approaches: the recursive approach and the iterative approach. Both have their advantages and trade-offs in terms of time and space complexity.

• Recursive Approach: More intuitive and easier to implement but uses the recursion stack.
• Iterative Approach: More space-efficient and avoids the recursion stack but might be slightly less intuitive.

Depending on your needs (space efficiency or simplicity), you can choose the appropriate approach. For trees with a lot of nodes or deep structures, the iterative approach might be a better choice.

---

SEO Tags:

• Search in Binary Search Tree (BST)
• Binary Search Tree search algorithm
• Leetcode 700 search in BST
• Recursive vs Iterative BST search
• Optimizing search in BST
• Binary Tree search
• Leetcode solution for BST search