DSA course menu
Tree Traversals: Preorder, Inorder, Postorder and Level Order
Learn binary tree traversals in Python: preorder, inorder and postorder (recursive and iterative with a stack), level-order traversal with a queue, and what each order is used for.
On this page
A traversal visits every node of a tree exactly once. The order matters, and each order has its uses. All examples use this tree:
1
/ \
2 3
/ \ \
4 5 6The three depth-first orders#
They differ only in when the node itself is visited relative to its subtrees:
- Preorder: node, then left subtree, then right subtree.
- Inorder: left subtree, then node, then right subtree.
- Postorder: left subtree, then right subtree, then node.
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value, self.left, self.right = value, left, right
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))
def preorder(node, out):
if node:
out.append(node.value)
preorder(node.left, out)
preorder(node.right, out)
return out
def inorder(node, out):
if node:
inorder(node.left, out)
out.append(node.value)
inorder(node.right, out)
return out
def postorder(node, out):
if node:
postorder(node.left, out)
postorder(node.right, out)
out.append(node.value)
return out
print("preorder ", preorder(root, []))
print("inorder ", inorder(root, []))
print("postorder", postorder(root, []))preorder [1, 2, 4, 5, 3, 6]
inorder [4, 2, 5, 1, 3, 6]
postorder [4, 5, 2, 6, 3, 1]What each order is for#
Postorder in practice: the size of a folder is known only after the sizes of everything inside it.
class Folder:
def __init__(self, name, files_kb=0, children=()):
self.name, self.files_kb, self.children = name, files_kb, list(children)
def total_size(folder, depth=0):
total = folder.files_kb
for child in folder.children:
total += total_size(child, depth + 1) # children first
print(" " * depth + f"{folder.name}: {total} KB") # then the parent
return total
home = Folder("home", 10, [
Folder("photos", 500, [Folder("2025", 300), Folder("2026", 450)]),
Folder("docs", 40),
])
total_size(home) 2025: 300 KB
2026: 450 KB
photos: 1250 KB
docs: 40 KB
home: 1300 KBIterative traversals with a stack#
Recursion uses the call stack; an explicit stack does the same job without recursion limits. Iterative inorder: go left as far as possible, pushing nodes; pop one, visit it, then go to its right child.
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value, self.left, self.right = value, left, right
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))
def inorder_iterative(root):
out, stack, node = [], [], root
while stack or node:
while node: # go as far left as possible
stack.append(node)
node = node.left
node = stack.pop()
out.append(node.value)
node = node.right
return out
def preorder_iterative(root):
out, stack = [], [root] if root else []
while stack:
node = stack.pop()
out.append(node.value)
if node.right: # push right first so left is popped first
stack.append(node.right)
if node.left:
stack.append(node.left)
return out
print(inorder_iterative(root))
print(preorder_iterative(root))[4, 2, 5, 1, 3, 6]
[1, 2, 4, 5, 3, 6]Level-order traversal with a queue#
Level order (also called breadth-first) visits the tree level by level, left to right. Use a queue: take a node from the front, then add its children to the back.
from collections import deque
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value, self.left, self.right = value, left, right
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))
def level_order(root):
if root is None:
return []
levels, queue = [], deque([root])
while queue:
level = []
for _ in range(len(queue)): # exactly the nodes of this level
node = queue.popleft()
level.append(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
levels.append(level)
return levels
print(level_order(root))[[1], [2, 3], [4, 5, 6]]Taking len(queue) at the start of each round separates the levels. This is the tree version of breadth-first search.
All four traversals are O(n) time. Depth-first ones use O(h) space for the stack; level order uses O(w), the widest level.
Common mistakes#
Practice#
Practice exercise
Write right_side_view(root): the values you would see looking at the tree from the right, one per level (the last node of each level). For the tree in this lesson, that is [1, 3, 6].
Show hint
Do a level-order traversal and record the last value of each level.
Show solution
from collections import deque
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value, self.left, self.right = value, left, right
def right_side_view(root):
if root is None:
return []
view, queue = [], deque([root])
while queue:
size = len(queue)
for i in range(size):
node = queue.popleft()
if i == size - 1:
view.append(node.value)
for child in (node.left, node.right):
if child:
queue.append(child)
return view
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))
print(right_side_view(root))
lopsided = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
print(right_side_view(lopsided))[1, 3, 6]
[1, 3, 4]In the lopsided tree, node 4 is visible from the right because nothing on its level is further right.
Key takeaway#
Next: trees that keep their values in order, Binary Search Trees.
Finished this lesson?