Binary Tree Algorithms: Traversals, Recursion, and Construction

A binary tree is a set of nodes where each node holds a value and links to at most two children, called left and right. The node with no parent is the root, and a node with no children is a leaf. Interview problems usually hand you the root and ask for something about the whole tree.

The examples use this node class and tree.

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

#         4
#        / \
#       2   6
#      / \   \
#     1   3   7
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)),
                TreeNode(6, None, TreeNode(7)))

Tree Traversals

Depth-first search (DFS) follows one branch all the way down before backing up. Its three orders visit the same nodes and differ only in when a node does its own work compared with its children.

Inorder Traversal

Left, then root, then right

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val)
        inorder(root.right)

On the example this prints 1, 2, 3, 4, 6, 7. The example is a binary search tree (BST), meaning every value in a node's left subtree is smaller than the node and every value in its right subtree is larger. Inorder on a BST comes out sorted, which is how you find the kth smallest value.

Preorder Traversal

Root, then left, then right

def preorder(root):
    if root:
        print(root.val)
        preorder(root.left)
        preorder(root.right)

This prints 4, 2, 1, 3, 6, 7. A node runs before its children, so preorder fits problems where information flows down from parent to child. Path sum, which asks whether some root-to-leaf path adds up to a target, works this way. Each call subtracts its own value and passes what is left to its children, and a leaf checks whether the remainder is zero.

Postorder Traversal

Left, then right, then root

def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.val)

This prints 1, 3, 2, 7, 6, 4. A node runs only after both children finish, so postorder fits problems where a node's answer depends on its children's answers, such as height or whether the tree is balanced.

All three take O(n) time and use stack space equal to the tree's height. That is about log n for a balanced tree but n for a tree that is one long chain, deep enough to hit the recursion limit covered in DFS vs BFS.

Level-Order Traversal (BFS)

Breadth-first search (BFS) visits the tree one level at a time using a queue.

from collections import deque

def level_order(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        level = []
        
        for _ in range(level_size):
            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

On the example it returns [[4], [2, 6], [1, 3, 7]]. At the top of each outer loop the queue holds exactly one level, so reading len(queue) first tells the inner loop where this level ends before the children get added behind it. Use it when the problem talks about levels, such as the rightmost node on each one, or wants the shallowest leaf, where BFS can stop at the first leaf it meets.

What Each Call Returns

Most recursive tree solutions follow one shape. Handle the empty tree, recurse on both children, and combine their results.

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

Problems get harder when the answer you want is not what the parent needs back. The diameter of a tree is the number of edges on its longest path between any two nodes, and that path does not have to pass through the root. The longest path that bends at a node is its left height plus its right height, so the helper returns height and keeps the best sum in a separate variable.

def diameter(root):
    best = 0

    def height(node):
        nonlocal best
        if not node:
            return 0
        left, right = height(node.left), height(node.right)
        best = max(best, left + right)   # longest path that bends here
        return 1 + max(left, right)      # what the parent needs

    height(root)
    return best

On the example the best path bends at the root, from 1 up to 4 and down to 7, for 4 edges. Returning the diameter from height is the usual mistake, since the parent can't use it.

Validating a BST

Comparing each node only with its two children passes the tree below, which is not a BST, because 6 sits in the left subtree of 5.

    5
   / \
  3   8
   \
    6

Every value in 5's left subtree must be less than 5, including grandchildren the local check never compares with 5. The fix passes an allowed range down the tree, the preorder pattern from earlier.

def is_valid_bst(node, low=float("-inf"), high=float("inf")):
    if not node:
        return True
    if not (low < node.val < high):
        return False
    return (is_valid_bst(node.left, low, node.val) and
            is_valid_bst(node.right, node.val, high))

Going left, the parent's value becomes the new upper bound. Going right, it becomes the new lower bound. Checking that the inorder output is strictly increasing also works.

Building a Tree From Two Traversals

A single traversal's list of values can't pin down a general binary tree. The preorder [1, 2] fits a root 1 with 2 as either its left or its right child. Preorder plus inorder is enough when the values are distinct. The first preorder value is the root. In the inorder list, the values before it form the left subtree and the values after it form the right.

def build_tree(preorder, inorder):
    index = {val: i for i, val in enumerate(inorder)}
    next_root = iter(preorder)

    def build(lo, hi):  # builds the subtree for inorder[lo:hi]
        if lo == hi:
            return None
        root = TreeNode(next(next_root))
        mid = index[root.val]
        root.left = build(lo, mid)  # left first, the order preorder lists them
        root.right = build(mid + 1, hi)
        return root

    return build(0, len(inorder))

The dictionary finds each root's inorder position in O(1), where searching the list would make the build quadratic when the tree is one long chain. Postorder plus inorder works the same way from the back. The last postorder value is the root, and walking backward you build the right subtree before the left.

Trees show up constantly in interviews, so these patterns are worth drilling with the routine in LeetCode interview tips.