Portfolio/Learn/Binary Trees: Traversals, Properties & Recursive Thinking
Algorithms & DSIntermediate

Binary Trees: Traversals, Properties & Recursive Thinking

Build deep intuition for binary trees — inorder, preorder, postorder traversals, tree properties, and the recursive patterns that solve 90% of tree problems.

18 min read
March 15, 2026
Binary TreesRecursionDFSBFSTraversalPython

Thinking Recursively About Trees

Every binary tree problem follows the same mental model: solve the problem for the left subtree, solve it for the right subtree, and combine the results at the current node. The base case is always a null node. Once you internalize this pattern, tree problems become mechanical.

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

The Three DFS Traversals

Inorder (Left-Root-Right) gives sorted order for BSTs. Preorder (Root-Left-Right) is used for serialization and copying trees. Postorder (Left-Right-Root) is used for deletion and bottom-up calculations. Understanding when to use each is critical.

python
def inorder(root: TreeNode | None) -> list[int]:
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)


def preorder(root: TreeNode | None) -> list[int]:
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)


def postorder(root: TreeNode | None) -> list[int]:
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]


# Iterative inorder using a stack (important for interviews)
def inorder_iterative(root: TreeNode | None) -> list[int]:
    result = []
    stack = []
    curr = root

    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        result.append(curr.val)
        curr = curr.right

    return result

Level-Order Traversal (BFS)

python
from collections import deque

def level_order(root: TreeNode | None) -> list[list[int]]:
    """Return node values level by level."""
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)

    return result

Tree Properties

Most tree problems reduce to computing a property: height, diameter, balance, symmetry, or path sums. The pattern is always the same — recursively compute the property for subtrees, then combine.

python
def max_depth(root: TreeNode | None) -> int:
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))


def is_balanced(root: TreeNode | None) -> bool:
    """Check if heights of left and right subtrees differ by at most 1."""
    def check(node):
        if not node:
            return 0
        left = check(node.left)
        right = check(node.right)
        if left == -1 or right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)

    return check(root) != -1


def diameter(root: TreeNode | None) -> int:
    """Longest path between any two nodes (number of edges)."""
    result = 0

    def depth(node):
        nonlocal result
        if not node:
            return 0
        left = depth(node.left)
        right = depth(node.right)
        result = max(result, left + right)
        return 1 + max(left, right)

    depth(root)
    return result

The 'diameter' pattern — using a global variable updated during recursion — is extremely common. It applies to maximum path sum, longest zigzag path, and many other problems where the answer passes through nodes rather than ending at them.

Lowest Common Ancestor (LCA)

Finding the LCA of two nodes is a fundamental operation used in distance calculations, path queries, and tree comparisons. The recursive solution is elegant: if both targets are in different subtrees, the current node is the LCA.

python
def lowest_common_ancestor(root, p, q):
    """Find the lowest common ancestor of nodes p and q."""
    if not root or root == p or root == q:
        return root

    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)

    if left and right:
        return root  # p and q are in different subtrees
    return left or right

For BSTs, LCA is simpler: if both values are less than root, go left. If both are greater, go right. Otherwise, root is the LCA. This runs in O(h) instead of O(n).

More Articles