Find a Value in a BST - Algorithm, Visualization, Examples

Binary Search Trees

Contents

VisualizationProblemExamplesSolutionAlgorithmCode

Visualization Player

Problem Statement❯

Given a Binary Search Tree (BST) and a target value, your task is to determine whether this value exists in the BST. If it does, return the node that contains this value; otherwise, return null or indicate that the value is not found.

Examples❯

Input BST (level-order traversal) Target Expected Output Explanation
[5, 3, 7, 2, 4, 6, 8]
6 Node with value 6 Value 6 exists in the BST. The function should return the node containing 6.Visualization
[5, 3, 7, 2, 4, 6, 8]
9 null Value 9 is greater than all values in the BST. It is not found.Visualization
[5]
5 Node with value 5 Single node in BST matches the target. Return that node.Visualization
[] 3 null The BST is empty. There's nothing to search; return null.Visualization

Solution❯

A Binary Search Tree (BST) ensures that for any node:

  • All values in the left subtree are smaller.
  • All values in the right subtree are larger.

This structure allows us to efficiently search for values using a process similar to binary search.

How We Approach the Problem

To search for a value in a BST, we follow these steps:

  1. Start at the root node of the tree.
  2. Compare the target value with the current node's value.
  3. If they are equal, the search is successful — we return the node.
  4. If the target is smaller, we move to the left child and repeat the process.
  5. If the target is greater, we move to the right child and continue the search.
  6. If we reach a null node, the target doesn't exist in the tree — return null.

Example Tree

Given level order array: [5, 3, 7, 2, 4, 6, 8]

The BST formed is:

Search Example: Find 6

  1. Start at root node 5
  2. 6 > 5 → go right
  3. Current node is 7 → 6 < 7 → go left
  4. Current node is 6 → match found

Output: Node with value 6

Edge Case 1 - Target Value Does Not Exist

Given level order array: [5, 3, 7, 2, 4, 6, 8]. Search for value 9.

  1. Start at root node 5
  2. At 5, we get 9 > 5 → go right
  3. At 7, we get 9 > 7 → go right
  4. At 8, we get 9 > 8 → go right
  5. 8 does not have a right, return null.

Output: Not found (null)

Edge Case 2 - Target Value is the Root

Given level order array: [5, 3, 7, 2, 4, 6, 8]. Search for value 5.

  1. Start at root: 5 → match found

Output: Node with value 5

Edge Case 3-1 - Target is the Leftmost or Rightmost Node

Given level order array: [5, 3, 7, 2, 4, 6, 8]. Search for value 2.

  1. Start at root node 5
  2. At 5, we get 2 < 5 → go left
  3. At 3, we get 2 < 3 → go left
  4. At 2, we get 2 == 2 → return node 2

Output: Node with value 2

Edge Case 3-2 - Target is the Leftmost or Rightmost Node

Given level order array: [5, 3, 7, 2, 4, 6, 8]. Search for value 8.

  1. Start at root node 5
  2. At 5, we get 8 > 5 → go right
  3. At 7, we get 8 > 7 → go right
  4. At 8, we get 8 == 8 → return node 8

Output: Node with value 8

Edge Case 4 - Empty Tree

If the tree is empty (i.e., root is null):

  • No nodes to search → return null immediately

Output: Not found (null)

Algorithm Steps❯

  1. Given a Binary Search Tree (BST) and a target value.
  2. Start at the root node of the BST.
  3. If the current node is null, the target is not found; return null.
  4. If the current node's value equals the target, return the current node.
  5. If the target is less than the current node's value, recursively search the left subtree.
  6. If the target is greater than the current node's value, recursively search the right subtree.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

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

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

TreeNode* findInBST(TreeNode* root, int target) {
    if (root == NULL) return NULL;
    if (root->val == target) return root;
    return target < root->val ? findInBST(root->left, target) : findInBST(root->right, target);
}

int main() {
    TreeNode* root = createNode(10);
    root->left = createNode(5);
    root->right = createNode(15);

    int target = 5;
    TreeNode* result = findInBST(root, target);

    if (result) {
        printf("Found node with value: %d\n", result->val);
    } else {
        printf("Value not found\n");
    }

    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...