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?
Related lessons
Recommended DSA resources
- Cracking the Coding Interview by Gayle Laakmann McDowell
189 practice questions with solutions, for coding interview preparation.
Some links are affiliate links. If you buy through them, Laviyx Learn may earn a commission at no extra cost to you. As an Amazon Associate, we earn from qualifying purchases.