Tree traversals

Implement a TreeNode class and write inorder, preorder, and postorder traversal functions and a height function in Python.

The three traversal orders from the previous lesson — inorder, preorder, postorder — each follow the same recursive skeleton: handle the base case (empty node), then combine results from the left subtree, the current node, and the right subtree in the defining order. The only thing that changes is which of those three contributions comes first.

Implementation

Python — editable, runs in your browser

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

def inorder(root):
  """Left -> root -> right. Returns a list of values."""
  if root is None:
      return []
  return inorder(root.left) + [root.val] + inorder(root.right)

def preorder(root):
  """Root -> left -> right. Returns a list of values."""
  if root is None:
      return []
  return [root.val] + preorder(root.left) + preorder(root.right)

def postorder(root):
  """Left -> right -> root. Returns a list of values."""
  if root is None:
      return []
  return postorder(root.left) + postorder(root.right) + [root.val]

def height(root):
  """Height = edges on the longest root-to-leaf path. Empty tree = 0."""
  if root is None:
      return 0
  return 1 + max(height(root.left), height(root.right))

# Build the example tree:
#       4
#      / \
#     2   6
#    / \ / \
#   1  3 5  7

root = TreeNode(
  4,
  TreeNode(2, TreeNode(1), TreeNode(3)),
  TreeNode(6, TreeNode(5), TreeNode(7)),
)

print("Inorder:  ", inorder(root))    # [1, 2, 3, 4, 5, 6, 7]
print("Preorder: ", preorder(root))   # [4, 2, 1, 3, 6, 5, 7]
print("Postorder:", postorder(root))  # [1, 3, 2, 5, 7, 6, 4]
print("Height:   ", height(root))     # 3

# A skewed tree (linked-list shaped):
skewed = TreeNode(1, TreeNode(2, TreeNode(3)))
print()
print("Skewed inorder:", inorder(skewed))    # [1, 2, 3]  — leftmost first
print("Skewed height: ", height(skewed))     # 3

How the recursion works

Each traversal function has the same shape:

Base case: if the node is None, return an empty list.
Recursive case: build the result by combining the left subtree result, the current value, and the right subtree result — in the order that defines the traversal.

For inorder, the call tree for the root node 4 looks like:

inorder(4)
  = inorder(2) + [4] + inorder(6)
  = (inorder(1) + [2] + inorder(3)) + [4] + (inorder(5) + [6] + inorder(7))
  = ([] + [1] + []) + [2] + ([] + [3] + []) + [4] + ...
  = [1, 2, 3, 4, 5, 6, 7]

Each call processes exactly one node and two smaller subproblems. The total work is O(n) — each node is visited exactly once.

Height by recursion

height follows the same pattern. The height of a node is 1 plus the maximum height of its two subtrees. The base case (empty node) returns 0, which means a single-node leaf returns 1 + max(0, 0) = 1. The formula propagates correctly up to the root.

Some definitions count height as the number of nodes on the longest path rather than edges. Under that definition a single node has height 1 and the base case returns 0. The code above uses the edge-count convention (single node = height 1, empty tree = 0), which matches most textbooks.

Building trees for testing

The TreeNode(val, left, right) constructor with optional arguments lets you express a tree as a nested literal. Deep nesting becomes unreadable — a small helper that inserts values level by level is useful for larger tests, but for the exercises in this track the nested form is clear enough.

Where to go next

Next: binary search trees — the BST invariant, why inorder traversal produces sorted output, and why balance is the difference between O(log n) and O(n) operations.

Finished reading? Mark it complete to track your progress.

Implementation

How the recursion works

Height by recursion

Building trees for testing

Where to go next

On this page