Tree Traversals and Information Flow

Most binary tree interview problems are solved with a short recursive function, and most of the difficulty is deciding what that function should take as parameters and what it should return. The traversal names, preorder, inorder and postorder, sound like three algorithms to memorise. They’re really one algorithm with a single choice: do you handle the current node before its children, between them, or after them?

The way to make that choice is to ask which direction information has to flow. Does a node need to know something about its ancestors, or about its descendants? Answer that and the traversal picks itself.

One tree, three orders

Here’s a binary search tree used throughout this note, built from the level-order list [8, 3, 10, 1, 6, None, 14, None, None, 4, 7] (the format LeetCode uses):

        8
      /   \
     3     10
    / \      \
   1   6      14
      / \
     4   7

The three traversals as one-liners:

def preorder(n):  return [] if n is None else [n.val] + preorder(n.left) + preorder(n.right)
def inorder(n):   return [] if n is None else inorder(n.left) + [n.val] + inorder(n.right)
def postorder(n): return [] if n is None else postorder(n.left) + postorder(n.right) + [n.val]

preorder:  [8, 3, 1, 6, 4, 7, 10, 14]
inorder:   [1, 3, 4, 6, 7, 8, 10, 14]
postorder: [1, 4, 7, 6, 3, 14, 10, 8]

All three visit every node once. Preorder sees the root first, so it’s natural for copying or serialising a tree (you need the parent before you can attach children). Postorder sees the root last, after both subtrees are done, so it’s natural for anything that combines results from children, like computing sizes or freeing memory. Inorder sees left subtree, node, right subtree, which on a binary search tree means smallest to largest: the output above is sorted.

These one-liners build new lists at every level, so they’re fine for illustration but cost O(n · h) time from the list concatenation. In an interview, append to a shared result list instead.

Bottom-up: when a node needs its children’s answers

The height of a node depends on the heights of its children: one more than the taller of the two. You can’t know it until both children are finished, so this is postorder by necessity. The recursion returns the information upward.

Diameter of Binary Tree shows the pattern clearly. The diameter is the number of edges on the longest path between any two nodes, and that path may not pass through the root. Every path has a highest point where it bends, and the longest path bending at a node uses the height of its left subtree plus the height of its right subtree. So compute heights bottom-up and, at each node, check whether the bend there beats the best so far:

def diameter(root):
    best = 0
    def height(node):                    # postorder: children first, then combine
        nonlocal best
        if node is None:
            return 0
        lh, rh = height(node.left), height(node.right)
        best = max(best, lh + rh)        # longest path that bends at this node, in edges
        return 1 + max(lh, rh)
    height(root)
    return best

diameter: 5 3 1

For the example tree the longest path is 4 → 6 → 3 → 8 → 10 → 14, five edges, bending at the root. For [1, 2, 3, 4, 5] it’s 3 and for [1, 2] it’s 1.

Notice that the function computes two different things. It returns the height, because that’s what the parent needs. It records the diameter on the side, because that’s what the caller wants. Mixing those two up is the classic mistake here: if height returned lh + rh, the parent would try to extend a path that already uses both branches, which isn’t a path at all. Asking “what does my parent need from me?” separately from “what’s the final answer?” is the habit that solves most tree problems, including the practice question below.

Top-down: when a node needs its ancestors’ context

Some facts flow the other way. Whether a node is valid in a binary search tree depends on every ancestor above it, not just its parent. Those constraints are passed down as parameters, and the node is checked before its children: preorder.

The tempting wrong answer checks only parent and child:

def is_bst_local(node):
    if node is None:
        return True
    if node.left and node.left.val >= node.val:
        return False
    if node.right and node.right.val <= node.val:
        return False
    return is_bst_local(node.left) and is_bst_local(node.right)

Here’s a tree it gets wrong, [5, 4, 6, None, None, 3, 7]:

      5
     / \
    4   6
       / \
      3   7

Every parent-child pair looks fine: 3 < 6 and 7 > 6. But 3 is in the right subtree of 5, so it must be greater than 5. The correct version carries an allowed range down the tree. Going left tightens the upper bound to the current value; going right tightens the lower bound:

def is_bst(node, low=float("-inf"), high=float("inf")):
    if node is None:
        return True
    if not (low < node.val < high):      # must respect every ancestor, not just the parent
        return False
    return is_bst(node.left, low, node.val) and is_bst(node.right, node.val, high)

local check: True  bounds check: False  on the first tree: True

When the recursion reaches 3, the range is (5, 6): the lower bound came from going right at 5, the upper from going left at 6. 3 falls outside it. This is the bug interviewers are listening for on Validate Binary Search Tree. An alternative is an inorder traversal that checks each value is greater than the previous one, using the sorted-order property.

Inorder and sorted order

Because inorder on a BST yields sorted values, “find the kth smallest” is “stop the inorder traversal after k nodes”. Doing it iteratively with an explicit stack lets you stop early without unwinding recursion:

def kth_smallest(root, k):
    stack, node = [], root
    while stack or node:
        while node:                      # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()               # the next value in sorted order
        k -= 1
        if k == 0:
            return node.val
        node = node.right
    return None

kth smallest: [1, 4, 14]

Those are k = 1, 3, 8 on the example tree. The time is O(h + k), since you descend to the leftmost node and then visit only k nodes, rather than O(n) for a full traversal. That’s the answer to Kth Smallest Element in a BST. The explicit stack also illustrates what recursion does behind the scenes.

All of these traversals take O(n) time to visit the whole tree. Space is O(h) for the recursion or the explicit stack, where h is the height: O(log n) for a balanced tree, O(n) for a degenerate one that’s effectively a linked list. If you’re asked to traverse level by level instead, that’s breadth-first search with a queue, covered in the BFS note.

Interview practice: maximum path sum

A path in a binary tree is any sequence of nodes connected by edges, each used at most once. It doesn’t have to pass through the root, and node values can be negative. Return the largest sum of any non-empty path. For [-10, 9, 20, None, None, 15, 7] the answer is 42, from 15 → 20 → 7.

Answer

This is the diameter pattern with values instead of edge counts, plus negatives. Information must flow upward, so use postorder with a return value, and separate what the parent needs from what the caller wants:

• Return the best sum of a path that starts at this node and goes down one side. A parent can extend only that kind of path, because a path that already uses both of a node’s children can’t also go up.
• Record the best path that bends here: the node’s value plus the best downward gain from each side.

Negative branches need one more decision: if a child’s best downward gain is negative, including it only hurts, so clamp it to zero (take neither branch).

def max_path_sum(root):
    best = float("-inf")
    def gain(node):
        """Best sum of a path that starts at node and goes down one side."""
        nonlocal best
        if node is None:
            return 0
        left = max(gain(node.left), 0)       # a negative branch is better left out
        right = max(gain(node.right), 0)
        best = max(best, node.val + left + right)   # path that bends here
        return node.val + max(left, right)   # a parent can extend only one side
    gain(root)
    return best

[1, 2, 3] -> 6
[-10, 9, 20, None, None, 15, 7] -> 42
[-3] -> -3
[2, -1] -> 2
[5, 4, 8, 11, None, 13, 4, 7, 2, None, None, None, 1] -> 48

At node 20, the left gain is 15 and the right gain is 7, so the bend there is 20 + 15 + 7 = 42, which becomes best. It returns 20 + 15 = 35 to its parent. At the root, -10 + 9 + 35 = 34 is smaller, so 42 stands. Two details matter in the edge cases. best starts at negative infinity, not 0, so a single-node tree [-3] correctly returns -3 instead of claiming an empty path. And the clamp means [2, -1] returns 2 by leaving the negative child out. The last tree’s answer, 48, is the path 7 → 11 → 4 → 5 → 8 → 13.

Time is O(n) and space is O(h) for the recursion. You can run your version on Binary Tree Maximum Path Sum, and Maximum Depth of Binary Tree is the gentle warm-up for the same return-value pattern.

Where to go from here

• Data Structures and Algorithms interview questions
• DSA multiple-choice questions
• Breadth-First Search and Unweighted Shortest Paths, for level-order traversal
• Algorithm Space Complexity and Auxiliary Storage, on the O(h) recursion cost
• MIT 6.006 Introduction to Algorithms (Spring 2020), lectures 6 and 7 cover binary trees