DevPath
Tracks

Trees and Binary Search Trees

Hierarchical data, the four classic traversals, and how a binary search tree gives ordered search, insert and delete in O(h) time.

intermediate50 min#trees#bst#traversal#recursion

Prerequisites: Recursion, Stacks and Queues

Why it matters

Trees model anything with a parent and children: file systems, the HTML DOM, org charts, expression parsers, and the decision structure inside many algorithms. A binary search tree (BST) adds an ordering rule that lets you search, insert and delete in time proportional to the tree's height, and it keeps data sorted as a side effect. Databases and language libraries use balanced relatives of it (B-trees, red-black trees) every day, and tree problems are among the most common interview questions.

Intuition

A tree is a family tree turned upside down: one root at the top, and every node has zero or more children. A node with no children is a leaf. The height is the number of nodes on the longest root-to-leaf path (some books count edges instead, so always state which you use).

In a binary tree each node has at most two children, called left and right. A BST adds one rule: for every node, all keys in its left subtree are smaller and all keys in its right subtree are larger. That is exactly the rule of the "guess my number" game. At each node you compare once and throw away one whole side.

        50
       /  \
     30    70
    /  \   /  \
  20   40 60  80
       /
     35

Searching for 35 visits 50, 30, 40, 35: four comparisons instead of scanning eight keys.

5030204035706080
The same tree as above, searching for 35. The highlighted path is all that is visited; each comparison discards a whole faded subtree without looking inside it.

How it works

Traversals visit every node exactly once. They differ only in when you handle the node relative to its children:

  • Pre-order (node, left, right): copy a tree, serialize it.
  • In-order (left, node, right): on a BST this yields keys in sorted order.
  • Post-order (left, right, node): children before parents, ideal for deleting a tree or computing sizes and heights.
  • Level-order (breadth first): row by row using a queue.

The first three are naturally recursive and use stack space proportional to the height. Level-order replaces recursion with a queue.

5030204035706080
In-order means left, node, right. So we dive left from the root 50 as far as possible before visiting anything.
step 1 / 9

In-order traversal on the example BST. Green is the node being visited, amber is already visited. Notice that the output comes out sorted.

The other orders walk the same tree and only change when the node is handled, so the root lands in a different place in each output.

Pre-order
50
30
20
40
35
70
60
80
In-order
20
30
35
40
50
60
70
80
Post-order
20
35
40
30
60
80
70
50
Level-order
50
30
70
20
40
60
80
35
Visiting order of the example tree under each traversal (matches the code's output below). The highlighted cell is the root 50: first in pre-order and level-order, in the middle for in-order, last in post-order.

Insert walks down comparing keys until it falls off the tree, then attaches a new leaf there. Search is the same walk. Delete has three cases:

  1. The node is a leaf: remove it.
  2. The node has one child: replace the node with that child.
  3. The node has two children: copy in the in-order successor (smallest key in the right subtree), then delete that successor from the right subtree. The successor has no left child, so its removal falls into case 1 or 2.
5030204035706080
Search for 35, then insert 65. Both start at the root.
step 1 / 9

Search and insert are the same downward walk: amber is the path taken so far, green is the current node. Insert just attaches a leaf where the search would have failed.

Balance. Every cost above is O(h). If keys arrive in sorted order, each insert goes right and the tree degrades into a linked list with h equal to n. A self-balancing tree (AVL, red-black) rotates nodes after updates to keep h near log n. You rarely write one by hand, but you should know why they exist.

Same five keys, two insertion orders. The shape, not the key count, decides the cost.

32145
Balanced-looking tree for keys 1 to 5 (inserted in the order 3, 2, 4, 1, 5). Height is 3, so any search takes at most 3 comparisons.
12345
The same keys inserted in sorted order 1, 2, 3, 4, 5 form a chain of height 5, which is exactly a linked list. Searching for 5 visits every node: O(n) instead of O(log n).
OperationTimeNotes
Search / insert / delete (balanced BST)O(log n)Height is about log n
Search / insert / delete (worst case, skewed)O(n)Sorted inserts make a chain
Any traversalO(n)Each node visited once
Extra space for recursive traversalO(h)Call stack depth
Min / maxO(h)Walk all the way left or right

Code: a BST with all four traversals

import json
from collections import deque
 
def show(*xs):
    print(*(json.dumps(x, separators=(',', ':')) for x in xs))
 
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
 
def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root
 
def search(root, key):
    while root and root.key != key:
        root = root.left if key < root.key else root.right
    return root is not None
 
def delete(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        succ = root.right
        while succ.left:
            succ = succ.left
        root.key = succ.key
        root.right = delete(root.right, succ.key)
    return root
 
def inorder(n):
    return inorder(n.left) + [n.key] + inorder(n.right) if n else []
 
def preorder(n):
    return [n.key] + preorder(n.left) + preorder(n.right) if n else []
 
def postorder(n):
    return postorder(n.left) + postorder(n.right) + [n.key] if n else []
 
def level_order(root):
    out, q = [], deque([root] if root else [])
    while q:
        level = []
        for _ in range(len(q)):
            n = q.popleft()
            level.append(n.key)
            if n.left: q.append(n.left)
            if n.right: q.append(n.right)
        out.append(level)
    return out
 
def height(n):
    return 0 if n is None else 1 + max(height(n.left), height(n.right))
 
root = None
for k in [50, 30, 70, 20, 40, 60, 80, 35]:
    root = insert(root, k)
show(inorder(root))
show(preorder(root))
show(postorder(root))
show(level_order(root))
show(search(root, 60), search(root, 65), height(root))
root = delete(root, 30)
show(inorder(root), root.left.key)
root = None
for k in range(1, 6):
    root = insert(root, k)
show(height(root))

Python prints:

[20,30,35,40,50,60,70,80]
[50,30,20,40,35,70,60,80]
[20,35,40,30,60,80,70,50]
[[50],[30,70],[20,40,60,80],[35]]
true false 4
[20,35,40,50,60,70,80] 35
5

JavaScript prints exactly the same seven lines. The in-order output is sorted, deleting 30 (two children) pulls up its successor 35, and inserting 1 to 5 in order produces height 5, a chain.

Common pitfalls

  • Forgetting the base case: a function that dereferences node.left without checking for an empty tree crashes on every leaf.
  • Validating a BST locally: checking only left < node < right for each node is wrong. A key deep in the left subtree can still exceed an ancestor. Pass down min and max bounds, or check that the in-order output is strictly increasing.
  • Assuming a BST is balanced: inserting sorted data silently produces O(n) operations. Shuffle input or use a self-balancing structure.
  • Mixing up height and depth: depth counts down from the root, height counts up from the leaves.
  • Deep recursion: a skewed tree with a million nodes overflows the call stack in both Python and JavaScript. Use an explicit stack for that case.
  • Duplicates: decide up front whether they are rejected, counted, or sent to one side. The code above ignores them.

Practice

Maximum depth of a binary tree easy

Hint

Height of a tree in terms of the heights of its subtrees.

Show solution

The height of an empty tree is 0. Otherwise it is 1 plus the larger of the left and right heights. This is a post-order computation, O(n) time and O(h) stack space.

Validate a binary search tree medium

Hint

A node's valid range is narrowed by every ancestor, not just its parent.

Show solution

Recurse with an allowed open interval (lo, hi), starting at (negative infinity, positive infinity). A node is valid if lo is less than its key and its key is less than hi. Go left with (lo, key) and right with (key, hi). O(n) time. The in-order alternative: traverse and confirm each key is greater than the previous one.

Lowest common ancestor in a BST medium

Hint

Compare both targets with the current node and use the BST ordering.

Show solution

Start at the root. If both targets are smaller than the node, go left; if both are larger, go right; otherwise the current node is the split point and is the answer. Iterative, O(h) time, O(1) space.

Level-order grouped by depth, then zigzag hard

Hint

Process one level per loop iteration, using the queue length at the start of the level.

Show solution

Do the level-order traversal from the code above, which already returns a list per level. For zigzag, reverse every odd-numbered level before appending it. The queue holds at most one level plus children, so space is O(width) and time is O(n).

Interview questions

  1. Which traversal gives sorted output from a BST, and why? In-order, because it visits the smaller left subtree, then the node, then the larger right subtree at every level.
  2. What is the cost of search in a BST? O(h): O(log n) if balanced, O(n) if skewed.
  3. How do you delete a node with two children? Replace its key with the in-order successor (or predecessor) and delete that node, which has at most one child.
  4. Why do self-balancing trees exist? To guarantee h stays near log n regardless of insertion order, via rotations.
  5. Recursive versus iterative traversal? Recursion is shorter; an explicit stack avoids stack overflow on very deep trees.

Interviewers look for: clarity about whether the tree is a BST or just a binary tree, handling the empty tree, naming the complexity in terms of height, and awareness that balance is not free.

Quick check

You insert the keys 1, 2, 3, 4, 5, 6 in that order into an empty plain BST. What is the cost of searching for 6?

Finished this lesson?

Further resources

Related lessons