Find a Value in a Binary Search Tree

Problem and examples

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.

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

Explore Find a Value in a BST

Load an example or enter your own input. Use the player controls to follow each change.

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:

Start at the root node of the tree.
Compare the target value with the current node's value.
If they are equal, the search is successful — we return the node.
If the target is smaller, we move to the left child and repeat the process.
If the target is greater, we move to the right child and continue the search.
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

Start at root node 5
6 > 5 → go right
Current node is 7 → 6 < 7 → go left
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.

Start at root node 5
At 5, we get 9 > 5 → go right
At 7, we get 9 > 7 → go right
At 8, we get 9 > 8 → go right
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.

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.

Start at root node 5
At 5, we get 2 < 5 → go left
At 3, we get 2 < 3 → go left
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.

Start at root node 5
At 5, we get 8 > 5 → go right
At 7, we get 8 > 7 → go right
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)

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

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

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

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

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

    if (result) {
        cout << "Found node with value: " << result->val << endl;
    } else {
        cout << "Value not found" << endl;
    }

    return 0;
}

Python implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def find_in_bst(root, target):
    if root is None:
        return None
    if root.val == target:
        return root
    return find_in_bst(root.left, target) if target < root.val else find_in_bst(root.right, target)

if __name__ == '__main__':
    root = TreeNode(10, TreeNode(5), TreeNode(15))
    target = 5
    result = find_in_bst(root, target)
    if result:
        print(f"Found node with value: {result.val}")
    else:
        print("Value not found")

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) {
        this.val = val;
    }
}

public class BSTSearch {
    public static 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);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(15);

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

        if (result != null) {
            System.out.println("Found node with value: " + result.val);
        } else {
            System.out.println("Value not found");
        }
    }
}

JavaScript implementation

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function findInBST(root, target) {
    if (!root) return null;
    if (root.val === target) return root;
    return target < root.val ? findInBST(root.left, target) : findInBST(root.right, target);
}

const root = new TreeNode(10, new TreeNode(5), new TreeNode(15));
const target = 5;
const result = findInBST(root, target);

if (result) {
    console.log(`Found node with value: ${result.val}`);
} else {
    console.log("Value not found");
}

Go implementation

package main

import (
    "fmt"
)

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

func findInBST(root *TreeNode, target int) *TreeNode {
    if root == nil {
        return nil
    }
    if root.val == target {
        return root
    }
    if target < root.val {
        return findInBST(root.left, target)
    }
    return findInBST(root.right, target)
}

func main() {
    root := &TreeNode{val: 10, left: &TreeNode{val: 5}, right: &TreeNode{val: 15}}
    target := 5
    result := findInBST(root, target)

    if result != nil {
        fmt.Printf("Found node with value: %d\n", result.val)
    } else {
        fmt.Println("Value not found")
    }
}

Rust implementation

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

fn find_in_bst(root: &Option<Box<TreeNode>>, target: i32) -> Option<&Box<TreeNode>> {
    match root {
        None => None,
        Some(node) if node.val == target => Some(node),
        Some(node) if target < node.val => find_in_bst(&node.left, target),
        Some(node) => find_in_bst(&node.right, target),
    }
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 10,
        left: Some(Box::new(TreeNode {
            val: 5,
            left: None,
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            val: 15,
            left: None,
            right: None,
        })),
    }));

    let target = 5;
    let result = find_in_bst(&root, target);

    match result {
        Some(node) => println!("Found node with value: {}", node.val),
        None => println!("Value not found"),
    }
}

Kotlin implementation

class TreeNode(var val: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun findInBST(root: TreeNode?, target: Int): TreeNode? {
    if (root == null) return null
    if (root.val == target) return root
    return if (target < root.val) findInBST(root.left, target) else findInBST(root.right, target)
}

fun main() {
    val root = TreeNode(10).apply {
        left = TreeNode(5)
        right = TreeNode(15)
    }
    val target = 5
    val result = findInBST(root, target)
    if (result != null) {
        println("Found node with value: ${result.val}")
    } else {
        println("Value not found")
    }
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

func findInBST(_ root: TreeNode?, _ target: Int) -> TreeNode? {
    guard let node = root else { return nil }
    if node.val == target { return node }
    return target < node.val ? findInBST(node.left, target) : findInBST(node.right, target)
}

let root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
let target = 5
if let result = findInBST(root, target) {
    print("Found node with value: \(result.val)")
} else {
    print("Value not found")
}

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function findInBST(root: TreeNode | null, target: number): TreeNode | null {
    if (!root) return null;
    if (root.val === target) return root;
    return target < root.val ? findInBST(root.left, target) : findInBST(root.right, target);
}

const root = new TreeNode(10, new TreeNode(5), new TreeNode(15));
const target = 5;
const result = findInBST(root, target);

if (result) {
    console.log(`Found node with value: ${result.val}`);
} else {
    console.log("Value not found");
}