In-order, pre-order en post-order DFS
Implementeer alle drie DFS-doorlopen recursief en iteratief met een expliciete stack en leg uit wanneer elke volgorde nuttig is.
In-order, pre-order en post-order DFS is een gratis DSA Interview Prep-les op CoddyKit. Dit is les 2 van 4. Je kunt 3 lessen uit dit leerpad gratis volledig lezen — daarna ontgrendelt CoddyKit PRO alle lessen, plus praktische oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject DSA Interview Prep. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus DSA Interview Prep bevat in totaal 4 lessen.
Drie DFS-doorloopvolgorden
DFS op een binaire boom bezoekt knopen in een van drie volgorden, afhankelijk van wanneer de wortel wordt verwerkt ten opzichte van zijn kinderen. Pre-order: wortel → links → rechts. In-order: links → wortel → rechts. Post-order: links → rechts → wortel. De namen geven aan waar de wortel in de volgorde komt. Het is essentieel om alle drie te begrijpen, omdat verschillende problemen verschillende volgorden vereisen.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Build: 1 -> left=2(left=4,right=5), right=3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# pre: 1 2 4 5 3
# in: 4 2 5 1 3
# post: 4 5 2 3 1
print('Tree built successfully')Recursieve pre-orderdoorloop
Bij een pre-orderdoorloop wordt de huidige knoop vóór zijn deelbomen verwerkt. Dit weerspiegelt de natuurlijke top-downlezing van een boom en wordt gebruikt voor het kopiëren en serialiseren van bomen en voor het evalueren van prefixexpressies. De recursieve implementatie is bijzonder kort, maar bouwt een aanroepstack met diepte O(h), waarbij h de hoogte van de boom is.
def preorder(root):
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
# More memory-efficient with an accumulator:
def preorder_v2(root, result=None):
if result is None:
result = []
if not root:
return result
result.append(root.val) # PROCESS ROOT FIRST
preorder_v2(root.left, result)
preorder_v2(root.right, result)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_v2(root)) # [1, 2, 4, 5, 3]Recursieve in-orderdoorloop
Een in-orderdoorloop bezoekt de linker deelboom, daarna de wortel en vervolgens de rechter deelboom. Voor een binaire zoekboom levert een in-orderdoorloop altijd een gesorteerde reeks op. Deze eigenschap wordt gebruikt bij problemen zoals een BST valideren, het k-de kleinste element vinden en een BST omzetten naar een gesorteerde array. Dit is de belangrijkste doorloop voor BST-problemen.
def inorder(root, result=None):
if result is None:
result = []
if not root:
return result
inorder(root.left, result) # left subtree first
result.append(root.val) # PROCESS ROOT MIDDLE
inorder(root.right, result) # right subtree last
return result
# For a BST, inorder gives sorted output:
from collections import deque
def make_bst():
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
return root
bst = make_bst()
print(inorder(bst)) # [1, 2, 3, 4, 6] - sorted!Recursieve post-orderdoorloop
Een post-orderdoorloop verwerkt beide kinderen vóór de huidige knoop. Deze bottom-upvolgorde is natuurlijk wanneer de berekening van de ouder afhankelijk is van de resultaten van zijn kinderen, bijvoorbeeld bij het berekenen van deelboommaten, het verwijderen van een boom of het evalueren van een expressieboom. De meeste boomproblemen waarbij informatie omhoog wordt doorgegeven, gebruiken impliciete post-orderlogica.
def postorder(root, result=None):
if result is None:
result = []
if not root:
return result
postorder(root.left, result) # left subtree
postorder(root.right, result) # right subtree
result.append(root.val) # PROCESS ROOT LAST
return result
# Use case: delete a tree (children before parent)
def delete_tree(root):
if not root:
return
delete_tree(root.left)
delete_tree(root.right)
print(f'Deleting node {root.val}') # safe: children gone
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(postorder(root)) # [4, 2, 3, 1]Iteratieve pre-orderdoorloop met een stack
Om limieten voor recursiediepte te vermijden, implementeer je DFS iteratief met een expliciete stack. Plaats voor pre-order de wortel op de stack. Haal daarna in elke iteratie een knoop van de stack, leg die vast en plaats eerst het rechterkind en daarna het linker kind op de stack, zodat links als eerste wordt verwerkt. Dit bootst het LIFO-gedrag van de aanroepstack na en is de standaardaanpak voor diepe bomen waarbij de standaardrecursielimiet van Python van 1000 zou worden overschreden.
def preorder_iterative(root):
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val) # process now
if node.right: # push right FIRST
stack.append(node.right)
if node.left: # push left second (popped first)
stack.append(node.left)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_iterative(root)) # [1, 2, 4, 5, 3]Iteratieve in-orderdoorloop met een stack
Iteratieve in-order is iets lastiger. Gebruik een stack en een aanwijzer curr: ga zo ver mogelijk naar links en plaats elke knoop op de stack. Wanneer je niet verder naar links kunt, haal je een knoop van de stack, leg je die vast en ga je naar rechts. Dit patroon — naar links blijven gaan en knopen op de stack plaatsen tot null, een knoop eraf halen en verwerken, en daarna naar rechts gaan — is een vaste iteratieve techniek die voorkomt bij problemen met BST-iterators.
def inorder_iterative(root):
result = []
stack = []
curr = root
while curr or stack:
# Go as far left as possible
while curr:
stack.append(curr)
curr = curr.left
# Pop and process
curr = stack.pop()
result.append(curr.val)
# Move to right subtree
curr = curr.right
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(inorder_iterative(root)) # [4, 2, 5, 1, 3]Iteratieve post-orderdoorloop met twee stacks
Iteratieve post-order heeft een handige truc: voer een aangepaste pre-orderdoorloop uit (wortel → rechts → links) en verzamel de resultaten in omgekeerde volgorde. Plaats de wortel op de stack, haal een knoop eraf en voeg die vooraan aan het resultaat toe; plaats daarna links en vervolgens rechts op de stack. Door de omkering verandert wortel-rechts-links in links-rechts-wortel, precies de post-ordervolgorde. Je kunt ook een prev-aanwijzer gebruiken om met één stack de laatst bezochte knoop bij te houden.
from collections import deque
def postorder_iterative(root):
if not root:
return []
result = deque()
stack = [root]
while stack:
node = stack.pop()
result.appendleft(node.val) # prepend = reverse pre-order
if node.left:
stack.append(node.left) # push left first
if node.right:
stack.append(node.right) # push right second
return list(result)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(postorder_iterative(root)) # [4, 5, 2, 3, 1]Wanneer kies je welke doorloop
De juiste doorloop kiezen is een belangrijk signaal tijdens een sollicitatiegesprek. Gebruik pre-order wanneer je een ouder vóór zijn kinderen moet verwerken, bijvoorbeeld om een boom te serialiseren of een structuur te kopiëren. Gebruik in-order voor BST's om de gesorteerde volgorde te benutten. Gebruik post-order wanneer je waarden berekent die afhangen van beide kinderen, zoals hoogte, diameter of de som van een deelboom. BFS heeft de voorkeur bij problemen met kortste paden en groepering per niveau.
# Pattern summary:
# Pre-order -> top-down: parent info flows DOWN to children
# In-order -> BST sorted property, kth element, validate BST
# Post-order -> bottom-up: children info flows UP to parent
# BFS -> shortest path, level grouping, level averages
# Example: compute subtree sum (post-order because
# we need left + right sum before computing total)
def subtree_sum(root):
if not root:
return 0
left = subtree_sum(root.left)
right = subtree_sum(root.right)
return root.val + left + right # uses children FIRST
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(subtree_sum(root)) # 6Morris-doorloop: in-order met O(1) ruimte
De Morris-doorloop bereikt in-order met O(1) ruimte door de boom tijdelijk te wijzigen. Zoek voor elke knoop met een linker deelboom de in-order-voorganger (de meest rechtse knoop van de linker deelboom) en koppel diens rechteraanwijzer terug naar de huidige knoop. Herstel de koppeling nadat je de knoop hebt bezocht. Deze geavanceerde techniek komt aan bod bij zeer selectieve sollicitatiegesprekken wanneer de interviewer vraagt: 'kun je dit met O(1) extra ruimte doen?'
def morris_inorder(root):
result = []
curr = root
while curr:
if not curr.left:
result.append(curr.val)
curr = curr.right
else:
# Find in-order predecessor
pred = curr.left
while pred.right and pred.right != curr:
pred = pred.right
if not pred.right:
# Make thread and move left
pred.right = curr
curr = curr.left
else:
# Remove thread, visit, move right
pred.right = None
result.append(curr.val)
curr = curr.right
return result
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(morris_inorder(root)) # [1, 2, 3, 4, 6]Boom reconstrueren uit doorlopen
Met gegeven pre-order- en in-order-arrays kun je de oorspronkelijke boom reconstrueren. Het eerste element van pre-order is altijd de wortel. Zoek die wortel op in de in-order-array: alles links ervan hoort bij de linker deelboom en alles rechts ervan bij de rechter deelboom. Pas dit recursief toe op de deelarrays. De tijdcomplexiteit is O(n) dankzij het opzoeken van de index in een hash-tabel.
def build_from_preorder_inorder(preorder, inorder):
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
mid = inorder.index(root_val)
# left subtree: inorder[0:mid], preorder[1:mid+1]
root.left = build_from_preorder_inorder(
preorder[1:mid+1], inorder[:mid])
# right subtree: inorder[mid+1:], preorder[mid+1:]
root.right = build_from_preorder_inorder(
preorder[mid+1:], inorder[mid+1:])
return root
pre = [3, 9, 20, 15, 7]
ino = [9, 3, 15, 20, 7]
root = build_from_preorder_inorder(pre, ino)
print(root.val, root.left.val, root.right.val) # 3 9 20Samenvatting van tijd- en ruimtecomplexiteit van doorlopen
Alle drie DFS-doorlopen hebben tijdcomplexiteit O(n), omdat elke knoop precies één keer wordt bezocht. De ruimtecomplexiteit is O(h), waarbij h de hoogte van de boom is: O(log n) voor gebalanceerde bomen en O(n) voor scheve bomen door de aanroepstack of expliciete stack. Iteratieve implementaties vermijden de recursielimiet van Python, maar gebruiken dezelfde asymptotische ruimte. De Morris-doorloop bereikt als enige O(1) ruimte door de rechteraanwijzers van de boom opnieuw te gebruiken.
# Complexity table:
# Traversal | Time | Space (recursion) | Space (iterative)
# -----------|------|-------------------|------------------
# Pre-order | O(n) | O(h) | O(h)
# In-order | O(n) | O(h) | O(h)
# Post-order | O(n) | O(h) | O(h)
# Morris | O(n) | O(1) | O(1)
# BFS | O(n) | O(w) | O(w)
# h = height, w = max width
# Balanced: h = log n, w = n/2
# Skewed: h = n, w = 1
print('O(n) time for all traversals')Snelle controle
Toets je begrip van de concepten Data Structures & Algorithms — Coding Interview Prep uit deze les.
Samenvatting van de les
In deze les heb je geleerd: drie DFS-doorloopvolgorden (pre, in, post) en wanneer je elke volgorde kiest, recursieve en iteratieve implementaties met een expliciete stack, en de Morris-techniek met O(1) ruimte. Hierna verkennen we het berekenen van de diameter, hoogte en balans van binaire bomen.
Leer Python met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “In-order, pre-order en post-order DFS” gratis?
Ja — je kunt hier op het web alle 3 lessen van het leerpad DSA Interview Prep, waaronder “In-order, pre-order en post-order DFS”, gratis volledig lezen. Daarna ontgrendelt CoddyKit PRO alle lessen, plus interactieve oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. De cursus DSA Interview Prep bevat in totaal 4 lessen.
Wat leer ik in “In-order, pre-order en post-order DFS”?
Implementeer alle drie DFS-doorlopen recursief en iteratief met een expliciete stack en leg uit wanneer elke volgorde nuttig is. Je oefent met DSA Interview Prep door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met DSA Interview Prep te beginnen?
Ervaring vooraf is niet nodig. DSA Interview Prep op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 2 van 4.
Hoe lang duurt de les “In-order, pre-order en post-order DFS”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over DSA Interview Prep?
Ja. Elke les over DSA Interview Prep bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- TreeNode-klasse en BFS op niveaus
- In-order, pre-order en post-order DFS
- Diameter, hoogte en gebalanceerde bomen
- Path sum en laagste gemeenschappelijke voorouder