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

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode

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

Visualization Player

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

Python
Java
JavaScript
C
C++
C#
Go
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
    elif target < root.val:
        return find_in_bst(root.left, target)
    else:
        return find_in_bst(root.right, target)

# Example usage:
if __name__ == '__main__':
    # Construct a simple BST
    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")