Python Tutorial
Trees
A hierarchical structure of nodes with a single root and no cycles — the shape of file systems, org charts, and parse trees.
Tree Terminology
- Root: the top node with no parent.
- Child / Parent: a node directly below / above another.
- Leaf: a node with no children.
- Edge: a link between parent and child.
- Depth: distance from the root; height: longest path to a leaf.
- Subtree: a node together with all its descendants.
Unlike linear structures, a tree branches: one node can have many children, but every node (except the root) has exactly one parent, and there are no cycles.
A General Tree Node
class TreeNode:
def __init__(self, value):
self.value = value
self.children = []
def add(self, child):
self.children.append(child)
root = TreeNode("CEO")
cto = TreeNode("CTO")
cfo = TreeNode("CFO")
root.add(cto); root.add(cfo)
cto.add(TreeNode("Dev Lead"))
for c in root.children:
print(c.value) # CTO, CFOTraversing a Tree
Visiting every node uses either depth-first (go deep before wide) or breadth-first (level by level).
def dfs(node):
print(node.value)
for child in node.children:
dfs(child) # recursion uses the call stack
from collections import deque
def bfs(node):
q = deque([node])
while q:
cur = q.popleft()
print(cur.value)
q.extend(cur.children)
dfs(root) # CEO, CTO, Dev Lead, CFO
bfs(root) # CEO, CTO, CFO, Dev LeadDFS is naturally recursive (or uses an explicit stack); BFS uses a queue. This pattern reappears for graphs.
Measuring Height and Size
def height(node):
if not node.children:
return 0
return 1 + max(height(c) for c in node.children)
def count(node):
return 1 + sum(count(c) for c in node.children)
print(height(root)) # 2
print(count(root)) # 4Where Trees Are Used
- File systems (folders and files).
- The DOM in web pages and parsed source code (syntax trees).
- Decision trees in machine learning.
- Database indexes (B-trees), heaps, and tries.
Best Practices
- Recursion mirrors a tree's structure — but watch Python's recursion limit on deep trees.
- Use an explicit stack/queue to traverse very deep trees iteratively.
- The next lessons specialize to binary trees, BSTs, and balanced AVL trees.
Try It Yourself
Exercise 1: Which traversal uses a queue, and which naturally uses recursion?
Show solution
Breadth-first (level order) uses a queue; depth-first is naturally recursive (or an explicit stack).
Exercise 2: How does a tree differ from a general graph?
Show solution
A tree is a connected, acyclic graph with one root where every node (except the root) has exactly one parent. Graphs may have cycles and multiple parents.
📘 Real-World Deep Dive
Knowing <strong>DSA Trees (algorithms & data structures)</strong> well is what turns algorithms & data structures from a curiosity into a daily tool — you'll reach for it in nearly every real project.
Real-Life Scenario
An end-to-end usage of DSA Trees that you'd actually see in a data pipeline or analytics notebook.
Real-Life Example
def dfs(root):
yield root
if root.left: yield from dfs(root.left)
if root.right: yield from dfs(root.right)
# tree built with simple Node class
class N: __slots__=("v","l","r")
def __init__(self,v,l=None,r=None): self.v=v; self.l=l; self.r=r
t = N(1, N(2, N(4), N(5)), N(3, N(6), N(7)))
print([n.v for n in dfs(t)])Expected Output
(see source)Common mistakes
- Off-by-one errors in binary-search: the standard idiom is
while lo <= hiwithmid = (lo + hi) // 2. - Recursive algorithms blow the stack for n > ~10⁴; convert to iterative with an explicit stack.
- Comparison algorithms (
sorted(iterable)) are stable by default in Python — surprising for Java/C++ users. - Treating DSA Trees as a black box without reading the docs — the API has subtle defaults that bite when you scale.
🚀 Performance & Best Practices
- Use
bisect.bisect_left/bisect_rightinstead of writing your own binary search. - Convert a sorted search into a tuple-access pattern with
numpy.searchsortedfor huge arrays. - Use
heapqfor priority queues instead of maintaining a sorted list manually. - When working with algorithms & data structures, prefer vectorised / batched operations over Python loops.
🧪 Try It Yourself
- Reproduce the snippet on a representative slice of your own data.
- Profile the snippet with
cProfileortimeitand find the single biggest improvement. - Generalise the snippet into a small, reusable function you can drop into future projects.