Trees in Python
A tree is a hierarchical data structure made of nodes connected by edges. Trees represent parent-child relationships and are used heavily in searching, parsing, databases, and hierarchical storage.
Key advantages:
- Represent hierarchy naturally
- Many problems become easier with recursion
- Balanced trees provide fast operations: O(log n)
- Root: top-most node
- Edge: connection between nodes
- Parent: a node that has children
- Child: node that comes from a parent
- Leaf: node with no children
- Sibling: nodes with same parent
- Depth: distance from root to node (edges count)
- Height: max distance from node to leaf
- Subtree: any node + all its descendants
A binary tree is a tree where each node has at most two children: left and right.
Types of Binary Trees
- Full: every node has 0 or 2 children
- Complete: filled level by level (left to right)
- Perfect: all internal nodes have 2 children and all leaves same level
- Balanced: height stays about log(n)
Node Class
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
Example Tree Construction
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
Tree shape:
1
/ \
2 3
/ \
4 5
Traversal means visiting all nodes systematically.
In-order Traversal (Left, Root, Right)
- Used in BST to get sorted order.
def inorder(root):
if root:
inorder(root.left)
print(root.data, end=" ")
inorder(root.right)
Pre-order Traversal (Root, Left, Right)
- Used for copying tree, prefix expressions.
def preorder(root):
if root:
print(root.data, end=" ")
preorder(root.left)
preorder(root.right)
Post-order Traversal (Left, Right, Root)
- Used for deleting/freeing tree, postfix expressions.
def postorder(root):
if root:
postorder(root.left)
postorder(root.right)
print(root.data, end=" ")
Level-order Traversal (BFS)
- Visits nodes level by level using a queue.
from collections import deque
def level_order(root):
if not root:
return
q = deque([root])
while q:
node = q.popleft()
print(node.data, end=" ")
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
A BST is a binary tree with ordering:
- Left subtree values < node value
- Right subtree values > node value
This enables average O(log n) search/insert/delete (if balanced).
Insertion in BST (O(h))
def insert(root, value):
if root is None:
return TreeNode(value)
if value < root.data:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
Searching in BST (O(h))
def search_bst(root, value):
if root is None or root.data == value:
return root
if value < root.data:
return search_bst(root.left, value)
return search_bst(root.right, value)
Deletion in BST (O(h))
Deletion cases:
- Leaf node → remove directly
- One child → replace node with child
- Two children → replace with inorder successor (min in right subtree)
def min_value_node(node):
current = node
while current.left:
current = current.left
return current
def delete(root, key):
if not root:
return root
if key < root.data:
root.left = delete(root.left, key)
elif key > root.data:
root.right = delete(root.right, key)
else:
if root.left is None:
return root.right
if root.right is None:
return root.left
temp = min_value_node(root.right)
root.data = temp.data
root.right = delete(root.right, temp.data)
return root
AVL trees keep BST height balanced using rotations so performance stays O(log n).
Common rotations
- Left rotation
- Right rotation
- Left-right rotation
- Right-left rotation
Why needed: A normal BST can become skewed (like a linked list) if inserted in sorted order.
- File systems (folders/subfolders)
- Databases (B-Trees/B+ Trees)
- Autocomplete (Trie trees)
- Parsing expressions (syntax trees)
- Routing / decision making (decision trees)
Trees represent hierarchical data and power many efficient algorithms. Binary trees teach recursion and traversals. BSTs add ordering for faster search, and AVL trees maintain balance for consistent performance.