Is the Binary Trees — traversals and recursion lesson free?

Yes. The first 5 lessons on PyRun are free forever — no signup, no card. Binary Trees — traversals and recursion runs real Python in your browser via Pyodide.

How long does the Binary Trees — traversals and recursion lesson take?

About 12 minutes end-to-end. It's a hands-on lesson — you read a paragraph, edit the code, and run it in the same tab.

Do I need to install Python to try the Binary Trees — traversals and recursion lesson?

No install required. PyRun runs real CPython in your browser via Pyodide (Python compiled to WebAssembly). Works on Chrome, Firefox, Safari, and Edge — desktop or mobile.

What level is the Binary Trees — traversals and recursion lesson?

Advanced level. Assumes comfort with classes, functions, and standard library. Not for first-time Python learners.

← All lessons

Advanced·12 min·dsa · trees · recursion · interview

Binary Trees — traversals and recursion

Binary Trees

A binary tree is a node with up to two children. That single rule — 'at most two' — unlocks a family of structures behind expression parsers, filesystems, decision models, and every balanced-tree database index.

The four traversals

Depth-first traversals are defined by when you visit the current node relative to its children:

Preorder (node, left, right) — good for cloning a tree or emitting a prefix expression.
Inorder (left, node, right) — on a BST, this yields sorted order.
Postorder (left, right, node) — perfect for freeing memory or evaluating an expression tree, because children are done before the parent.

The fourth is level-order (BFS): visit depth 0, then depth 1, then depth 2. It needs a queue rather than recursion.

Recursive vs iterative

Recursion mirrors the definition of a tree, so the code is short. The cost is stack depth: a skewed tree of 10,000 nodes will blow Python's default recursion limit of 1000. Iterative versions use an explicit stack (list) for DFS or a deque for BFS and dodge that ceiling.

Common bugs to avoid

Forgetting the base case. if not n: return on the first line prevents an AttributeError at leaves.
Mutating a shared list wrong. If you pass out=[] as a default argument, Python reuses the same list across calls. Pass it explicitly.
Confusing height with depth. Height is measured from a node down to its deepest leaf; depth is from the root down. Off-by-one bugs live here.
BFS without a visited marker on a graph. Trees don't need one — graphs do. Reusing tree-BFS code on a graph will loop forever.

Try it

Add a function max_depth(root) that returns the length of the longest root-to-leaf path. A leaf is depth 1; an empty tree is depth 0.
Write an iterative preorder using an explicit list as a stack. Remember to push the right child before the left so left comes out on top.

Practice

3 graded exercises

Write the code, click Check. We’ll tell you exactly what to fix.

Progress0 / 3

Exercise 1
Define a Node class with attributes value, left, and right. Then build a root node with value 10, a left child of 5, and a right child of 15, and print the root's value followed by its left and right children's values on one line separated by spaces.
Exercise 2
Write inorder(node) that returns a list of values from an in-order traversal (left, root, right). Test it on a tree with root 4, left subtree (2 with children 1 and 3), and right child 5 — expected list is [1, 2, 3, 4, 5].
Exercise 3
Write max_depth(node) returning the number of nodes on the longest root-to-leaf path (empty tree = 0, single node = 1). Print the depth of the sample tree.

← PreviousSorting — merge, quick, and when Python's sorted() isn't enough Next →Binary Search Trees — ordered lookup in O(log n)

Binary Trees — traversals and recursion

Binary Trees

The four traversals

Depth-first traversals are defined by when you visit the current node relative to its children:

Preorder (node, left, right) — good for cloning a tree or emitting a prefix expression.
Inorder (left, node, right) — on a BST, this yields sorted order.
Postorder (left, right, node) — perfect for freeing memory or evaluating an expression tree, because children are done before the parent.

The fourth is level-order (BFS): visit depth 0, then depth 1, then depth 2. It needs a queue rather than recursion.

Recursive vs iterative

Common bugs to avoid

Forgetting the base case. if not n: return on the first line prevents an AttributeError at leaves.
Mutating a shared list wrong. If you pass out=[] as a default argument, Python reuses the same list across calls. Pass it explicitly.
Confusing height with depth. Height is measured from a node down to its deepest leaf; depth is from the root down. Off-by-one bugs live here.
BFS without a visited marker on a graph. Trees don't need one — graphs do. Reusing tree-BFS code on a graph will loop forever.

Try it

Add a function max_depth(root) that returns the length of the longest root-to-leaf path. A leaf is depth 1; an empty tree is depth 0.
Write an iterative preorder using an explicit list as a stack. Remember to push the right child before the left so left comes out on top.

Practice

3 graded exercises

Write the code, click Check. We’ll tell you exactly what to fix.

Progress0 / 3

Exercise 1
Define a Node class with attributes value, left, and right. Then build a root node with value 10, a left child of 5, and a right child of 15, and print the root's value followed by its left and right children's values on one line separated by spaces.
Exercise 2
Write inorder(node) that returns a list of values from an in-order traversal (left, root, right). Test it on a tree with root 4, left subtree (2 with children 1 and 3), and right child 5 — expected list is [1, 2, 3, 4, 5].
Exercise 3
Write max_depth(node) returning the number of nodes on the longest root-to-leaf path (empty tree = 0, single node = 1). Print the depth of the sample tree.