Binary Trees

Updated Nov 16, 2026 · 4 min read
On this page

    Folder structures, org charts, expression parsers and decision rules are all hierarchies, and a flat list can't answer questions like "how deep is this?" or "what do these two have in common?" without a lot of bookkeeping. Trees are the most common data structure in coding interviews after arrays and hash maps, and almost every tree question is solved with the same small idea: ask each child for an answer, then combine.

    How it works

    Nodes with up to two children

    The root is at the top; nodes without children are leaves; every node is the root of its own subtree.
    The root is at the top; nodes without children are leaves; every node is the root of its own subtree.

    A binary tree is made of nodes, each holding a value and pointers to at most two children, left and right.

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

    The words you'll use in every tree problem:

    • Root: the top node. Leaf: a node with no children.
    • Subtree: any node together with everything below it. Every subtree is itself a binary tree, which is why recursion fits so well.
    • Depth of a node: edges from the root. Height of a tree: the number of levels on its longest root-to-leaf path. A tree with n nodes has height between about log₂ n (balanced) and n (a chain).

    Visiting every node: DFS and BFS

    Preorder, inorder and postorder differ only in when the node is processed relative to its two subtrees; level order goes row by row.
    Preorder, inorder and postorder differ only in when the node is processed relative to its two subtrees; level order goes row by row.

    Depth-first search (DFS) goes all the way down one branch before backing up. It comes in three orders, depending on when you handle the node itself:

    • Preorder (node, left, right): copying or serializing a tree, because you see a parent before its children.
    • Inorder (left, node, right): on a binary search tree, this visits values in sorted order.
    • Postorder (left, right, node): when a node's answer depends on its children's answers (height, sums, diameters).

    Breadth-first search (BFS), or level order, visits row by row using a queue. Use it when the question mentions levels, the left or right view, or the nearest something.

    The core idea: answer from the children

    Each node's depth is one more than the larger of its children's depths; an empty child counts as 0.
    Each node's depth is one more than the larger of its children's depths; an empty child counts as 0.

    Most tree problems are solved by writing one recursive function and trusting it on the children:

    1. Base case: what is the answer for an empty tree (None)?
    2. Recursive case: get the answers for left and right, then combine them with the current node.

    Maximum depth is the simplest example: depth(node) = 1 + max(depth(left), depth(right)), and depth(None) = 0.

    Operations and costs

    OperationCost
    Visit every node (any DFS order or BFS)O(n) time
    Recursion stack for DFSO(h) space, where h is the height
    BFS queueO(w) space, where w is the widest level (up to about n/2)
    Find a value in a plain binary treeO(n): no ordering, so you may check every node

    For a balanced tree h is O(log n); for a skewed tree (a chain) h is O(n), so recursive DFS can use O(n) stack.

    When to reach for it

    • The input is a tree: almost always DFS with a recursive helper, or BFS if the problem talks about levels.
    • You need the answer for a node from its children's answers: postorder DFS that returns values.
    • You need information from the path above a node (current sum, allowed range, depth): DFS that passes values down as parameters.
    • You need both: return one thing up and track a global best on the side (diameter, maximum path sum).

    Example

    Maximum depth with DFS, and level order with BFS:

    from collections import deque
    
    def max_depth(root):
        if root is None:
            return 0
        return 1 + max(max_depth(root.left), max_depth(root.right))
    
    def level_order(root):
        if not root:
            return []
        out, q = [], deque([root])
        while q:
            level = []
            for _ in range(len(q)):          # exactly the nodes of this level
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            out.append(level)
        return out

    The depth function in the other three languages:

    int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
    func maxDepth(root *TreeNode) int {
        if root == nil {
            return 0
        }
        return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
    }

    (Go 1.21 and later has a built-in max; on older versions write a two-line helper.)

    Time: O(n) for both. Space: O(h) for the recursion, O(w) for the BFS queue. For the tree in the pictures, depth is 3 and level order is [[1], [2, 3], [4, 5, 6]].

    Common mistakes

    • Missing the base case. Every recursive tree function must handle None first.
    • Returning the wrong thing. Decide what the function returns for a subtree (a height? a sum? a boolean?) and keep it consistent.
    • Mixing up "return up" and "best overall". In diameter or path-sum problems the value you return to the parent is not the answer; keep the answer in a separate variable.
    • Only checking a node against its children. Some properties (like "valid BST") depend on all ancestors, so pass a range down.
    • Forgetting the level size in BFS. Take len(q) before the inner loop, or levels blur together.
    • Stack overflow on deep trees. If the tree can be a long chain (10⁵ nodes), mention an iterative version with an explicit stack.

    Say this in the interview

    • "I'll write a recursive helper that returns the height of a subtree; each node combines its children's heights."
    • "This visits each node once, so O(n) time and O(h) space for the recursion, which is O(log n) if balanced and O(n) in the worst case."
    • "The question is about levels, so I'll use BFS with a queue and process one level per outer loop."

    Used in