Drzewa binarne pojawiają się w niemal każdej serii zadań rekrutacyjnych. Wzorzec dotyka rekurencji, pamięci stanu, traversali i decyzji o strukturze danych — czyli pełnego spektrum tego, czego rozmówca chce zobaczyć w 30 minut.
Ten artykuł pokazuje drzewa binarne jako narzędzie rozwiązywania zadań: od definicji i terminologii, przez BST i traversale, po sygnały rozpoznawcze i sytuacje, w których drzewo jest złym wyborem. Implementacje są w Pythonie dla zwięzłości — wzorzec jest language-agnostic, identycznie działa w Javie, C++ czy JavaScript.
Pozostaję w obrębie zwykłego drzewa binarnego i BST. Drzewa balansowane (AVL, red-black), B-trees i indeksy bazodanowe to inne tematy, celowo poza zakresem.
Czym jest drzewo binarne
Drzewo binarne to struktura danych, w której każdy węzeł ma wartość oraz co najwyżej dwoje dzieci: lewe i prawe. Jeden węzeł jest korzeniem, czyli root. Węzeł bez dzieci to liść. Głębokość węzła oznacza odległość od korzenia, a wysokość drzewa to najdłuższa ścieżka od korzenia do liścia. To jest zwykłe binary tree, niekoniecznie struktura do szybkiego wyszukiwania.
Intuicja jest prosta: zamiast trzymać dane liniowo, dzielisz je na relacje rodzic-dziecko. Drzewo nie mówi jeszcze, że po lewej są mniejsze wartości, a po prawej większe. Mówi tylko: z jednego węzła możesz zejść najwyżej w dwie strony.
A depth(A)=0
/ \
B C depth(B)=1
/ \ \
D E F D, E, F are leaves
height = 2
Na rozmowie technicznej zobaczysz drzewo binarne, gdy wejście ma postać root, TreeNode, left, right albo gdy opis problemu mówi o hierarchii: katalogi, wyrażenia matematyczne, AST, zależności, struktura komentarzy. Najważniejszy sygnał: masz obiekt, który prowadzi do podobnych obiektów, aż do None.
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
root = Node("A",
Node("B", Node("D"), Node("E")),
Node("C", right=Node("F")),
)
print(root.left.right.value) # expected_output: E
BST (Binary Search Tree)
BST, czyli Binary Search Tree, to szczególny przypadek drzewa binarnego. Niezmiennik brzmi: dla każdego węzła wszystkie wartości w lewym poddrzewie są mniejsze od wartości węzła, a wszystkie wartości w prawym poddrzewie są większe. To nie jest reguła tylko o bezpośrednim dziecku, ale o całym poddrzewie. Każde BST jest drzewem binarnym, ale nie każde drzewo binarne jest BST. Zobacz też definicję Binary search tree.
Intuicja: w zwykłym drzewie, żeby znaleźć 9, często musisz sprawdzić wiele gałęzi. W BST każde porównanie mówi, którą połowę drzewa możesz odrzucić. Jeśli szukasz 9, a jesteś w 8, idziesz w prawo. Jeśli jesteś w 12, idziesz w lewo. Niezmiennik działa tylko wtedy, gdy jest prawdziwy globalnie.
BST: not BST:
8 8
/ \ / \
4 12 4 12
/ \ / \ / \ / \
2 6 10 14 2 9 10 14
ok 9 is in left subtree of 8
Na rozmowie sygnałem BST są słowa: sorted, less than, greater than, validate BST, search, insert, k-th smallest. Pamiętaj jednak, że BST bez balansowania może zdegenerować do listy. Struktury balansowane, na przykład AVL, utrzymują operacje w O(log n), ale tu interesuje nas zwykły BST: średnio O(log n), w najgorszym przypadku O(n).
def contains(root, target):
node = root
while node:
if target == node.value:
return True
if target < node.value:
node = node.left
else:
node = node.right
return False
bst = Node(8, Node(4, Node(2), Node(6)), Node(12, Node(10), Node(14)))
print(contains(bst, 6)) # expected_output: True
print(contains(bst, 7)) # expected_output: False
Intuicja porównawcza: ten sam wzorzec „halve the search space at each step” występuje w wyszukiwaniu binarnym na sorted array. Różnica: BST trzyma drzewo wskaźników, sorted array wymaga indeksu i ciągłej pamięci.
Pre-order, In-order, Post-order traversal
Traversal to przejście po drzewie, czyli odwiedzenie każdego węzła dokładnie raz. Trzy klasyczne warianty DFS różnią się tylko momentem odwiedzenia korzenia: pre-order to root -> left -> right, in-order to left -> root -> right, a post-order to left -> right -> root. Zobacz też Tree traversal.
Intuicja: w każdym węźle masz trzy rzeczy do zrobienia: odwiedzić bieżący węzeł, przejść lewe poddrzewo, przejść prawe poddrzewo. Zmiana kolejności tych trzech kroków daje różne właściwości. In-order na BST zwraca wartości posortowane. Post-order jest wygodny, gdy wynik rodzica zależy od wyników dzieci.
1
/ \
2 3
pre-order: visit 1, then left, then right
in-order: left, then visit 1, then right
post-order: left, then right, then visit 1
Na rozmowie wybór traversalu jest często sednem zadania. serialize tree często pachnie pre-orderem. k-th smallest in BST zwykle prowadzi do in-order. delete/free/evaluate from leaves albo obliczanie wysokości naturalnie używa post-order, bo najpierw musisz znać odpowiedzi z poddrzew.
Drzewo z wartościami 1..7 i wyniki trzech traversali side-by-side:
1
/ \
2 3
/ \ / \
4 5 6 7
pre-order: [1, 2, 4, 5, 3, 6, 7] ← root, potem lewe, potem prawe
in-order: [4, 2, 5, 1, 6, 3, 7] ← lewe, potem root, potem prawe
post-order: [4, 5, 2, 6, 7, 3, 1] ← lewe, potem prawe, potem root
Zauważ: każdy traversal odwiedza wszystkie 7 węzłów, ale w innej kolejności. In-order na BST zwraca wartości rosnąco (tu drzewo nie jest BST, więc nie sortuje). Post-order jest jedyny, który kończy na korzeniu.
def traversals(root):
pre, ino, post = [], [], []
def walk(node):
if not node:
return
pre.append(node.value)
walk(node.left)
ino.append(node.value)
walk(node.right)
post.append(node.value)
walk(root)
return pre, ino, post
root = Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6), Node(7)))
print(traversals(root))
# expected_output: ([1, 2, 4, 5, 3, 6, 7], [4, 2, 5, 1, 6, 3, 7], [4, 5, 2, 6, 7, 3, 1])
Rekurencja jako naturalny model
Rekurencja pasuje do drzewa, bo każde poddrzewo wygląda jak mniejsza wersja całego problemu. Jeśli umiesz policzyć wynik dla lewego i prawego poddrzewa, możesz policzyć wynik dla bieżącego węzła. Przypadek bazowy to zwykle None: puste drzewo ma wysokość 0, nie zawiera wartości albo daje pustą listę.
Intuicja: call stack zachowuje się jak niewidoczny stos zadań. Gdy funkcja wchodzi w lewe poddrzewo, Python zapamiętuje, że trzeba jeszcze wrócić do rodzica i przejść prawą stronę. Nie musisz samodzielnie trzymać stosu, bo robi to mechanizm wywołań funkcji.
max_depth(1)
max_depth(2)
max_depth(4)
max_depth(None) -> 0
max_depth(None) -> 0
returns 1
...
returns 3
W zadaniach rekrutacyjnych rekurencja jest często najkrótszą drogą do poprawnego rozwiązania: max depth, same tree, invert tree, path sum, validate recursively with bounds. Limit rekurencji w CPythonie domyślnie wynosi 1000 — przy bardzo głębokim drzewie warto rozważyć wersję iteracyjną z explicit stackiem (rozwijam to w artykule Rekurencja vs Iteracja).
def max_depth(root):
if not root:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return 1 + max(left_depth, right_depth)
print(max_depth(root)) # expected_output: 3
Trace dla max_depth:
Krok 1: call_stack=[max_depth(1)], funkcja schodzi do 2.
Krok 2: call_stack=[1, 2], funkcja schodzi do 4.
Krok 3: call_stack=[1, 2, 4], dzieci 4 to None, więc zwracają 0.
Krok 4: 4 zwraca 1, call_stack=[1, 2].
Krok 5: po policzeniu 5, węzeł 2 zwraca 2, a root finalnie zwraca 3.
DFS iteracyjnie z explicit stack
DFS iteracyjny robi to samo co rekurencja, ale zamiast call stack używa jawnego stosu. Stos działa w trybie LIFO: ostatni dodany element wychodzi pierwszy. Dzięki temu możesz zejść głęboko jedną gałęzią, potem wrócić do zapamiętanych alternatyw.
Intuicja: rekurencja ukrywa stos w runtime, a wersja iteracyjna pokazuje go w kodzie. Jeśli chcesz odwiedzić lewe dziecko przed prawym, na stos wrzucasz najpierw prawe, potem lewe. Lewe będzie zdjęte jako pierwsze.
start: stack=[1]
pop 1, push 3, push 2
pop 2, push 5, push 4
pop 4
pop 5
pop 3, push 7, push 6
Iteracyjny DFS wybierasz, gdy drzewo może być bardzo głębokie, gdy chcesz kontrolować pamięć, albo gdy rozmówca prosi o rozwiązanie bez rekurencji. To także dobry wzorzec dla grafów, gdzie dochodzi jeszcze visited, ale w czystym drzewie bez cykli zwykle nie jest potrzebny.
def preorder_iterative(root):
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.value)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
print(preorder_iterative(root)) # expected_output: [1, 2, 4, 5, 3, 6, 7]
Trace dla pre-order:
Krok 1: stack=[1], visit 1 -> stack=[3, 2].
Krok 2: stack=[3, 2], visit 2 -> stack=[3, 5, 4].
Krok 3: stack=[3, 5, 4], visit 4 -> stack=[3, 5].
Krok 4: stack=[3, 5], visit 5 -> stack=[3].
Krok 5: stack=[3], visit 3 -> stack=[7, 6].
BFS na drzewie z queue
BFS, czyli breadth-first search, przechodzi drzewo poziomami. Najpierw odwiedza root, potem wszystkie węzły na głębokości 1, potem wszystkie na głębokości 2. Na drzewie ten porządek nazywa się też level-order traversal. BFS używa kolejki FIFO, a w Pythonie praktycznym wyborem jest collections.deque (kolejka dwustronna z O(1) na obu końcach — szczegóły: Stos i Kolejka).
Intuicja: kolejka zachowuje kolejność zgłoszeń. Gdy odwiedzasz węzeł, jego dzieci trafiają na koniec kolejki. Najpierw zostaną obsłużone starsze węzły z tego samego poziomu, więc algorytm naturalnie idzie warstwami.
1
/ \
2 3
/ \ / \
4 5 6 7
BFS: 1, 2, 3, 4, 5, 6, 7
BFS jest lepszy od DFS, gdy pytanie dotyczy poziomów: right side view, minimum depth, average per level, zigzag level order, serializacja warstwowa. W realnym kodzie BFS pomaga, gdy najbliższe rozwiązanie jest ważniejsze niż zejście do końca jednej gałęzi.
from collections import deque
def level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
node = queue.popleft()
result.append(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
print(level_order(root)) # expected_output: [1, 2, 3, 4, 5, 6, 7]
Trace dla BFS:
Krok 1: queue=[1], visit 1 -> queue=[2, 3].
Krok 2: queue=[2, 3], visit 2 -> queue=[3, 4, 5].
Krok 3: queue=[3, 4, 5], visit 3 -> queue=[4, 5, 6, 7].
Krok 4: queue=[4, 5, 6, 7], visit 4 -> queue=[5, 6, 7].
Krok 5: wynik narasta poziomami: [1, 2, 3, 4, 5, 6, 7].
Wstawianie i wyszukiwanie w BST
Wyszukiwanie w BST zaczyna się od korzenia i po każdym porównaniu wybiera tylko jedną gałąź. Wstawianie działa podobnie: idziesz w lewo, gdy nowa wartość jest mniejsza, w prawo, gdy większa, aż trafisz na puste miejsce. Zakładamy tu brak duplikatów albo jasną politykę duplikatów, bo bez niej niezmiennik staje się niejednoznaczny.
Intuicja: koszt operacji zależy od wysokości drzewa. Jeśli drzewo jest rozsądnie rozłożone, wysokość jest bliska log n, więc lookup i insert są średnio O(log n). Jeśli wstawiasz wartości już posortowane, drzewo może zmienić się w listę, a wtedy operacje spadają do O(n).
insert: 1, 2, 3, 4
1
\
2
\
3
\
4
height = 4, lookup behaves like linear scan
Na rozmowie zwykły BST pojawia się w zadaniach o dynamicznym zbiorze wartości, sprawdzaniu obecności, budowie drzewa z wejścia i przejściu in-order. Gdy rozmówca pyta o złożoność, zawsze podaj oba przypadki: average O(log n), worst O(n) dla drzewa zdegenerowanego.
def insert(root, value):
if not root:
return Node(value)
node = root
while True:
if value < node.value:
if not node.left:
node.left = Node(value)
return root
node = node.left
else:
if not node.right:
node.right = Node(value)
return root
node = node.right
bst = Node(8, Node(4), Node(12))
insert(bst, 10)
print(bst.right.left.value) # expected_output: 10
print(bst.right.value) # expected_output: 12
Trace dla insert(root=8, value=10):
Krok 1: node=8, 10 > 8, idź w prawo.
Krok 2: node=12, 10 < 12, idź w lewo.
Krok 3: node.left is None, wstaw 10 jako lewe dziecko 12.
Krok 4: ścieżka porównań to [8, 12], nie całe drzewo.
Krok 5: niezmiennik pozostaje prawdziwy: 8 < 10 < 12.
Sygnały rozpoznawcze zadań na drzewa
Zadanie pachnie drzewem, gdy wejście jest rekurencyjne: root, left, right, children, parent, katalog, parser, hierarchia. Dla drzewa binarnego szczególnie ważne są problemy, w których trzeba połączyć odpowiedzi z lewego i prawego poddrzewa albo przejść wszystkie węzły w określonym porządku.
Intuicja: większość zadań drzewowych da się sprowadzić do pytania „co wiem po lewej, co wiem po prawej i co z tym robi root?”. Jeżeli potrzebujesz informacji z dzieci przed decyzją w rodzicu, myśl post-order. Jeżeli chcesz zachować strukturę lub serializować root przed dziećmi, myśl pre-order. Jeżeli to BST i potrzebujesz kolejności rosnącej, myśl in-order.
validate BST -> recursion with min/max bounds
lowest common ancestor -> search paths or post-order return
max depth -> 1 + max(left, right)
serialize tree -> traversal with null markers
k-th smallest in BST -> in-order traversal
level averages -> BFS queue
Na rozmowie rozpoznanie wzorca jest często ważniejsze niż sama implementacja. lowest common ancestor wymaga zauważenia, że węzeł może dostać sygnał z dwóch stron. serialize tree wymaga zapisu None, bo inaczej różne drzewa mogą dać ten sam traversal. validate BST wymaga zakresów, nie lokalnego porównania z dziećmi.
Kiedy NIE drzewo binarne
Drzewo binarne nie jest domyślną odpowiedzią na każde zadanie o porządku danych. Jeśli nie masz naturalnej hierarchii, lewego i prawego podproblemu albo potrzeby dynamicznego przechodzenia po strukturze, prostsza struktura może być lepsza. Szczególnie zwykły BST bez balansowania bywa ryzykowny, bo nie gwarantuje wysokości log n.
Intuicja: wybór struktury danych to kompromis między operacjami. Jeśli chcesz stale znać najmniejszy albo największy element, heap zwykle pasuje lepiej. Jeśli masz statyczną posortowaną tablicę i potrzebujesz lookupów lub zakresów, bisect daje prostszy kod i przewidywalne wyszukiwanie binarne bez budowania węzłów.
find K-th smallest in stream:
better signal -> heap / two heaps, not plain BST
sorted lookup with range:
better signal -> sorted array + bisect
hierarchical left/right decisions:
tree may fit
Na rozmowie anty-sygnały są równie ważne jak sygnały. find K-th smallest in stream nie prosi automatycznie o BST, bo bez balansowania trudno utrzymać dobre gwarancje. sorted lookup with range na gotowej liście nie wymaga drzewa: bisect_left i bisect_right często wystarczą. Drzewo jest jednym narzędziem, nie odpowiedzią uniwersalną.
from bisect import bisect_left, bisect_right
def values_in_range(sorted_values, low, high):
start = bisect_left(sorted_values, low)
end = bisect_right(sorted_values, high)
return sorted_values[start:end]
print(values_in_range([2, 4, 6, 8, 10], 5, 9)) # expected_output: [6, 8]
Najczęstsze błędy
Mylenie głębokości z wysokością. Głębokość węzła to liczba krawędzi od korzenia do tego węzła (root ma głębokość 0). Wysokość węzła to liczba krawędzi od tego węzła do najgłębszego liścia w jego poddrzewie (liść ma wysokość 0). Wartości się rozjadą wszędzie poza prostą linią — przykład:
A depth=0, height=3
/ \
B C B: depth=1, height=2 C: depth=1, height=0 ← liść
/
D D: depth=2, height=1
|
E E: depth=3, height=0 ← liść
C ma głębokość 1, ale wysokość 0, bo jest liściem. B ma głębokość 1, ale wysokość 2, bo pod nim jest jeszcze ścieżka B→D→E. Pułapka pojawia się w kodzie, bo zadanie max depth of tree w LeetCode-style faktycznie liczy wysokość roota (= 3 dla drzewa wyżej), nie głębokość pojedynczego węzła. Stąd typowa funkcja max_depth(root) wewnętrznie liczy height. Naprawa: konsekwentne nazwy z różnymi sygnaturami — depth_of(root, target_node) (wymaga roota, idzie szukając target) vs height(node) (bierze tylko węzeł, idzie w dół).
Walidacja BST przez lokalne porównanie z dziećmi. Sprawdzanie node.left.value < node.value < node.right.value przepuszcza drzewa łamiące globalny niezmiennik. Wejście: root 8, lewe dziecko 4, jego prawe dziecko 9 — lokalnie 4 < 8 wygląda dobrze, ale 9 siedzi w lewym poddrzewie 8. Naprawa: rekurencja z parametrami min_bound, max_bound.
Założenie że in-order zawsze sortuje. In-order na zwykłym drzewie nie gwarantuje porządku rosnącego — sortuje TYLKO na BST. Drzewo z root 1, left 2, right 3 zwraca [2, 1, 3]. Naprawa: zanim oprzesz logikę na in-order, upewnij się że masz BST.
Brak przypadku bazowego dla None. Funkcja rekurencyjna na drzewie powinna zwracać sensowny wynik przy root is None (najczęściej 0, [] lub True). Bez tego dostajesz AttributeError: 'NoneType' object has no attribute 'left'.
Mówienie że BST zawsze daje O(log n). Bez balansowania wstawianie posortowanych danych 1, 2, 3, 4, 5 tworzy prawą ścieżkę — wyszukanie 5 wymaga przejścia przez wszystkie węzły. Średnio O(log n), w najgorszym przypadku O(n).
FAQ
Co z duplikatami w BST?
Niezmiennik klasycznego BST nie pokrywa duplikatów jednoznacznie. W praktyce wybierasz politykę: zabraniaj duplikatów, dopuszczaj na lewo (<=), lub trzymaj licznik w węźle. Na rozmowie warto eksplicytnie zapytać rozmówcę, którą wersję ma na myśli — to pokazuje świadomość ambiguity.
Jak najlepiej zwalidować BST rekurencyjnie?
Przekazujesz przedziały min_bound, max_bound. Dla root przedział to (-inf, +inf). Schodząc w lewo, zwężasz max_bound do wartości węzła. Schodząc w prawo, zwężasz min_bound. Walidacja każdego węzła to sprawdzenie min_bound < value < max_bound. Lokalna walidacja left < node < right przepuszcza błędy.
Czy drzewo binarne to to samo co heap?
Nie. Heap jest drzewem binarnym (zwykle reprezentowanym jako tablica), ale z innym niezmiennikiem: rodzic jest mniejszy od dzieci (min-heap) lub większy (max-heap). Heap nie ma niezmiennika lewy < prawy. Heap szybko daje minimum/maksimum, BST szybko daje wyszukiwanie po wartości.
Kiedy BST przegrywa z hash mapą?
Gdy nie potrzebujesz porządku ani zapytań zakresowych — sam lookup po dokładnym kluczu jest tańszy w hash mapie (średnio O(1) vs O(log n)). BST wybierasz, gdy chcesz k-th smallest, in-order traversal, next greater, range query. Porównanie sygnałów rozpoznawczych: Haszowanie w Zadaniach.
Czy mogę zaimplementować iteracyjny in-order?
Tak. Wzorzec: stos + wskaźnik current. Schodzisz w lewo aż do None, wtedy ściągasz węzeł ze stosu, odwiedzasz go i przechodzisz do prawego poddrzewa. Iteracyjna wersja jest dłuższa od rekurencyjnej, ale daje pełną kontrolę nad pamięcią i nie ryzykuje przekroczenia limitu rekurencji.
Czemu zwykły BST bywa złym pomysłem na produkcji?
Bo nie ma gwarancji wysokości. Wstawianie danych blisko posortowanych (timestampy, monotoniczne ID, autoincrement keys) tworzy prawie liniowe drzewo. Operacje, które na papierze są O(log n), w produkcji zachowują się jak skan listy. Standardowa odpowiedź na rozmowie: użyj balansowanego drzewa (AVL, red-black) albo skip-listy — same biblioteki językowe (np. Java TreeMap) dają to gotowe.
Powiązane tematy
- Rekurencja vs Iteracja — Kiedy Która Wygrywa — drzewa są klasycznym use case rekurencji; ten artykuł rozszerza intuicję call stack i tłumaczy kiedy wybrać explicit stack.
- Wyszukiwanie Binarne — Dziel-i-Zwyciężaj na Rozmowie — ten sam wzorzec „odrzuć połowę przestrzeni” na sorted array zamiast drzewa wskaźników.
- Haszowanie w Zadaniach — Wzorzec na Rozmowie — alternatywa, gdy nie potrzebujesz porządku; szybszy lookup, ale brak range query i traversali.
Sprawdź swoją wiedzę quizem
Przerób ten artykuł w 15-pytaniowy quiz testujący terminologię, BST, traversale, rekurencję na drzewach i sygnały rozpoznawcze: https://odpytywarka.pl/q/AGfPqT.
Masz własne notatki na rozmowę? Wgraj PDF lub wklej tekst na stworz-quiz-z-pdf — pierwsze 3 strony PDF i 15 pytań jednokrotnego wyboru za darmo, generowanie 30-60 sekund.
Źródła
- Wikipedia — Binary tree — definicja, terminologia, reprezentacje.
- Wikipedia — Binary search tree — niezmiennik BST, operacje, złożoności.
- Wikipedia — Tree traversal — pre-order, in-order, post-order, BFS/DFS.
- Python docs —
collections.deque— kolejka FIFO dla BFS.