Binary Search Tree

Searching

What is BST Searching?

Searching a Binary Search Tree is just insertion's walk without the final "attach a node" step: start at the root, compare the target against the current node, and let the BST property tell you exactly which way to go, smaller means left, larger means right. Either you land on the value, or you eventually fall off the tree (hit a null pointer), which means it isn't there.

How Does It Work?

  1. Search for 6 in a tree rooted at 8
  2. 8: 6 < 8 → go left
  3. 3: 6 > 3 → go right
  4. 6: 6 = 6 → found it!
831016
Comparison pathFound

If the value isn't in the tree, the same walk simply runs out of tree:

  1. Searching for a value that isn't present follows the same path logic
  2. The walk continues left/right based on comparisons
  3. Eventually it reaches a null pointer instead of a matching node
  4. That null pointer means the value isn't in the tree, so search stops there

This is the entire reason a BST is useful in the first place. The sorted structure lets you eliminate an entire subtree with every comparison, the same way binary search eliminates half of a sorted array. That's what gets search down to O(log n) instead of the O(n) you'd need to scan an unsorted structure.

Algorithm Steps

  1. Start at the root
  2. Compare the target value with the current node:
    • If equal, return the node (found)
    • If smaller, move to the left child
    • If larger, move to the right child
  3. Repeat until you find a match or hit a null pointer
  4. A null pointer means the value isn't in the tree

Time Complexity

  • Best Case: Target is the root → O(1).
  • Average Case: Roughly balanced tree → O(log n).
  • Worst Case: Degenerate/skewed tree → O(n).

Time Complexity Analysis

Space Complexity

Search needs O(1) additional space (excluding the recursion call stack), since it never creates or modifies any nodes: it's a read-only walk.

Because search, insertion, and deletion all follow this same root-to-leaf comparison walk, they share the same best/worst-case complexity profile, which is exactly why keeping a BST balanced (see AVL trees) matters for all three operations, not just one.

Daily DSA Challenge by Scale Engineer

Search for a value and watch the comparison path narrow in on it

Tree is empty
No tree yet, insert a value or generate a random tree
Internal nodeLeaf nodeRootComparison pathFoundNot foundEliminated subtree

Test Your Knowledge before moving forward!

BST Searching Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Binary Search Tree Searching Implementation

// Binary Search Tree node
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Search for a value in the BST
function search(node, value) {
  if (node === null) return null;       // not found
  if (value === node.value) return node; // found

  return value < node.value
    ? search(node.left, value)
    : search(node.right, value);
}

// Usage example
let root = null;
[8, 3, 10, 1, 6].forEach((value) => {
  root = insert(root, value); // see BST Insertion for insert
});

const result = search(root, 6);
console.log(result ? "Found" : "Not found");

Done With the Learning

Mark BST Searching as done and view it on your dashboard

Explore Other Tree Topics

BST Insertion

BST Deletion

AVL Balancing

Lowest Common Ancestor

Binary Tree Types

Structure & Properties