Tree Basics
DSA · Trees
Theory
A tree is a hierarchical structure of nodes connected by edges, with one root node and no cycles. Each node can have children; nodes without children are leaves. Key terms are parent, child, sibling, depth (distance from the root), height (longest path down to a leaf) and subtree. Any tree with n nodes has exactly n-1 edges.
Why we use it
Many real things are hierarchical: folders, organisation charts, HTML documents, categories. Trees also give O(log n) searching when balanced.
When to use it
Use trees for hierarchies, sorted data with fast insert/search (BSTs), prefix lookups (tries), priority queues (heaps), and decision making.
How it works
- Root node
- Each node has children (0 or more)
- Nodes without children are leaves
- Depth = edges from root; height = longest path down
- A connected acyclic hierarchy
Syntax
class TreeNode:
def __init__(self, val):
self.val = val
self.children = []
Root: no parent Leaf: no children
Height(leaf) = 0 Height(node) = 1 + max(child heights)Example
class TreeNode:
def __init__(self, name):
self.name = name
self.children = []
def show(node, depth=0):
print(" " * depth + "- " + node.name)
for c in node.children:
show(c, depth + 1)
def height(node):
if not node.children:
return 0
return 1 + max(height(c) for c in node.children)
root = TreeNode("CEO")
cto, cfo = TreeNode("CTO"), TreeNode("CFO")
root.children = [cto, cfo]
cto.children = [TreeNode("Data Lead"), TreeNode("Dev Lead")]
cto.children[0].children = [TreeNode("Analyst")]
show(root)
print("Height:", height(root))Key points
- One root, no cycles
- n nodes means n-1 edges
- Depth counts down from the root; height counts up from leaves
- Most tree algorithms are recursive