Trees & BSTs

Why We Need Trees & How to Think About It

Arrays and linked lists are linear (flat) structures. However, real-world data is often hierarchical. Consider a folder directory on your computer: a directory can contain individual files and other subdirectories. Or think of a company org chart: the CEO sits at the top (root), VPs are their children, and entry-level employees are the leaves (nodes with no children).

A tree structure is naturally self-similar: if you look at any department head, they act as the "CEO" of their own smaller sub-organization (subtree).

This self-similarity is the key mental shift for trees: every tree algorithm is "do something with this node, then delegate the rest to the left and right subtrees." Because of this, recursion is the native language of tree programming.

            (root) Documents
           /        |        \
       Photos     Work      Music
       /    \       |
   2025    2026   resume.pdf     ← leaves: nodes with no children

Vocabulary to memorize:

• Root: The top-most node with no parent.
• Leaf: A node with no children.
• Subtree: A node and all of its descendants.
• Depth: Distance from the root node.
• Height: The number of edges on the longest path from a node to a leaf.

A binary tree allows at most two children per node — left and right — and is the form 90% of interview tree questions take.

Core Structure and Basic Operations

Here is how to define a binary tree node and calculate basic properties (height and size) in Python, Java, and C++:

# Python
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def height(node):
    if node is None:                 # base case: empty tree has height -1
        return -1
    return 1 + max(height(node.left), height(node.right))

def count(node):
    if node is None:
        return 0
    return 1 + count(node.left) + count(node.right)

// Java
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

class TreeOps {
    public int height(TreeNode node) {
        if (node == null) {          // base case: empty tree has height -1
            return -1;
        }
        return 1 + Math.max(height(node.left), height(node.right));
    }

    public int count(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + count(node.left) + count(node.right);
    }
}

// C++
#include <algorithm>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int height(TreeNode* node) {
    if (node == nullptr) {           // base case: empty tree has height -1
        return -1;
    }
    return 1 + std::max(height(node->left), height(node->right));
}

int count(TreeNode* node) {
    if (node == nullptr) {
        return 0;
    }
    return 1 + count(node->left) + count(node->right);
}

Two lines of pattern — null check, combine recursive answers — and you can already compute size, height, sums, mirror a tree, compare two trees…

The four traversals

Same tree, four different visit orders — the only question is when each node gets to speak. Flip between them and watch the output row; notice in-order reading the BST in sorted order, and level-order being plain BFS:

"Visit every node" has four standard orders, and naming them is interview table stakes:

# DFS: In-order traversal
# Python
def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)

// Java
import java.util.List;

public void inorder(TreeNode node, List<Integer> out) {
    if (node == null) {
        return;
    }
    inorder(node.left, out);
    out.add(node.val);
    inorder(node.right, out);
}

// C++
#include <vector>

void inorder(TreeNode* node, std::vector<int>& out) {
    if (node == nullptr) {
        return;
    }
    inorder(node->left, out);
    out.push_back(node->val);
    inorder(node->right, out);
}

The first three are DFS (depth-first — dive, then backtrack: a stack discipline, via recursion). Level-order is BFS (breadth-first — a queue holding the current frontier):

# BFS: Level-order traversal
# Python
from collections import deque

def level_order(root):
    if not root: return []
    out, q = [], deque([root])
    while q:
        node = q.popleft()
        out.append(node.val)
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)
    return out

// Java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public List<Integer> levelOrder(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    if (root == null) return out;
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        TreeNode node = q.poll();
        out.add(node.val);
        if (node.left != null)  q.add(node.left);
        if (node.right != null) q.add(node.right);
    }
    return out;
}

// C++
#include <vector>
#include <queue>

std::vector<int> levelOrder(TreeNode* root) {
    std::vector<int> out;
    if (root == nullptr) return out;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        out.push_back(node->val);
        if (node->left != nullptr)  q.push(node->left);
        if (node->right != nullptr) q.push(node->right);
    }
    return out;
}

These are the same DFS/BFS you'll meet on graphs — a tree is just a graph with no cycles, so trees are where you learn them gently.

Binary Search Trees: sorted order as a shape

A BST adds one rule to a binary tree: at every node, left subtree < node < right subtree. That single invariant turns the tree into a decision diagram for search:

            8
          /   \
         3     10        find 6: 6<8 go left, 6>3 go right,
        / \      \                6=6 found — 3 comparisons,
       1   6     14               not a scan

Each comparison discards an entire subtree — the same halving as binary search, but in a structure that also supports insertion and deletion without shifting anything (unlike a sorted array):

Read that table's last two rows — they're the BST's reason to exist: hash tables answer exact lookups; BSTs answer order questions (min, max, range, nearest, rank) while staying fast to modify.

# Python
def search(node, target):
    if node is None or node.val == target:
        return node
    if target < node.val:
        return search(node.left, target)
    return search(node.right, target)

// Java
public TreeNode search(TreeNode node, int target) {
    if (node == null || node.val == target) {
        return node;
    }
    if (target < node.val) {
        return search(node.left, target);
    }
    return search(node.right, target);
}

// C++
TreeNode* search(TreeNode* node, int target) {
    if (node == nullptr || node.val == target) {
        return node;
    }
    if (target < node.val) {
        return search(node->left, target);
    }
    return search(node->right, target);
}

Watch it run

Build a BST by inserting values one at a time, then search — every comparison discards a whole subtree. Now change the insert order to 1, 2, 3, 4, 5, 6, 7 and watch the next section's warning come true.

The catch: balance

Insert 1, 2, 3, 4, 5 in order and the "tree" becomes a chain hanging right — height n, every operation O(n). A linked list with extra steps. All the O(log n) promises hold only if height stays ~log n: a balanced tree.

Self-balancing BSTs — AVL trees, Red-Black trees — restructure themselves with O(1)-ish rotations on every insert/delete to guarantee O(log n) height. You will almost never implement one (say that confidently in interviews — knowing that is the senior answer), but you use them daily: Java's TreeMap, C++'s std::map/std::set are Red-Black trees. And databases use the same idea, generalized: the B-tree — a BST flattened into fat nodes matching disk pages — is the database index (indexing, Level 9; it's why ORDER BY and range scans are fast).

Production perspective

• Every std::map, TreeMap, database index, and filesystem directory structure is this page. The DOM your browser renders, the JSON your API returns, the org chart in HR software — trees.
• Heaps (next-but-one page) are binary trees with a different invariant (parent beats children) stored in an array — same shape, different promise.
• Compilers parse your code into a tree (the AST) and every analysis is a traversal — when Level 8 tooling (linters, bundlers) feels magical, it's post-order walks.

Common mistakes

• Forgetting the base case — if node is None: return ... is line one of every tree function; omit it and you recurse into a crash.
• Checking only children, not subtrees, for BST validity — 5 → right: 8 → left: 3 passes the child check but breaks the invariant (3 < 5 yet sits in 5's right subtree). Validate with bounds passed down (see QA below) — this is among the most-failed easy questions.
• Confusing depth and height, or height of empty tree (-1) vs leaf (0) — define it out loud before coding.
• Assuming BST when given "binary tree" — no order invariant means no binary-search shortcuts; read the problem.
• Recursion depth — a chain-shaped tree of 10⁵ nodes overflows Python's default recursion limit; the iterative-with-stack version exists for a reason.

Think it through

The page's ladder flags one habit as the senior tree skill: a node returns one value to its parent while you track a different answer on the side. Reason through the cleanest example before revealing.

// Java — Diameter of Binary Tree
class DiameterSolution {
    private int best = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        best = 0;
        height(root);
        return best;
    }

    private int height(TreeNode node) {
        if (node == null) {
            return -1; // height in edges; empty node returns -1
        }
        int lh = height(node.left);
        int rh = height(node.right);
        best = Math.max(best, lh + rh + 2); // path bending at node
        return 1 + Math.max(lh, rh);
    }
}

// C++ — Diameter of Binary Tree
#include <algorithm>

class DiameterSolution {
    int best = 0;
    
    int height(TreeNode* node) {
        if (node == nullptr) {
            return -1; // height in edges; empty node returns -1
        }
        int lh = height(node->left);
        int rh = height(node->right);
        best = std::max(best, lh + rh + 2); // path bending at node
        return 1 + std::max(lh, rh);
    }
public:
    int diameterOfBinaryTree(TreeNode* root) {
        best = 0;
        height(root);
        return best;
    }
};

Check yourself

Interview perspective

Practice

1. Warm-up (recursion reps): implement height, count, sum, and mirror (swap every left/right). Each is ≤5 lines; do them from memory.
2. Traversals: build the BST from the diagram above by inserting 8,3,10,1,6,14; print all four traversals; confirm in-order comes out sorted.
3. The canon: validate-BST (bounds method), level-order traversal grouped by level (the output is [[8],[3,10],[1,6,14]] — where does the per-level boundary come from?), LCA both ways.
4. Think in invariants: you need a leaderboard supporting "insert score," "delete score," and "how many scores are higher than X?" — compare hash table, sorted array, and BST honestly, then pick. (The rank query is the tell.)

Next: Tries — trees whose paths are the data, powering autocomplete everywhere.

Practice — climb the ladder

Almost every tree problem is "pick a traversal + decide what each node returns to its parent". Say those two choices out loud before coding.