Basic Tree Questions

Five fundamental operations on a binary tree. Every harder tree problem you’ll see builds on these — get them automatic and the practice questions become routine.

For all examples, assume a TreeNode defined as:

1. Inorder Traversal (Left → Root → Right)

For a BST, inorder traversal visits nodes in sorted ascending order — that single property powers a huge number of BST problems.

Time: O(n) — every node visited once. Space: O(h) for the recursion stack, where h is the tree’s height.

2. Preorder Traversal (Root → Left → Right)

Useful when you need to process the root first — e.g. serializing a tree, copying a tree, computing a path from root to anywhere.

3. Postorder Traversal (Left → Right → Root)

The right choice when you need to process children before the parent — e.g. computing a node’s height (need both children’s heights first), deleting a tree (free children, then the root).

All three traversals are the same algorithm — just the position of the “visit” statement changes. Pre = visit first, In = visit middle, Post = visit last. The recursion stack handles the rest.

4. Height of a Binary Tree

A tree’s height is the longest path from the root to any leaf. Postorder fits this naturally: a node’s height depends on its children’s heights.

height(node) = 0                                    if node is null
             = 1 + max(height(left), height(right)) otherwise

Time: O(n) — touch every node once. Space: O(h) for the call stack.

5. Count the Nodes

Same recursive shape. Each node contributes 1 plus whatever the subtrees contribute.

The pattern to notice

Every solution above has the same shape:

solve(node):
    if node is null:
        return base value
    left_answer  = solve(node.left)
    right_answer = solve(node.right)
    return combine(node, left_answer, right_answer)

Three questions: base case for null, recursive call on each child, how to combine. Once you have those, the tree problem is written.

This is the same three-question recipe from Day 5 — Thinking Recursively, applied to trees. The recursion does all the bookkeeping; you only describe one level.

Extra problems

Try these on your own. Each is a 5-line variation on the templates above.

Find the maximum value in a binary tree.

Sum all values in a binary tree.

Count leaf nodes (nodes with no children).

Ready for the harder versions? Head to Practice Questions.

BST Operations Overview