Binary Trees & BST — Traversals, DFS, BFS and the Recursive Mindset

A binary tree is a structure where each node has at most two children, left and right. Trees model hierarchies (folders, org charts, HTML) and they're one of the most asked interview topics because they test recursion so well.

        1
       / \
      2   3
     / \
    4   5

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

Vocabulary: root (top), leaf (no children), height/depth (levels from root), subtree (a node plus everything below it).

The recursive mindset

Almost every tree problem fits this shape:

Answer for a node = combine(answer for left subtree, answer for right subtree, the node itself). Base case: an empty tree (None).

Maximum depth:

def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Invert (mirror) a tree: swap the children, then invert each subtree. Same tree: both empty → true; values equal and both subtrees same → true. Each is 3–5 lines with this mindset. Every node is visited once → O(n) time, O(h) space for the recursion (h = height).

DFS traversals: preorder, inorder, postorder

The three orders differ only in when you visit the node relative to its children:

Order	Visit	Result for the tree above	Typical use
Preorder	node, left, right	1 2 4 5 3	copy/serialise a tree
Inorder	left, node, right	4 2 5 1 3	BST → sorted order
Postorder	left, right, node	4 5 2 3 1	compute from children first (heights, deletion)

def inorder(root, out):
    if not root:
        return
    inorder(root.left, out)
    out.append(root.val)        # move this line to get pre/postorder
    inorder(root.right, out)

BFS: level order traversal

Process the tree level by level with a queue. Take the queue's current size to know how many nodes belong to this level.

from collections import deque

def level_order(root):
    if not root:
        return []
    res, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):              # exactly one level
            node = q.popleft()
            level.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        res.append(level)
    return res

Right Side View = the last node of each level. Minimum depth = the first level that contains a leaf. BFS is the natural fit whenever the question says "level".

Postorder power: return info upward

Diameter = the longest path between any two nodes. At each node the longest path through it is left_height + right_height. Compute heights bottom-up and track the best diameter on the way:

def diameter(root):
    best = 0
    def height(node):
        nonlocal best
        if not node:
            return 0
        l, r = height(node.left), height(node.right)
        best = max(best, l + r)          # path through this node
        return 1 + max(l, r)             # height to report upward
    height(root)
    return best

Balanced tree and Binary Tree Maximum Path Sum use the same "return one thing, update a global answer" trick.

Lowest Common Ancestor (LCA)

The LCA of p and q is the deepest node that has both below it (a node can be its own ancestor).

def lca(root, p, q):
    if not root or root is p or root is q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:
        return root          # p and q are on different sides
    return left or right     # both on one side

Binary Search Trees (BST)

A BST keeps every value in the left subtree smaller and every value in the right subtree larger than the node. That ordering gives O(h) search (O(log n) when balanced):

def search_bst(root, x):
    while root and root.val != x:
        root = root.left if x < root.val else root.right
    return root

Validate a BST: it's not enough to compare a node with its children — every node must fit within a range set by its ancestors.

def is_valid_bst(root, lo=float('-inf'), hi=float('inf')):
    if not root:
        return True
    if not (lo < root.val < hi):
        return False
    return is_valid_bst(root.left, lo, root.val) and is_valid_bst(root.right, root.val, hi)

Kth smallest in a BST: an inorder traversal visits BST values in sorted order — stop at the k-th.

How to recognise the approach

Question	Approach
depth, height, balanced, diameter, path sum	DFS returning a value (postorder)
level, row, right/left view, zigzag	BFS with a queue
sorted order, kth smallest, BST validation	inorder / range limits
ancestor, path between nodes	LCA recursion

Common mistakes

1. Forgetting the None base case.
2. Validating a BST by checking only parent–child pairs.
3. In BFS, not fixing the level size before the inner loop.
4. Confusing height (edges or nodes?) — state your convention.

Key takeaways

• Think recursively: solve left, solve right, combine. Base case: empty tree.
• DFS (pre/in/post) for depth-style questions, BFS (queue) for level-style questions.
• BST = ordered tree: inorder is sorted, search is O(h).