Search in a Binary Search Tree - Practice Coding Problems

Search in a Binary Search Tree - Problem

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

A binary search tree is a binary tree where for every node:

All nodes in the left subtree have values less than the node's value
All nodes in the right subtree have values greater than the node's value

Input & Output

Example 1 — Basic BST Search

$ Input: root = [4,2,7,1,3], val = 2

› Output: [2,1,3]

💡 Note: Start at root 4. Since 2 < 4, go left to node 2. Found target 2, return subtree rooted at 2 which contains [2,1,3].

Example 2 — Target Not Found

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

› Output: []

💡 Note: Start at root 4. Since 5 > 4, go right to node 7. Since 5 < 7, try to go left but node 7 has no left child. Target not found, return null (empty array).

Example 3 — Search Root

$ Input: root = [4,2,7,1,3], val = 4

› Output: [4,2,7,1,3]

💡 Note: Start at root 4. Target equals root value, so return the entire tree rooted at 4.

Constraints

The number of nodes in the tree is in range [1, 5000]
1 ≤ Node.val ≤ 10⁷
root is a binary search tree
1 ≤ val ≤ 10⁷

Visualization

Tap to expand

Understanding the Visualization

Input

BST tree and target value to search for

Navigate using BST property to find target node

Output

Return subtree rooted at found node or null if not found

Key Takeaway

🎯 Key Insight: BST property allows us to navigate directly to the target without visiting unnecessary nodes

Asked in

f Facebook 35 a Amazon 28 G Google 22 M Microsoft 18

The optimal approach leverages the BST property where left children are smaller and right children are larger. By comparing the target with each node, we can eliminate half the tree at each step, achieving O(h) time complexity where h is the tree height. Best approach is BST Property Search. Time: O(h), Space: O(h).

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search Tree Property	O(h)	O(h)	Use BST property to eliminate half the tree at each step
Brute Force DFS	O(n)	O(h)	Visit every node in the tree to find the target value

Binary Search Tree Property — Algorithm Steps

Compare target with current node
Go left if target is smaller
Go right if target is larger
Return node when found

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare at Root

Target 2 < 4, go left

Found Target

Node 2 equals target, return this subtree

Result

Subtree rooted at node 2

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* solution(struct TreeNode* root, int val) {
    if (!root) return NULL;
    if (root->val == val) return root;
    else if (val < root->val) return solution(root->left, val);
    else return solution(root->right, val);
}

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void printTree(struct TreeNode* root) {
    if (!root) {
        printf("[]");
        return;
    }
    struct TreeNode* queue[1000];
    int front = 0, rear = 0;
    queue[rear++] = root;
    int result[1000];
    int nulls[1000];
    int size = 0;
    
    while (front < rear) {
        struct TreeNode* node = queue[front++];
        if (node) {
            result[size] = node->val;
            nulls[size] = 0;
            queue[rear++] = node->left;
            queue[rear++] = node->right;
        } else {
            result[size] = 0;
            nulls[size] = 1;
        }
        size++;
    }
    
    while (size > 0 && nulls[size-1]) size--;
    
    printf("[");
    for (int i = 0; i < size; i++) {
        if (i > 0) printf(",");
        if (nulls[i]) printf("null");
        else printf("%d", result[i]);
    }
    printf("]\n");
}

int main() {
    // Simple implementation for demo
    struct TreeNode* root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(7);
    root->left->left = createNode(1);
    root->left->right = createNode(3);
    
    int val = 2;
    struct TreeNode* result = solution(root, val);
    printTree(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(h)

Tree height h determines path length, O(log n) for balanced tree, O(n) for skewed tree

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

89.0K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search Tree Property — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler