Suggest an edit

Improve this article

Refine the answer for “How does the search algorithm work with a binary tree?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## 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)

1. Start at the root. Let k be the key to search for, and x the current node.
2. If x == null, the element isn't present (return null/undefined).
3. If k == x.key, it's found; return x.
4. If k < x.key, move to the left subtree (x = x.left).
5. 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

1. Put the root into the queue.
2. 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.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts870 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.