Cấu trúc dữ liệu câyTree Data Structures
Mục lục
- Tổng quan
- Kiến thức nền tảng
- Thuật ngữ
- Biểu diễn tree trong code
- Binary tree
- Các hình dạng của binary tree
- Khái niệm chính
- Tree traversal
- Traversal dạng lặp
- Level-order traversal (BFS)
- DFS so với BFS trên tree
- Các phép tính thường gặp trên tree
- Binary search tree
- Vì sao BST không cân bằng suy biến về O(n)
- BST so với hash table
- Best Practices
- Tài liệu tham khảo
Table of contents
- Overview
- Fundamentals
- Terminology
- Representing a tree in code
- Binary trees
- Shapes of binary trees
- Key Concepts
- Tree traversal
- Iterative traversals
- Level-order traversal (BFS)
- DFS versus BFS on a tree
- Common tree computations
- Binary search trees
- Why an unbalanced BST degenerates to O(n)
- BST versus hash table
- Best Practices
- References
Thuộc bộ kiến thức Data Structures & Algorithms Roadmap.
Tổng quan
Mọi cấu trúc đã đi qua từ đầu tới giờ — array, linked list, stack, queue, hash table — đều là tuyến tính: các phần tử nằm thành một dãy, và “phần tử kế tiếp” chỉ có đúng một nghĩa. Tree là cấu trúc phi tuyến tính đầu tiên. Mỗi node có thể trỏ tới nhiều child, nên “kế tiếp” bị phân nhánh, và kết quả là một cấu trúc phân cấp: một hình dạng mô hình hoá rất tự nhiên quan hệ chứa đựng, phân loại và phân rã.
Cấu trúc phân cấp có mặt ở khắp nơi trong ngành, nên tree cũng vậy:
- Filesystem là một tree: directory chứa file và directory khác.
- HTML DOM là một tree:
<html>chứa<body>chứa<div>chứa text. - Database index là một tree — chính xác hơn là B+ tree (xem ./11-balanced-and-multiway-trees.md và ../../postgresql-dba/vi/08-indexing-strategies.md).
- Parse tree của compiler là một tree:
a + b * cphân rã thành một biểu thức mà toán hạng bên phải bản thân nó lại là một biểu thức. - Decision tree, sơ đồ tổ chức, JSON document, mô hình commit/object của Git, routing trie — tất cả đều là tree.
Nhưng lý do tree xứng đáng có một chương riêng không chỉ nằm ở khả năng mô hình hoá. Nó nằm ở O(log n). Cấu trúc tuyến tính bắt bạn phải đi qua k phần tử để tới phần tử thứ k. Tree với branching factor bằng 2 cho phép bạn cắt đôi số ứng viên còn lại ở mỗi bước, nên n phần tử được tiếp cận trong khoảng log₂ n bước. Một triệu phần tử là 20 bước; một tỷ là 30 bước. Đó cũng chính là mẹo mà binary search dùng trên mảng đã sắp xếp (xem ./09-search-algorithms.md), khác ở chỗ tree giữ được tính chất đó trong khi vẫn hỗ trợ insert và delete rẻ, điều mà mảng đã sắp xếp không làm được.
Điểm gài — và cũng là toàn bộ nội dung của note kế tiếp — là O(log n) chỉ đúng khi cây còn xoè rộng. Một binary search tree bị nạp dữ liệu đã sắp xếp sẽ co lại thành một linked list và mọi thao tác suy biến về O(n). Note này xây dựng thuật ngữ, các phép traversal, và binary search tree thuần; note kế tiếp sẽ sửa vấn đề suy biến.
Kiến thức nền tảng
Thuật ngữ
Tree là một tập các node nối với nhau bằng edge, có đúng một node được chọn làm root, và mọi node không phải root đều có đúng một parent. Nói cách khác: tree là một connected acyclic graph có gốc. Tập hợp nhiều tree rời nhau gọi là forest.
(A) <- root, depth 0
/ \
(B) (C) <- B và C là sibling; đều là child của A
/ \ \
(D) (E) (F) <- depth 2
/
(G) <- leaf, depth 3| Thuật ngữ | Ý nghĩa | Trong sơ đồ |
|---|---|---|
| Root | Node duy nhất không có parent | A |
| Parent | Node ở mức trên liền kề | parent của E là B |
| Child | Node ở mức dưới liền kề | child của B là D, E |
| Sibling | Các node chung parent | B và C; D và E |
| Leaf (external node) | Node không có child | D, G, F |
| Internal node | Node có ít nhất một child | A, B, C, E |
| Edge | Liên kết parent→child | A–B |
| Path | Dãy edge nối hai node | A → B → E → G |
| Ancestor | Bất kỳ node nào trên đường đi lên tới root | ancestor của G: E, B, A |
| Descendant | Bất kỳ node nào đi xuống tới được | descendant của B: D, E, G |
| Subtree | Một node cùng toàn bộ descendant của nó | subtree gốc B = {B, D, E, G} |
| Degree của node | Số child | degree của A = 2, của C = 1 |
| Depth của node | Số edge từ root đi xuống tới nó | depth của G = 3 |
| Height của node | Số edge trên đường dài nhất đi xuống tới một leaf | height của B = 2 |
| Height của tree | Height của root | 3 |
| Level | Tất cả node có cùng depth | level 2 = {D, E, F} |
Có hai quy ước gây nhầm lẫn triền miên, nên cần chốt rõ:
- Ở đây height được đo bằng số edge (cây một node có height 0). Một số giáo trình đếm theo node, khiến height thành 1. Cả hai quy ước đều tồn tại ngoài thực tế; điều quan trọng là nhất quán trong cùng một đoạn code. Code Python bên dưới dùng quy ước edge cho
height(), còn fieldheightlưu trong AVL ở note kế tiếp lại dùng quy ước node, vì đó là cách công thức AVL chuẩn giả định — một minh hoạ tốt cho việc luôn phải kiểm tra quy ước. - Depth đếm từ root đi xuống; height đếm từ leaf đi lên. Chúng không phải là cùng một phép đo nhìn từ hai đầu của cùng một đường đi, trừ trường hợp root và các leaf nằm trên đường dài nhất.
Hai sự kiện về cấu trúc đáng nhớ: tree có n node thì có đúng n − 1 edge (mọi node trừ root đều đóng góp đúng một edge lên parent của nó), và giữa hai node bất kỳ chỉ có đúng một simple path.
Biểu diễn tree trong code
Trường hợp tổng quát (n-ary) là một node giữ một giá trị và một danh sách các child:
class TreeNode:
"""Node của tree n-ary tổng quát: một value, số child tuỳ ý."""
__slots__ = ("value", "children")
def __init__(self, value, children=None):
self.value = value
self.children = children if children is not None else []
def add(self, child):
self.children.append(child)
return child
# Mô hình hoá một filesystem nhỏ
root = TreeNode("/")
usr = root.add(TreeNode("usr"))
etc = root.add(TreeNode("etc"))
usr.add(TreeNode("bin"))
usr.add(TreeNode("lib"))
etc.add(TreeNode("hosts"))Chú ý là ở đây không có parent pointer. Thêm nó vào (self.parent) làm cho việc đi ngược lên trở thành O(1) và là bắt buộc cho các thao tác kiểu “tìm đường quay về root” hoặc “tìm node in-order kế tiếp mà không cần stack”, nhưng nó tốn thêm một word mỗi node và tạo ra reference cycle mà một reference-counting collector ngây thơ sẽ để rò rỉ. Hãy thêm khi thật sự cần, đừng mặc định thêm.
Binary tree
Binary tree giới hạn mỗi node có tối đa hai child, đặt tên là left và right. Thứ tự có ý nghĩa: node chỉ có left child là một cây khác với node chỉ có right child, dù cả hai đều có một child.
class Node:
"""Node của binary tree."""
__slots__ = ("val", "left", "right")
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = rightTại sao lại giới hạn ở hai? Vì hai là branching factor nhỏ nhất mà vẫn chia đôi được bài toán, và vì một quyết định hai nhánh (nhỏ hơn / lớn hơn) chính là đầu ra tự nhiên của một phép so sánh. Fan-out lớn hơn cũng hữu ích, nhưng vì một lý do khác — giảm thiểu số lần đọc đĩa thay vì số phép so sánh — và đó chính xác là điều B-tree làm.
Các hình dạng của binary tree
Những cái tên dưới đây thường bị dùng lỏng lẻo ngoài thực tế; đây là các định nghĩa chuẩn.
full (mọi node có 0 hoặc 2 child) complete (mọi level đầy trừ có thể
(1) level cuối, điền từ trái sang phải)
/ \ (1)
(2) (3) / \
/ \ (2) (3)
(4) (5) / \ /
(4) (5) (6)
perfect (full VÀ mọi leaf cùng depth) degenerate (mỗi node có đúng một child —
(1) thực chất là một linked list)
/ \ (1)
(2) (3) \
/ \ / \ (2)
(4) (5) (6) (7) \
(3)
\
(4)| Hình dạng | Định nghĩa | Height với n node |
|---|---|---|
| Full (strict/proper) | Mọi node có 0 hoặc 2 child — không bao giờ đúng 1 | Không chặn (vẫn có thể rất cao) |
| Complete | Mọi level đầy trừ có thể level cuối, điền từ trái sang phải | Đúng bằng ⌊log₂ n⌋ |
| Perfect | Full và mọi leaf ở cùng depth | Đúng bằng log₂(n + 1) − 1 |
| Balanced | Height là O(log n); thường hiểu là “height hai subtree lệch nhau ≤ 1 tại mọi node” | O(log n) |
| Degenerate (pathological) | Mọi internal node có đúng một child | n − 1 |
Vài phép tính hữu ích rút thẳng ra từ các định nghĩa này:
- Perfect binary tree có height
hthì có2^(h+1) − 1node, trong đó2^hlà leaf — khoảng một nửa số node của perfect tree là leaf. Đây là lý do “làm việc ở leaf” chiếm phần lớn chi phí của đa số thuật toán trên tree, và cũng là lý do heapify làO(n)chứ không phảiO(n log n)(xem ./12-heaps-and-priority-queues.md). - Binary tree bất kỳ với
nnode có height ít nhất⌈log₂(n + 1)⌉ − 1và nhiều nhấtn − 1. Khoảng cách giữalog nvànchính là toàn bộ câu chuyện hiệu năng của tree. - Trong full binary tree, số leaf luôn nhiều hơn số internal node đúng 1.
Complete binary tree có một siêu năng lực riêng: vì không có lỗ hổng nào, nó có thể được lưu trong một mảng phẳng hoàn toàn không cần pointer, chỉ dùng phép tính chỉ số — child của node i nằm ở 2i+1 và 2i+2. Đó chính xác là cách binary heap được cài đặt, được triển khai trong ./12-heaps-and-priority-queues.md. Với tree tổng quát (không complete), cách lưu mảng này lãng phí O(2^h) ô cho một hình dạng degenerate, nên nó không phải cách biểu diễn dùng chung được.
Khái niệm chính
Tree traversal
Traversal là phép duyệt qua mọi node đúng một lần theo một thứ tự xác định. Có bốn thứ tự chuẩn, và ba cái đầu chỉ là cùng một phép đệ quy với câu lệnh “visit” được dời sang vị trí khác:
| Traversal | Thứ tự | Ghi nhớ | Trên BST cho ra |
|---|---|---|---|
| Pre-order | Node, Left, Right | N-L-R | Root trước — tốt để copy/serialize |
| In-order | Left, Node, Right | L-N-R | Tăng dần đã sắp xếp |
| Post-order | Left, Right, Node | L-R-N | Child trước parent — tốt để xoá/tính giá trị |
| Level-order (BFS) | Theo từng level, trái sang phải | — | Hình dạng theo depth |
def preorder(node, out):
"""N-L-R: xử lý node trước khi đi xuống."""
if node is None:
return
out.append(node.val) # visit
preorder(node.left, out)
preorder(node.right, out)
def inorder(node, out):
"""L-N-R: trên BST sẽ phát ra các key theo thứ tự tăng dần."""
if node is None:
return
inorder(node.left, out)
out.append(node.val) # visit
inorder(node.right, out)
def postorder(node, out):
"""L-R-N: cả hai child được xử lý xong trước khi tới lượt node."""
if node is None:
return
postorder(node.left, out)
postorder(node.right, out)
out.append(node.val) # visitVới cây dưới đây:
(F)
/ \
(B) (G)
/ \ \
(A) (D) (I)
/ \ /
(C) (E)(H)| Traversal | Kết quả |
|---|---|
| Pre-order | F B A D C E G I H |
| In-order | A B C D E F G H I |
| Post-order | A C E D B H I G F |
| Level-order | F B G A D I C E H |
Để ý kết quả in-order đúng thứ tự bảng chữ cái — cây đó là một BST.
Khi nào dùng cái nào — đây mới là phần thật sự đáng nhớ:
- Pre-order khi parent phải được xử lý trước child: serialize một tree (giá trị của root cho bộ deserialize biết cần dựng gì tiếp theo), copy một tree, in cây thư mục từ trên xuống, ký pháp tiền tố (Ba Lan) của biểu thức.
- In-order khi bạn muốn kết quả đã sắp xếp từ một BST, hoặc muốn “trải phẳng thành dãy” một cấu trúc. Ký pháp trung tố của expression tree.
- Post-order khi child phải được xử lý trước parent: giải phóng/xoá cây (không thể free một node rồi vẫn đi theo pointer của nó), tính một giá trị phụ thuộc vào kết quả của subtree (height, size,
du -sh), tính giá trị expression tree, ký pháp hậu tố (Nghịch đảo Ba Lan). - Level-order khi khoảng cách tới root mới là thứ quan trọng: tìm node nông nhất thoả một điều kiện, in cây theo hàng, tính tổng hợp theo từng level, hoặc serialize theo định dạng kiểu LeetCode
[1,2,3,null,null,4,5].
Traversal dạng lặp
Bản đệ quy ngắn gọn và rõ ràng, và trong Python production thường đó chính là thứ bạn nên dùng — cho tới khi cây trở nên quá sâu. Giới hạn đệ quy mặc định của CPython là 1000 frame, nên một cây degenerate 10.000 node sẽ ném RecursionError. Bản lặp dùng stack tường minh trên heap và không bị giới hạn đó.
def preorder_iterative(root):
"""Stack tường minh. Push right trước left để left được pop ra trước."""
if root is None:
return []
out, stack = [], [root]
while stack:
node = stack.pop()
out.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return out
def inorder_iterative(root):
"""Đi hết sang trái và push vào stack; rồi pop, visit, và rẽ phải."""
out, stack, cur = [], [], root
while cur is not None or stack:
while cur is not None:
stack.append(cur)
cur = cur.left
cur = stack.pop()
out.append(cur.val) # visit
cur = cur.right
return out
def postorder_iterative(root):
"""Mẹo: N-R-L chính là pre-order với hai child đảo chỗ; đảo ngược nó ra L-R-N."""
if root is None:
return []
out, stack = [], [root]
while stack:
node = stack.pop()
out.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
out.reverse()
return outMẹo post-order đáng để hiểu chứ không nên học thuộc: đảo ngược N-R-L sẽ ra L-R-N. Bản post-order “thật thà” một lượt cần thêm con trỏ last_visited hoặc cặp (node, visited_flag) trên stack, và đó mới là bản cần viết nếu bạn phải xử lý node ngay lúc pop thay vì gom thành list.
Level-order traversal (BFS)
Level-order là traversal duy nhất không phải là một phép đệ quy được sắp xếp lại. Nó cần queue thay vì stack (xem ./06-stacks-and-queues.md):
from collections import deque
def level_order(root):
"""Trả về danh sách phẳng các giá trị, theo từng level, trái sang phải."""
if root is None:
return []
out, q = [], deque([root])
while q:
node = q.popleft() # popleft() là O(1) trên deque; list.pop(0) là O(n)
out.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return out
def level_order_grouped(root):
"""Cùng phép duyệt, nhưng trả về một list cho mỗi level — dạng thường dùng thật sự."""
if root is None:
return []
levels, q = [], deque([root])
while q:
level_size = len(q) # chụp nhanh: đúng bằng số node ở depth hiện tại
level = []
for _ in range(level_size):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
levels.append(level)
return levelsViệc chụp level_size = len(q) ở đầu vòng lặp là idiom chuẩn để tách các level: tại thời điểm đó queue chứa đúng các node của một depth, nên tiêu thụ đúng chừng ấy node là xử lý xong đúng một level.
DFS so với BFS trên tree
Cả hai đều duyệt hết mọi node, cả hai đều O(n). Khác biệt nằm ở bộ nhớ và thứ tự phát hiện.
| DFS (pre/in/post-order) | BFS (level-order) | |
|---|---|---|
| Cấu trúc phụ trợ | Stack (tường minh hoặc call stack) | Queue |
| Bộ nhớ phụ đỉnh điểm | O(h) — chiều cao | O(w) — bề rộng lớn nhất |
| Trên cây balanced | O(log n) | O(n) — riêng level cuối đã ~n/2 node |
| Trên cây degenerate | O(n) | O(1) |
| Tìm ra kết quả nông nhất trước | Không | Có |
| Hợp với | ”Khám phá hết nhánh này”, tổng hợp theo subtree | ”Cách root bao xa”, số bước ngắn nhất |
| Thân thiện với đệ quy | Có | Không (cần queue tường minh) |
Quy tắc thực dụng: DFS rẻ hơn về bộ nhớ trên loại cây bạn thường gặp (tương đối cân bằng, nên O(log n) so với O(n)), nhưng BFS là cách duy nhất tìm ra đáp án nông nhất trước. Nếu câu hỏi là “cần tối thiểu bao nhiêu bước để tới X”, hãy dùng BFS. Điều này mở rộng thẳng sang graph, nơi BFS trên unweighted graph cho ra shortest path — xem ./13-graph-data-structures.md và ./14-shortest-path-algorithms.md.
Một lưu ý thực tế về bộ nhớ của BFS: trên perfect binary tree n node, level sâu nhất chứa khoảng n/2 node, tất cả đều nằm trong queue cùng lúc. BFS trên cây rộng có thể ngốn nhiều bộ nhớ hơn cả bản thân cái cây. DFS thì không bao giờ giữ nhiều hơn một đường root-tới-leaf.
Các phép tính thường gặp trên tree
Gần như mọi câu hỏi về tree đều là một phép post-order traversal có trả về giá trị thay vì append vào list:
def height(node):
"""Height tính bằng EDGE. Cây rỗng trả -1 để cây một node là 0. O(n) thời gian, O(h) bộ nhớ."""
if node is None:
return -1
return 1 + max(height(node.left), height(node.right))
def size(node):
"""Số node. O(n)."""
if node is None:
return 0
return 1 + size(node.left) + size(node.right)
def diameter(root):
"""Đường dài nhất (theo edge) giữa hai node bất kỳ. O(n) — một lượt, không phải O(n^2)."""
best = 0
def depth(node):
nonlocal best
if node is None:
return -1
left = depth(node.left)
right = depth(node.right)
# Đường dài nhất ĐI QUA node này, làm ứng viên cho kết quả toàn cục
best = max(best, left + right + 2)
return 1 + max(left, right)
depth(root)
return best
def is_balanced(root):
"""Cân bằng theo nghĩa AVL: |height(L) - height(R)| <= 1 ở mọi nơi. O(n)."""
def check(node):
# Trả về height, hoặc None làm sentinel nghĩa là "phía dưới đã mất cân bằng"
if node is None:
return -1
left = check(node.left)
if left is None:
return None
right = check(node.right)
if right is None:
return None
if abs(left - right) > 1:
return None
return 1 + max(left, right)
return check(root) is not NoneHai hàm diameter và is_balanced minh hoạ một pattern đáng thấm: bản ngây thơ gọi height() tại mọi node, cho ra O(n²) (hoặc O(n log n) trên cây cân bằng). Trả height kèm theo đáp án từ một lượt post-order duy nhất biến nó thành O(n). Mỗi khi một lời giải trên tree trông có vẻ bậc hai, hãy tự hỏi phép đệ quy có thể trả cái gì lên trên để khỏi tính lại.
Binary search tree
Binary search tree (BST) là binary tree có thêm một ràng buộc về thứ tự:
Với mọi node
x: mọi key trong subtree trái củaxđều< x.key, và mọi key trong subtree phải đều> x.key.
Ràng buộc phải đúng tại mọi node, không chỉ ở root — một lỗi phổ biến là chỉ kiểm tra child trực tiếp, khiến những cây như 50 → left 30 → right 60 được chấp nhận (60 nằm trong subtree trái của 50 nhưng lại lớn hơn 50, nên đây không phải BST dù 30 < 50 và 30 < 60).
Hai hệ quả khiến BST trở nên hữu dụng:
- Search là một chuỗi quyết định hai nhánh, nên tốn
O(h)— logarit khi cây cân bằng. - In-order traversal phát ra các key theo thứ tự đã sắp xếp, miễn phí, trong
O(n). Đây là thứ BST cho bạn mà hash table không bao giờ cho: duyệt có thứ tự, range query, predecessor/successor, min/max.
class BST:
"""Binary search tree thuần, không tự cân bằng, key phân biệt."""
def __init__(self):
self.root = None
# ---- search -------------------------------------------------------
def search(self, key):
"""Dạng lặp — không lo giới hạn đệ quy. O(h)."""
node = self.root
while node is not None:
if key == node.val:
return node
node = node.left if key < node.val else node.right
return None
def min_node(self, node):
"""Node trái nhất của một subtree. O(h)."""
while node.left is not None:
node = node.left
return node
# ---- insert -------------------------------------------------------
def insert(self, key):
"""Key mới luôn trở thành leaf — đường search CHÍNH LÀ đường insert."""
self.root = self._insert(self.root, key)
def _insert(self, node, key):
if node is None:
return Node(key)
if key < node.val:
node.left = self._insert(node.left, key)
elif key > node.val:
node.right = self._insert(node.right, key)
# key == node.val: trùng, bỏ qua (hoặc giữ thêm một field đếm)
return node
# ---- delete -------------------------------------------------------
def delete(self, key):
self.root = self._delete(self.root, key)
def _delete(self, node, key):
if node is None:
return None
if key < node.val:
node.left = self._delete(node.left, key)
elif key > node.val:
node.right = self._delete(node.right, key)
else:
# Case 1 & 2: không có hoặc có một child — kéo child lên thế chỗ.
if node.left is None:
return node.right # bao luôn trường hợp "không child" (trả None)
if node.right is None:
return node.left
# Case 3: hai child. Thay key của node này bằng in-order successor
# (key nhỏ nhất trong subtree phải), rồi xoá successor đó khỏi
# subtree phải — nơi nó có tối đa một child.
succ = self.min_node(node.right)
node.val = succ.val
node.right = self._delete(node.right, succ.val)
return node
def inorder(self):
out = []
inorder(self.root, out)
return outBa trường hợp delete, viết ra cụ thể vì đây là chỗ các bản cài đặt BST hay sai:
Case 1 — leaf (không child): chỉ việc bỏ đi.
(50) (50)
/ \ => / \
(30) (70) (30) (70)
/ /
(60) xoá 60 -
Case 2 — một child: kéo child lên đúng vị trí node bị xoá.
(50) (50)
/ \ => / \
(30) (70) (30) (60)
/
(60) xoá 70
Case 3 — hai child: chép key của in-order successor vào đây,
rồi xoá successor đó khỏi subtree phải.
(50) (60)
/ \ => / \
(30) (70) (30) (70)
/ \ \
(60) (80) (80)
xoá 50Successor ở case 3 là node trái nhất của subtree phải — key nhỏ nhất mà vẫn lớn hơn key bị xoá. Vì nó trái nhất nên nó không có left child, nên việc xoá nó luôn rơi vào case 1 hoặc case 2, và phép đệ quy kết thúc. Dùng in-order predecessor (node phải nhất của subtree trái) cũng đúng như vậy; luôn chọn cùng một bên là nguyên nhân đã biết gây lệch cây về dài hạn, và luân phiên hai bên là cách giảm thiểu rẻ tiền cho một BST thuần.
Vì sao BST không cân bằng suy biến về O(n)
Mọi thao tác BST đều tốn O(h), với h là height. Cái O(log n) bạn được hứa chỉ đúng khi h ≈ log n. Không có gì trong thuật toán insert của BST bắt buộc điều đó.
Insert 1, 2, 3, 4, 5 vào một BST rỗng theo đúng thứ tự đó:
insert 1: (1)
insert 2: (1) 2 > 1, rẽ phải
\
(2)
insert 3: (1) 3 > 1 -> phải; 3 > 2 -> phải
\
(2)
\
(3)
insert 5: (1)
\
(2)
\
(3)
\
(4)
\
(5) height = 4 = n - 1Cây trở thành một linked list kèm thêm chi phí bộ nhớ. search(5) phải đi qua mọi node: O(n). Tất cả cấu trúc đó chỉ mua cho bạn một left pointer bỏ không trên mỗi node.
Và đây không phải một worst case gượng ép — dữ liệu đã sắp xếp là hình dạng phổ biến nhất của dữ liệu thật. ID tự tăng, timestamp, một table nạp từ bản export đã sắp xếp, một log replay theo thứ tự: mỗi cái đều dựng nên một BST suy biến tối đa.
| Thao tác | BST cân bằng | BST degenerate | Vì sao |
|---|---|---|---|
| Search | O(log n) | O(n) | Chi phí là O(h); h là log n so với n − 1 |
| Insert | O(log n) | O(n) | Insert = search vị trí + nối link O(1) |
| Delete | O(log n) | O(n) | Search + tìm successor, cả hai đều O(h) |
| Min / max | O(log n) | O(n) | Đi tới leaf trái nhất/phải nhất |
| Predecessor / successor | O(log n) | O(n) | O(h) |
| In-order traversal | O(n) | O(n) | Dù sao cũng phải thăm mọi node |
| Bộ nhớ | O(n) | O(n) | Hai pointer mỗi node ở cả hai trường hợp |
| Bộ nhớ phụ khi traversal | O(log n) | O(n) | Độ sâu stack = height |
Thứ tự insert ngẫu nhiên cho height kỳ vọng khoảng 2 ln n ≈ 1.39 log₂ n, tức là ổn — nên BST được nạp key thật sự ngẫu nhiên hoạt động tốt trung bình. Nhưng bạn không thể trông cậy input của mình là ngẫu nhiên, và một kẻ tấn công (hoặc một bản export ORDER BY id) sẽ trao cho bạn đúng worst case. Cách sửa là dùng cây tự cân bằng lại sau mỗi lần thay đổi: AVL tree, red-black tree, B-tree, hoặc skip list. Đó là toàn bộ nội dung của ./11-balanced-and-multiway-trees.md.
BST so với hash table
Đáng nêu rõ, vì lựa chọn này xuất hiện liên tục:
| Hash table (./07-hash-tables.md) | BST cân bằng | |
|---|---|---|
| Lookup / insert / delete | O(1) trung bình, O(n) worst case | O(log n) đảm bảo |
| Duyệt có thứ tự | Không (hoặc chỉ theo thứ tự insert) | Có, O(n) in-order |
Range query [a, b] | O(n) — phải quét hết | O(log n + k) |
| Min / max / successor | O(n) | O(log n) |
| Overhead bộ nhớ | Phần dư theo load factor + bucket | 2 pointer + metadata cân bằng mỗi node |
| Độ tin cậy của worst case | Kém (collision, khựng khi rehash) | Tốt — không có đỉnh nhọn do amortization |
Dùng hash table khi bạn chỉ bao giờ hỏi “key chính xác này có tồn tại không”. Dùng BST cân bằng (Python không có sẵn; sortedcontainers.SortedDict hoặc bisect trên list là hai thay thế thực dụng) khi bạn cần thứ tự — range scan, “cuộc hẹn kế tiếp sau 3 giờ chiều”, bảng xếp hạng, hoặc bất cứ thứ gì có BETWEEN. Đây cũng chính xác là lý do database index bằng B+ tree thay vì hash table theo mặc định: WHERE created_at BETWEEN ... AND ... và ORDER BY đều là thao tác theo range.
Best Practices
- Ưu tiên dạng lặp cho search, đệ quy cho cấu trúc.
search,min,maxcủa BST viết dạng lặp rất dễ và tránh hẳn giới hạn đệ quy. Traversal và các phép tính tổng hợp đọc dễ hơn nhiều khi viết đệ quy — chỉ chuyển sang stack tường minh khi cây có thể sâu hoặc được sinh ra từ input không tin cậy. - Biết rõ giới hạn đệ quy của mình. CPython mặc định 1000 frame; một cây degenerate 10.000 node sẽ ném
RecursionErrortrong traversal đệ quy. Nângsys.setrecursionlimitcó nguy cơ làm interpreter crash cứng vì ràng buộc thật nằm ở C stack — hãy dùng stack tường minh thay vì vậy. - Kiểm tra BST bằng biên, không bằng so sánh cục bộ. Cách đúng là truyền một khoảng
(low, high)xuống theo đệ quy; chỉ so sánhnode.left.val < node.val < node.right.vallà một đáp án sai kinh điển, nó chấp nhận cả những cây không phải BST. - Đừng bao giờ dựng BST thuần từ dữ liệu đã sắp xếp. Nó suy biến thành linked list và mọi thao tác thành
O(n). Hoặc xáo trộn input trước, hoặc dựng đệ quy từ phần tử giữa (cách này cho ra cây cân bằng hoàn hảo trongO(n)từ mảng đã sắp xếp), hoặc dùng cây tự cân bằng. - Trả kết quả tổng hợp lên trên theo đệ quy thay vì tính lại. Gọi
height()bên trong một vòng lặp chạy qua từng node biến bài toánO(n)thànhO(n²). Một lượt post-order duy nhất trả về(height, đáp án)là xong. - Dùng
collections.dequecho BFS, tuyệt đối không dùnglist.list.pop(0)làO(n)vì nó dịch mọi phần tử còn lại, âm thầm biến một traversalO(n)thànhO(n²).deque.popleft()làO(1). - Cẩn thận bộ nhớ BFS trên cây rộng. Queue giữ trọn một level; trên perfect binary tree đó là ~n/2 node. Nếu bạn chỉ cần thăm hết mọi node và thứ tự không quan trọng, DFS chỉ tốn
O(h). - Xử lý cây rỗng ngay đầu tiên.
if node is Nonelàm dòng đầu của mọi hàm đệ quy trên tree loại bỏ phần lớn bug về tree trước cả khi chúng tồn tại. - Chốt quy ước height và ghi vào docstring. Lỗi lệch một đơn vị giữa quy ước edge và node trong
height()và trong hàm kiểm tra cân bằng nằm trong nhóm bug tree phổ biến nhất, và chúng vô hình cho tới khi cây trở nên sâu. - Đừng lưu tree tổng quát trong mảng trừ khi nó complete. Phép tính chỉ số rất đẹp nhưng một cây degenerate
nnode sẽ cần2ⁿô.
Tài liệu tham khảo
- roadmap.sh — Data Structures & Algorithms
- Tree (abstract data type) — Wikipedia
- Binary tree — Wikipedia
- Binary search tree — Wikipedia
- Tree traversal — Wikipedia
- Breadth-first search — Wikipedia
- Depth-first search — Wikipedia
- CLRS — Introduction to Algorithms, Chapter 12: Binary Search Trees
- MIT 6.006 — Introduction to Algorithms (OpenCourseWare)
- VisuAlgo — Binary Search Tree visualization
- Big-O Cheat Sheet
- Python Documentation —
collections.deque
Part of the Data Structures & Algorithms Roadmap knowledge base.
Overview
Every structure covered so far — arrays, linked lists, stacks, queues, hash tables — is linear: elements sit in a sequence, and “next” means exactly one thing. A tree is the first genuinely non-linear structure. Each node can point at several children, so “next” branches, and the result is a hierarchy: a shape that naturally models containment, classification, and decomposition.
Hierarchies are everywhere in computing, which is why trees are everywhere too:
- A filesystem is a tree: directories contain files and other directories.
- The HTML DOM is a tree:
<html>contains<body>contains<div>contains text. - A database index is a tree — a B+ tree, specifically (see ./11-balanced-and-multiway-trees.md and ../../postgresql-dba/en/08-indexing-strategies.md).
- A compiler’s parse tree is a tree:
a + b * cdecomposes into an expression whose right operand is itself an expression. - Decision trees, org charts, JSON documents, Git’s commit and object model, routing tries — all trees.
The reason trees earn a chapter of their own is not just modelling, though. It is the O(log n). A linear structure forces you to walk past k elements to reach the k-th one. A tree with a branching factor of 2 lets you halve the remaining candidates at every step, so n elements are reachable in about log₂ n steps. A million items is 20 steps; a billion is 30. That is the same trick binary search plays on a sorted array (see ./09-search-algorithms.md), except a tree keeps the property while supporting cheap insertion and deletion, which a sorted array does not.
The catch — and it is the whole subject of the next note — is that the O(log n) only holds while the tree stays bushy. A binary search tree that has been fed sorted data collapses into a linked list and every operation degrades to O(n). This note builds the vocabulary, the traversals, and the plain binary search tree; the next one fixes the degeneracy.
Fundamentals
Terminology
A tree is a set of nodes connected by edges, with exactly one node designated the root, and with the constraint that every non-root node has exactly one parent. Equivalently: a tree is a connected acyclic graph with a distinguished root. A collection of disjoint trees is a forest.
(A) <- root, depth 0
/ \
(B) (C) <- B and C are siblings; children of A
/ \ \
(D) (E) (F) <- depth 2
/
(G) <- leaf, depth 3| Term | Meaning | In the diagram |
|---|---|---|
| Root | The single node with no parent | A |
| Parent | The node one level up | parent of E is B |
| Child | A node one level down | children of B are D, E |
| Siblings | Nodes sharing a parent | B and C; D and E |
| Leaf (external node) | A node with no children | D, G, F |
| Internal node | A node with at least one child | A, B, C, E |
| Edge | A parent→child link | A–B |
| Path | A sequence of edges between two nodes | A → B → E → G |
| Ancestor | Any node on the path up to the root | ancestors of G: E, B, A |
| Descendant | Any node reachable going down | descendants of B: D, E, G |
| Subtree | A node plus all its descendants | subtree rooted at B = {B, D, E, G} |
| Degree of a node | Number of children | degree of A = 2, of C = 1 |
| Depth of a node | Number of edges from the root down to it | depth of G = 3 |
| Height of a node | Number of edges on the longest path down to a leaf | height of B = 2 |
| Height of the tree | Height of the root | 3 |
| Level | All nodes at the same depth | level 2 = {D, E, F} |
Two conventions cause endless confusion, so pin them down:
- Height is measured in edges here (a single-node tree has height 0). Some textbooks count nodes, making it height 1. Both appear in the wild; what matters is being consistent within one piece of code. The Python code below uses the edge convention for
height()and the node convention for AVL’s storedheightfield in the next note, because that is what the standard AVL formulation expects — a good illustration of why you should always check. - Depth counts downward from the root; height counts upward from the leaves. They are not the same measurement from opposite ends of the same path, except for the root and for leaves on the longest path.
Two structural facts worth memorizing: a tree with n nodes has exactly n − 1 edges (every node except the root contributes exactly one edge to its parent), and there is exactly one simple path between any two nodes.
Representing a tree in code
The general (n-ary) case is a node holding a value and a list of children:
class TreeNode:
"""A general n-ary tree node: one value, any number of children."""
__slots__ = ("value", "children")
def __init__(self, value, children=None):
self.value = value
self.children = children if children is not None else []
def add(self, child):
self.children.append(child)
return child
# Model a small filesystem
root = TreeNode("/")
usr = root.add(TreeNode("usr"))
etc = root.add(TreeNode("etc"))
usr.add(TreeNode("bin"))
usr.add(TreeNode("lib"))
etc.add(TreeNode("hosts"))Note there is no parent pointer here. Adding one (self.parent) makes upward navigation O(1) and is essential for operations like “find the path back to the root” or “find the next in-order node without a stack”, but it costs a word per node and creates a reference cycle that a naive reference-counting collector would leak. Add it when you need it, not by default.
Binary trees
A binary tree restricts every node to at most two children, named left and right. The order matters: a node with only a left child is a different tree from a node with only a right child, even though both have one child.
class Node:
"""A binary tree node."""
__slots__ = ("val", "left", "right")
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = rightWhy restrict to two? Because two is the smallest branching factor that still halves the problem, and because a two-way decision (less / greater) is the natural output of a comparison. Higher fan-outs are useful, but for a different reason — minimizing disk reads rather than comparisons — which is exactly what B-trees do.
Shapes of binary trees
The names below get used loosely in the wild; these are the standard definitions.
full (every node has 0 or 2 children) complete (all levels full except
(1) possibly the last, filled left-to-right)
/ \ (1)
(2) (3) / \
/ \ (2) (3)
(4) (5) / \ /
(4) (5) (6)
perfect (full AND all leaves at the degenerate (each node has one child —
same depth) effectively a linked list)
(1) (1)
/ \ \
(2) (3) (2)
/ \ / \ \
(4) (5) (6) (7) (3)
\
(4)| Shape | Definition | Height with n nodes |
|---|---|---|
| Full (strict/proper) | Every node has 0 or 2 children — never exactly 1 | Unbounded (can still be tall) |
| Complete | Every level full except possibly the last, which fills left to right | Exactly ⌊log₂ n⌋ |
| Perfect | Full and every leaf at the same depth | Exactly log₂(n + 1) − 1 |
| Balanced | Height is O(log n); usually “subtree heights differ by ≤ 1 at every node” | O(log n) |
| Degenerate (pathological) | Every internal node has exactly one child | n − 1 |
Useful arithmetic that falls straight out of these definitions:
- A perfect binary tree of height
hhas2^(h+1) − 1nodes, of which2^hare leaves — roughly half of all nodes in a perfect tree are leaves. This is why “do work at the leaves” dominates the cost of most tree algorithms and why heapify isO(n)rather thanO(n log n)(see ./12-heaps-and-priority-queues.md). - Any binary tree with
nnodes has height at least⌈log₂(n + 1)⌉ − 1and at mostn − 1. That gap betweenlog nandnis the entire performance story of trees. - In a full binary tree, the number of leaves is exactly one more than the number of internal nodes.
Complete binary trees have a special superpower: because there are no gaps, they can be stored in a flat array with no pointers at all, using index arithmetic — node i’s children are at 2i+1 and 2i+2. That is exactly how a binary heap is implemented, and it is developed in ./12-heaps-and-priority-queues.md. For a general (non-complete) tree, this array layout wastes O(2^h) slots on a degenerate shape, so it is not a general-purpose representation.
Key Concepts
Tree traversal
A traversal visits every node exactly once in some defined order. There are four standard orders, and the first three are the same recursive walk with the “visit” statement moved to a different place:
| Traversal | Order | Mnemonic | On a BST it yields |
|---|---|---|---|
| Pre-order | Node, Left, Right | N-L-R | Root first — good for copying/serializing |
| In-order | Left, Node, Right | L-N-R | Sorted ascending |
| Post-order | Left, Right, Node | L-R-N | Children before parent — good for deletion/evaluation |
| Level-order (BFS) | Level by level, left to right | — | Shape by depth |
def preorder(node, out):
"""N-L-R: visit the node before descending."""
if node is None:
return
out.append(node.val) # visit
preorder(node.left, out)
preorder(node.right, out)
def inorder(node, out):
"""L-N-R: on a BST this emits the keys in ascending order."""
if node is None:
return
inorder(node.left, out)
out.append(node.val) # visit
inorder(node.right, out)
def postorder(node, out):
"""L-R-N: both children are fully processed before the node itself."""
if node is None:
return
postorder(node.left, out)
postorder(node.right, out)
out.append(node.val) # visitFor the tree below:
(F)
/ \
(B) (G)
/ \ \
(A) (D) (I)
/ \ /
(C) (E)(H)| Traversal | Output |
|---|---|
| Pre-order | F B A D C E G I H |
| In-order | A B C D E F G H I |
| Post-order | A C E D B H I G F |
| Level-order | F B G A D I C E H |
Notice the in-order output is alphabetical — that tree is a BST.
When to use which — this is the part that is actually worth remembering:
- Pre-order when the parent must be handled before its children: serializing a tree (the root’s value tells the deserializer what to build next), copying a tree, printing a directory listing top-down, prefix (Polish) notation of an expression.
- In-order when you want sorted output from a BST, or the “flatten to a sequence” reading of a structure. Infix notation of an expression tree.
- Post-order when children must be handled before the parent: freeing/deleting a tree (you cannot free a node then follow its pointers), computing a value that depends on the subtree results (height, size,
du -sh), evaluating an expression tree, postfix (Reverse Polish) notation. - Level-order when distance from the root is the thing that matters: finding the shallowest node satisfying a predicate, printing a tree by rows, computing per-level aggregates, or serializing in the LeetCode-style
[1,2,3,null,null,4,5]format.
Iterative traversals
The recursive versions are short and clear, and in production Python they are usually what you want — until the tree is deep. CPython’s default recursion limit is 1000 frames, so a degenerate tree of 10,000 nodes raises RecursionError. Iterative versions use an explicit stack on the heap and have no such limit.
def preorder_iterative(root):
"""Explicit stack. Push right before left so left is popped first."""
if root is None:
return []
out, stack = [], [root]
while stack:
node = stack.pop()
out.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return out
def inorder_iterative(root):
"""Walk left as far as possible, pushing; then pop, visit, and go right."""
out, stack, cur = [], [], root
while cur is not None or stack:
while cur is not None:
stack.append(cur)
cur = cur.left
cur = stack.pop()
out.append(cur.val) # visit
cur = cur.right
return out
def postorder_iterative(root):
"""Trick: N-R-L is pre-order with the children swapped; reverse it to get L-R-N."""
if root is None:
return []
out, stack = [], [root]
while stack:
node = stack.pop()
out.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
out.reverse()
return outThe post-order trick is worth understanding rather than memorizing: reversing N-R-L gives L-R-N. The “honest” single-pass post-order needs a last_visited pointer or a (node, visited_flag) pair on the stack, and is the version to write if you need to process nodes as you pop them rather than collecting a list.
Level-order traversal (BFS)
Level-order is the one traversal that is not a rearranged recursion. It needs a queue instead of a stack (see ./06-stacks-and-queues.md):
from collections import deque
def level_order(root):
"""Returns a flat list of values, level by level, left to right."""
if root is None:
return []
out, q = [], deque([root])
while q:
node = q.popleft() # popleft() is O(1) on a deque; list.pop(0) is O(n)
out.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return out
def level_order_grouped(root):
"""Same walk, but returns one list per level — the usual form you actually want."""
if root is None:
return []
levels, q = [], deque([root])
while q:
level_size = len(q) # snapshot: exactly the nodes at the current depth
level = []
for _ in range(level_size):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
levels.append(level)
return levelsThe level_size = len(q) snapshot at the top of the loop is the standard idiom for separating levels: at that instant the queue contains exactly the nodes of one depth, so consuming that many nodes processes exactly one level.
DFS versus BFS on a tree
Both visit every node, both are O(n) time. The difference is memory and order of discovery.
| DFS (pre/in/post-order) | BFS (level-order) | |
|---|---|---|
| Auxiliary structure | Stack (explicit or the call stack) | Queue |
| Peak auxiliary space | O(h) — the height | O(w) — the maximum width |
| On a balanced tree | O(log n) | O(n) — the last level alone is ~n/2 nodes |
| On a degenerate tree | O(n) | O(1) |
| Finds the shallowest match first | No | Yes |
| Natural fit | ”Explore this branch fully”, subtree aggregates | ”How far from the root”, shortest hop count |
| Recursion-friendly | Yes | No (needs an explicit queue) |
The rule of thumb: DFS is cheaper in memory on the trees you usually have (balanced-ish, so O(log n) versus O(n)), but BFS is the only one that finds the shallowest answer first. If the question is “what is the minimum number of steps to X”, use BFS. This generalizes directly to graphs, where BFS on an unweighted graph gives shortest paths — see ./13-graph-data-structures.md and ./14-shortest-path-algorithms.md.
One practical caveat about BFS’s space: on a perfect binary tree of n nodes, the deepest level holds about n/2 nodes, all of which are queued simultaneously. A BFS over a wide tree can easily use more memory than the tree itself. DFS never holds more than one root-to-leaf path.
Common tree computations
Almost every tree question is a post-order traversal that returns something instead of appending to a list:
def height(node):
"""Height in EDGES. Empty tree is -1 so a single node is 0. O(n) time, O(h) space."""
if node is None:
return -1
return 1 + max(height(node.left), height(node.right))
def size(node):
"""Number of nodes. O(n)."""
if node is None:
return 0
return 1 + size(node.left) + size(node.right)
def diameter(root):
"""Longest path (in edges) between any two nodes. O(n) — one pass, not O(n^2)."""
best = 0
def depth(node):
nonlocal best
if node is None:
return -1
left = depth(node.left)
right = depth(node.right)
# The longest path THROUGH this node, as a candidate for the global best
best = max(best, left + right + 2)
return 1 + max(left, right)
depth(root)
return best
def is_balanced(root):
"""Height-balanced in the AVL sense: |height(L) - height(R)| <= 1 everywhere. O(n)."""
def check(node):
# Returns the height, or None as a sentinel meaning "already unbalanced below"
if node is None:
return -1
left = check(node.left)
if left is None:
return None
right = check(node.right)
if right is None:
return None
if abs(left - right) > 1:
return None
return 1 + max(left, right)
return check(root) is not NoneThe diameter and is_balanced implementations illustrate a pattern worth internalizing: the naive version calls height() at every node, giving O(n²) (or O(n log n) on a balanced tree). Returning the height along with the answer from a single post-order pass makes it O(n). Whenever a tree solution looks quadratic, ask what the recursion could return upward to avoid recomputation.
Binary search trees
A binary search tree (BST) is a binary tree with an ordering invariant:
For every node
x: every key inx’s left subtree is< x.key, and every key inx’s right subtree is> x.key.
The invariant must hold at every node, not just the root — a common bug is checking only the immediate children, which accepts trees like 50 → left 30 → right 60 (60 is in the left subtree of 50 but is larger than 50, so it is not a BST even though 30 < 50 and 30 < 60).
Two consequences make the BST useful:
- Search is a sequence of two-way decisions, so it costs
O(h)— logarithmic when the tree is balanced. - In-order traversal emits the keys in sorted order, for free, in
O(n). This is what a BST gives you that a hash table never will: ordered iteration, range queries, predecessor/successor, min/max.
class BST:
"""A plain, unbalanced binary search tree with distinct keys."""
def __init__(self):
self.root = None
# ---- search -------------------------------------------------------
def search(self, key):
"""Iterative — no recursion depth risk. O(h)."""
node = self.root
while node is not None:
if key == node.val:
return node
node = node.left if key < node.val else node.right
return None
def min_node(self, node):
"""Leftmost node of a subtree. O(h)."""
while node.left is not None:
node = node.left
return node
# ---- insert -------------------------------------------------------
def insert(self, key):
"""New keys always become leaves — the search path IS the insertion path."""
self.root = self._insert(self.root, key)
def _insert(self, node, key):
if node is None:
return Node(key)
if key < node.val:
node.left = self._insert(node.left, key)
elif key > node.val:
node.right = self._insert(node.right, key)
# key == node.val: duplicate, ignore (or keep a count field)
return node
# ---- delete -------------------------------------------------------
def delete(self, key):
self.root = self._delete(self.root, key)
def _delete(self, node, key):
if node is None:
return None
if key < node.val:
node.left = self._delete(node.left, key)
elif key > node.val:
node.right = self._delete(node.right, key)
else:
# Case 1 & 2: zero or one child — splice the child up into our place.
if node.left is None:
return node.right # covers "no children" too (returns None)
if node.right is None:
return node.left
# Case 3: two children. Replace this node's key with its in-order
# successor (smallest key in the right subtree), then delete that
# successor from the right subtree — where it has at most one child.
succ = self.min_node(node.right)
node.val = succ.val
node.right = self._delete(node.right, succ.val)
return node
def inorder(self):
out = []
inorder(self.root, out)
return outThe three delete cases, spelled out because this is where BST implementations go wrong:
Case 1 — leaf (no children): just remove it.
(50) (50)
/ \ => / \
(30) (70) (30) (70)
/ /
(60) delete 60 -
Case 2 — one child: splice the child into the deleted node's position.
(50) (50)
/ \ => / \
(30) (70) (30) (60)
/
(60) delete 70
Case 3 — two children: copy the in-order successor's key here,
then delete the successor from the right subtree.
(50) (60)
/ \ => / \
(30) (70) (30) (70)
/ \ \
(60) (80) (80)
delete 50Case 3’s successor is the leftmost node of the right subtree — the smallest key strictly greater than the one being removed. Because it is leftmost, it has no left child, so deleting it is always case 1 or case 2, and the recursion terminates. Using the in-order predecessor (rightmost node of the left subtree) works equally well; always picking the same side is a known cause of long-term tree skew, and alternating is a cheap mitigation for a plain BST.
Why an unbalanced BST degenerates to O(n)
Every BST operation costs O(h), where h is the height. The O(log n) you were promised is only true when h ≈ log n. Nothing in the BST insert algorithm enforces that.
Insert 1, 2, 3, 4, 5 into an empty BST in that order:
insert 1: (1)
insert 2: (1) 2 > 1, goes right
\
(2)
insert 3: (1) 3 > 1 -> right; 3 > 2 -> right
\
(2)
\
(3)
insert 5: (1)
\
(2)
\
(3)
\
(4)
\
(5) height = 4 = n - 1The tree is a linked list with extra memory overhead. search(5) visits every node: O(n). All the structure has bought you is a wasted left pointer per node.
And this is not a contrived worst case — sorted input is the single most common shape of real data. Auto-incrementing IDs, timestamps, a table loaded from an already-sorted export, a log replayed in order: every one of them builds a maximally degenerate BST.
| Operation | Balanced BST | Degenerate BST | Why |
|---|---|---|---|
| Search | O(log n) | O(n) | Cost is O(h); h is log n versus n − 1 |
| Insert | O(log n) | O(n) | Insert = search for the position + O(1) link |
| Delete | O(log n) | O(n) | Search + successor lookup, both O(h) |
| Min / max | O(log n) | O(n) | Walk to the leftmost/rightmost leaf |
| Predecessor / successor | O(log n) | O(n) | O(h) |
| In-order traversal | O(n) | O(n) | Must visit every node regardless |
| Space | O(n) | O(n) | Two pointers per node either way |
| Traversal aux. space | O(log n) | O(n) | Stack depth = height |
Random insertion order gives an expected height of about 2 ln n ≈ 1.39 log₂ n, which is fine — so a BST fed genuinely random keys behaves well on average. But you cannot rely on your input being random, and an adversary (or a ORDER BY id export) will hand you the worst case. The fix is a tree that rebalances itself on every mutation: AVL trees, red-black trees, B-trees, or a skip list. That is the whole of ./11-balanced-and-multiway-trees.md.
BST versus hash table
Worth stating plainly, because the choice comes up constantly:
| Hash table (./07-hash-tables.md) | Balanced BST | |
|---|---|---|
| Lookup / insert / delete | O(1) average, O(n) worst | O(log n) guaranteed |
| Ordered iteration | No (or insertion order only) | Yes, O(n) in-order |
Range query [a, b] | O(n) — must scan everything | O(log n + k) |
| Min / max / successor | O(n) | O(log n) |
| Memory overhead | Load factor slack + buckets | 2 pointers + balance metadata per node |
| Worst-case predictability | Poor (collisions, rehash pauses) | Good — no amortization spikes |
Use a hash table when you only ever ask “is this exact key present”. Use a balanced BST (Python has no built-in one; sortedcontainers.SortedDict or bisect on a list are the practical stand-ins) when you need order — range scans, “the next appointment after 3pm”, leaderboards, or anything with a BETWEEN. This is also exactly why databases index with B+ trees rather than hash tables by default: WHERE created_at BETWEEN ... AND ... and ORDER BY are range operations.
Best Practices
- Prefer iteration for search, recursion for structure. BST
search,min, andmaxare trivially iterative and dodge the recursion limit entirely. Traversals and aggregate computations read far better recursively — switch them to an explicit stack only when the tree can be deep or produced by untrusted input. - Know your recursion limit. CPython defaults to 1000 frames; a 10,000-node degenerate tree will raise
RecursionErrorin a recursive traversal. Raisingsys.setrecursionlimitrisks a hard interpreter crash because the C stack is the real constraint — use an explicit stack instead. - Validate a BST with bounds, not with local comparisons. The correct check passes a
(low, high)range down the recursion; comparing onlynode.left.val < node.val < node.right.valis a classic wrong answer that accepts non-BSTs. - Never build a plain BST from sorted data. It degenerates to a linked list and every operation becomes
O(n). Either shuffle the input first, build from the median recursively (which yields a perfectly balanced tree inO(n)from a sorted array), or use a self-balancing tree. - Return the aggregate up the recursion instead of recomputing it. Calling
height()inside a per-node loop turns anO(n)problem intoO(n²). One post-order pass that returns(height, answer)fixes it. - Use
collections.dequefor BFS, never alist.list.pop(0)isO(n)because it shifts every remaining element, silently turning anO(n)traversal intoO(n²).deque.popleft()isO(1). - Watch BFS memory on wide trees. The queue holds a whole level; on a perfect binary tree that is ~n/2 nodes. If you only need to visit everything and order does not matter, DFS uses
O(h). - Handle the empty tree first.
if node is Noneas the first line of every recursive tree function eliminates most tree bugs before they exist. - Decide your height convention and write it in the docstring. Edges-vs-nodes off-by-one errors between
height()and a balance check are among the most common tree bugs, and they are invisible until the tree is deep. - Do not store a general tree in an array unless it is complete. The index arithmetic is elegant but a degenerate tree of
nnodes needs2ⁿslots.
References
- roadmap.sh — Data Structures & Algorithms
- Tree (abstract data type) — Wikipedia
- Binary tree — Wikipedia
- Binary search tree — Wikipedia
- Tree traversal — Wikipedia
- Breadth-first search — Wikipedia
- Depth-first search — Wikipedia
- CLRS — Introduction to Algorithms, Chapter 12: Binary Search Trees
- MIT 6.006 — Introduction to Algorithms (OpenCourseWare)
- VisuAlgo — Binary Search Tree visualization
- Big-O Cheat Sheet
- Python Documentation —
collections.deque