DFS In-Order, Pre-Order, dan Post-Order
Implementasikan ketiga traversal DFS secara rekursif dan iteratif dengan stack eksplisit, serta jelaskan kapan setiap urutan berguna.
DFS In-Order, Pre-Order, dan Post-Order adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Tiga Urutan Penelusuran DFS
DFS pada pohon biner mengunjungi simpul dalam salah satu dari tiga urutan berdasarkan kapan akar diproses relatif terhadap anak-anaknya. preorder: akar → kiri → kanan. inorder: kiri → akar → kanan. postorder: kiri → kanan → akar. Nama-nama tersebut menunjukkan di mana akar ditempatkan dalam urutan. Memahami ketiganya penting karena masalah yang berbeda memerlukan urutan yang berbeda.
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')Penelusuran preorder Rekursif
Dalam preorder, simpul saat ini diproses sebelum subpohonnya. Hal ini mencerminkan pembacaan alami pohon dari atas ke bawah dan digunakan untuk menyalin pohon, melakukan serialisasi, serta mengevaluasi ekspresi prefiks. Implementasi rekursif ini sangat singkat, tetapi membangun tumpukan pemanggilan dengan kedalaman O(h), dengan h sebagai height pohon.
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]Penelusuran inorder Rekursif
Penelusuran inorder mengunjungi subpohon kiri, lalu akar, kemudian subpohon kanan. Untuk Pohon Pencarian Biner, penelusuran inorder selalu menghasilkan urutan yang terurut—sifat ini digunakan dalam masalah seperti validasi BST, elemen ke-k terkecil, dan mengubah BST menjadi larik terurut. Inilah penelusuran terpenting yang perlu dikuasai untuk masalah BST.
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!Penelusuran postorder Rekursif
Penelusuran postorder memproses kedua anak sebelum simpul saat ini. Urutan dari bawah ke atas ini alami ketika perhitungan induk bergantung pada hasil dari anak-anaknya—misalnya saat menghitung ukuran subpohon, menghapus pohon, atau mengevaluasi pohon ekspresi. Sebagian besar masalah pohon yang meneruskan informasi ke atas menggunakan logika postorder tersirat.
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]Penelusuran preorder Iteratif dengan Tumpukan
Untuk menghindari batas kedalaman rekursi, implementasikan DFS secara iteratif menggunakan tumpukan eksplisit. Untuk preorder: masukkan akar ke tumpukan, lalu pada setiap iterasi lakukan pop pada sebuah simpul, catat simpul tersebut, dan masukkan anak kanannya kemudian anak kirinya (kanan terlebih dahulu agar kiri diproses lebih dulu). Cara ini meniru perilaku LIFO pada tumpukan pemanggilan dan merupakan pendekatan utama untuk pohon dalam, ketika batas rekursi bawaan Python sebesar 1000 akan menyebabkan kegagalan.
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]Penelusuran inorder Iteratif dengan Tumpukan
Penelusuran inorder iteratif sedikit lebih rumit. Gunakan tumpukan dan penunjuk curr: bergerak ke kiri sejauh mungkin sambil memasukkan setiap simpul ke tumpukan. Saat tidak dapat bergerak lebih jauh ke kiri, lakukan pop, catat simpul tersebut, lalu bergerak ke kanan. Pola ini—masukkan ke tumpukan ke kiri hingga kosong, lakukan pop dan proses, lalu bergerak ke kanan—adalah teknik iteratif yang sering digunakan dan muncul dalam masalah iterasi BST.
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]Penelusuran postorder Iteratif dengan Dua Tumpukan
Penelusuran postorder iteratif memiliki trik yang menarik: jalankan preorder yang dimodifikasi (akar → kanan → kiri) dan kumpulkan hasil secara terbalik. Masukkan akar ke tumpukan, lakukan pop dan tambahkan ke awal hasil, lalu masukkan anak kiri kemudian anak kanan. Pembalikan tersebut mengubah akar-kanan-kiri menjadi kiri-kanan-akar—tepat seperti postorder. Sebagai alternatif, gunakan penunjuk prev untuk melacak simpul yang terakhir dikunjungi dengan satu tumpukan.
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]Kapan Memilih Setiap Penelusuran
Memilih penelusuran yang tepat merupakan sinyal penting dalam wawancara. Gunakan preorder ketika Anda perlu memproses induk sebelum anak-anaknya (melakukan serialisasi pohon, menyalin struktur). Gunakan inorder untuk BST agar dapat memanfaatkan urutan terurut. Gunakan postorder ketika menghitung nilai yang bergantung pada kedua anak (height, diameter, jumlah subpohon). BFS lebih disukai untuk masalah jalur terpendek dan pengelompokan tingkat.
# 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)) # 6Penelusuran Morris: Ruang O(1)
Penelusuran Morris mencapai ruang O(1) untuk inorder dengan memodifikasi pohon untuk sementara. Untuk setiap simpul yang memiliki subpohon kiri, temukan pendahulu inorder (simpul paling kanan pada subpohon kiri) dan hubungkan penunjuk kanannya kembali ke simpul saat ini. Setelah mengunjunginya, pulihkan tautan tersebut. Teknik tingkat lanjut ini ditanyakan dalam wawancara tingkat atas ketika pewawancara bertanya, 'Dapatkah Anda melakukannya dengan ruang tambahan O(1)?'
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]Merekonstruksi Pohon dari Hasil Penelusuran
Dengan diberikan larik preorder dan inorder, Anda dapat merekonstruksi pohon asli. Elemen pertama dari preorder selalu merupakan akar. Temukan akar tersebut dalam larik inorder—semua yang berada di sebelah kirinya termasuk subpohon kiri, sedangkan semua yang berada di sebelah kanannya termasuk subpohon kanan. Terapkan langkah ini secara rekursif pada sublarik. Kompleksitas waktunya adalah O(n) dengan pencarian indeks menggunakan peta hash.
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 20Ringkasan Waktu dan Ruang Penelusuran
Ketiga penelusuran DFS memiliki kompleksitas waktu O(n) karena setiap simpul dikunjungi tepat satu kali. Kompleksitas ruang adalah O(h)
# 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')Uji Cepat
Ujilah pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini Anda mempelajari: tiga urutan penelusuran DFS (pre, in, post) dan kapan memilih masing-masing, implementasi rekursif dan iteratif menggunakan tumpukan eksplisit, serta teknik Morris dengan ruang O(1). Selanjutnya, kita akan mempelajari cara menghitung diameter, height, dan keseimbangan pohon biner.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “DFS In-Order, Pre-Order, dan Post-Order” gratis?
Ya — teks lengkap “DFS In-Order, Pre-Order, dan Post-Order” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “DFS In-Order, Pre-Order, dan Post-Order”?
Implementasikan ketiga traversal DFS secara rekursif dan iteratif dengan stack eksplisit, serta jelaskan kapan setiap urutan berguna. Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.
Berapa lama pelajaran “DFS In-Order, Pre-Order, dan Post-Order” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Kelas TreeNode dan BFS Berdasarkan Level
- DFS In-Order, Pre-Order, dan Post-Order
- Diameter, Tinggi, dan Pohon Seimbang
- Jumlah Jalur dan Leluhur Bersama Terendah