How does the search algorithm work with a binary tree?

AlgorithmsJunior~3 min read

Short answer

If the tree is a binary search tree (BST), the search proceeds top-down: compare the key with the current node, go left if key < node, go right if key > node; stop on equality or when an empty reference is reached. Time is O(h), where h is the tree's height: O(log n) in the balanced case and O(n) in the worst (stretched-out) case. If the tree is just a plain binary tree (without the BST property), a full traversal (DFS or BFS) is needed, with O(n) time.

Detailed breakdown

Definitions

Binary tree: each node has at most two children (left, right). No additional ordering guarantees.
Binary search tree (BST): for every node it holds that all keys in the left subtree are < the node's key, and all keys in the right subtree are > the node's key (equality is often allowed by convention). This property enables a "directed" search.

Searching a binary search tree (BST)

Start at the root. Let k be the key to search for, and x the current node.
If x == null, the element isn't present (return null/undefined).
If k == x.key, it's found; return x.
If k < x.key, move to the left subtree (x = x.left).
Otherwise (k > x.key), move to the right subtree (x = x.right). Repeat until done.

Time complexity: O(h), where h is the tree's height. In a balanced tree, h ≈ log2(n), so O(log n). In the worst case (a stretched-out tree), O(n).
Memory: O(1) extra memory iteratively; O(h) recursively, due to the call stack.

Code: BST search (JavaScript)

class TreeNode {
  constructor(key, left = null, right = null) {
    this.key = key;
    this.left = left;
    this.right = right;
  }
}

// Recursive search
function searchBSTRecursive(node, k) {
  if (node === null) return null;
  if (k === node.key) return node;
  if (k < node.key) return searchBSTRecursive(node.left, k);
  return searchBSTRecursive(node.right, k);
}

// Iterative search
function searchBSTIterative(root, k) {
  let curr = root;
  while (curr !== null) {
    if (k === curr.key) return curr;
    curr = k < curr.key ? curr.left : curr.right;
  }
  return null;
}

// Example
//        8
//      /   \
//     3     10
//    / \      \
//   1   6      14
//      / \     /
//     4   7   13
const root = new TreeNode(8,
  new TreeNode(3,
    new TreeNode(1),
    new TreeNode(6, new TreeNode(4), new TreeNode(7))
  ),
  new TreeNode(10, null, new TreeNode(14, new TreeNode(13)))
);

console.log(!!searchBSTIterative(root, 7));   // true
console.log(!!searchBSTIterative(root, 2));   // false

Duplicates in a BST

There are several conventions; pick one and stick with it throughout the tree:

Always place duplicates on the left (≤) or always on the right (≥).
Store a frequency counter in the node (key, count).

Searching a plain binary tree (without the BST property)

If the tree provides no ordering, there is no directed search: you must traverse all nodes until you find the one you need. DFS or BFS is typically used.

BFS (breadth-first) via a queue

Put the root into the queue.
While the queue isn't empty: dequeue a node, check it, add its children to the queue.

function searchBinaryTreeBFS(root, predicate) {
  if (!root) return null;
  const q = [root];
  while (q.length) {
    const node = q.shift();
    if (predicate(node)) return node;
    if (node.left) q.push(node.left);
    if (node.right) q.push(node.right);
  }
  return null;
}

// Example: find the node with value 13
const foundBFS = searchBinaryTreeBFS(root, (n) => n.key === 13);
console.log(!!foundBFS); // true

DFS (depth-first), recursively (pre/in/post-order)

Pre-order (NLR): process the node, then the left, then the right.
In-order (LNR): left, process the node, right (gives a sorted sequence for a BST).
Post-order (LRN): left, right, process the node.

function searchBinaryTreeDFS(node, predicate) {
  if (!node) return null;
  if (predicate(node)) return node;            // pre-order check
  const left = searchBinaryTreeDFS(node.left, predicate);
  if (left) return left;
  return searchBinaryTreeDFS(node.right, predicate);
}

const foundDFS = searchBinaryTreeDFS(root, (n) => n.key === 4);
console.log(!!foundDFS); // true

Complexity for BFS/DFS: time O(n), memory O(w) for BFS (the maximum level width) and O(h) for recursive DFS.

Comparing the approaches

Scenario	Time	Memory	Conditions
BST search (iterative)	O(h) (often O(log n))	O(1)	The tree satisfies the BST property
Plain binary tree (BFS/DFS)	O(n)	O(w) for BFS, O(h) for DFS	No ordering, a full traversal is needed

Common interview questions

How do you handle duplicates? Which side do you place them on, and how do you find all occurrences?
What happens to the complexity in an unbalanced tree, and how do AVL/red-black structures help?
Iterative vs recursive search: trade-offs around the stack and simplicity.
Can DFS stop early? Yes, if the predicate matches, you return back up the stack.
How do you get a sorted result? An in-order traversal of a BST.

Summary

In a BST, search relies on the ordering property and moves left/right until a match or an empty reference, giving O(log n) in the balanced case. In a plain binary tree, search requires a full traversal (DFS/BFS) with O(n) complexity.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.