DSA · Lesson 10 of 17

Binary Trees & BSTs

⏱ 14 min🎬 Interactive visualizer💻 Python · Java · C++ · JavaScript🧩 9 practice problems

Recursion on trees: DFS in pre-, in- and post-order, BFS level by level, and the binary-search-tree property. The most common interview topic after arrays.

The idea

A binary tree node has a value and up to two children. Almost every tree problem is solved by asking: if I knew the answer for the left and right subtrees, how would I combine them at this node? That is recursion.

Traversals

Order	Visit	Typical use
Pre-order	node, left, right	copy or serialise a tree, path problems from the root
In-order	left, node, right	BST gives sorted order; k-th smallest, validate BST
Post-order	left, right, node	height, diameter, delete tree: needs children first
Level-order (BFS)	level by level with a queue	right-side view, min depth, zigzag, connect next pointers

Binary search tree (BST)

Every value in the left subtree is smaller and every value in the right subtree is larger. Search, insert and delete walk one path: O(h), which is O(log n) when balanced and O(n) when skewed. Balanced variants (AVL, red-black) power Java TreeMap and C++ std::map.

The “return a value, update a global” trick

For diameter or maximum path sum, the recursive function returns the best downward path (used by the parent) while updating a global best for paths that bend at the current node.

Code template

from collections import deque

def height(node):                      # post-order
    if not node: return 0
    return 1 + max(height(node.left), height(node.right))

def inorder(node, out):                # sorted order for a BST
    if node:
        inorder(node.left, out); out.append(node.val); inorder(node.right, out)

def level_order(root):                 # BFS
    res, q = [], deque([root] if root else [])
    while q:
        level = []
        for _ in range(len(q)):
            n = q.popleft(); level.append(n.val)
            if n.left: q.append(n.left)
            if n.right: q.append(n.right)
        res.append(level)
    return res

int height(TreeNode node) {                       // post-order
    if (node == null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

void inorder(TreeNode node, List<Integer> out) {  // sorted order for a BST
    if (node == null) return;
    inorder(node.left, out); out.add(node.val); inorder(node.right, out);
}

List<List<Integer>> levelOrder(TreeNode root) {   // BFS
    List<List<Integer>> res = new ArrayList<>();
    Queue<TreeNode> q = new ArrayDeque<>();
    if (root != null) q.add(root);
    while (!q.isEmpty()) {
        List<Integer> level = new ArrayList<>();
        for (int k = q.size(); k > 0; k--) {
            TreeNode n = q.poll(); level.add(n.val);
            if (n.left != null) q.add(n.left);
            if (n.right != null) q.add(n.right);
        }
        res.add(level);
    }
    return res;
}

int height(TreeNode* node) {                       // post-order
    if (!node) return 0;
    return 1 + max(height(node->left), height(node->right));
}

void inorder(TreeNode* node, vector<int>& out) {   // sorted order for a BST
    if (!node) return;
    inorder(node->left, out); out.push_back(node->val); inorder(node->right, out);
}

vector<vector<int>> levelOrder(TreeNode* root) {   // BFS
    vector<vector<int>> res;
    queue<TreeNode*> q;
    if (root) q.push(root);
    while (!q.empty()) {
        vector<int> level;
        for (int k = q.size(); k > 0; k--) {
            TreeNode* n = q.front(); q.pop(); level.push_back(n->val);
            if (n->left) q.push(n->left);
            if (n->right) q.push(n->right);
        }
        res.push_back(level);
    }
    return res;
}

const height = node => node ? 1 + Math.max(height(node.left), height(node.right)) : 0; // post-order

function inorder(node, out = []) {   // sorted order for a BST
  if (node) { inorder(node.left, out); out.push(node.val); inorder(node.right, out); }
  return out;
}

function levelOrder(root) {          // BFS
  const res = [];
  let level = root ? [root] : [];
  while (level.length) {
    res.push(level.map(n => n.val));
    level = level.flatMap(n => [n.left, n.right].filter(Boolean));
  }
  return res;
}

Complexity

Every traversal is O(n) time. Space is O(h) for recursion (h = height) and O(w) for BFS (w = maximum width).

Practise this pattern (9 problems)

Each problem has a statement, hints, approaches, solutions in 4 languages and a code runner. Solve them in order: easy first.

#	Problem	Difficulty
45	Maximum Depth of Binary Tree	Easy
46	Invert Binary Tree	Easy
47	Same Tree	Easy
48	Diameter of Binary Tree	Easy
49	Binary Tree Inorder Traversal	Easy
50	Binary Tree Level Order Traversal	Medium
51	Validate Binary Search Tree	Medium
52	Kth Smallest Element in a BST	Medium
53	Binary Tree Right Side View	Medium

Common mistakes

Validating a BST by comparing only with the direct children: pass down (low, high) bounds.
Confusing depth (from the root) with height (from the leaves).
Deep recursion on a skewed tree: Python’s default recursion limit is about 1000, so use an iterative version or raise the limit.

Check yourself: which traversal of a BST returns the values in sorted order?

In-order (left, node, right).

Check yourself: why is the height computed in post-order?

A node’s height depends on its children’s heights, so the children must be processed first.

🧩 All DSA problems 🎬 Algorithm visualizer 🎓 Certificates

Created by Ajeetkumar