Binary Trees
Introduction to tree data structure, terminology, and properties. Learn about nodes, edges, height, depth, and tree traversal.
Trees are hierarchical data structures that model relationships like file systems, organization charts, and decision processes. Binary trees, where each node has at most two children, are the foundation for many important data structures.
What is a Binary Tree?
A binary tree is a tree where each node has:
- A value (data)
- At most two children: left and right
1 <- root
/ \
2 3 <- children of 1
/ \ \
4 5 6 <- leaves (no children)
/
7
Terminology
| Term | Definition | |------|------------| | Root | The topmost node (1 in example) | | Parent | Node with children (1 is parent of 2, 3) | | Child | Node connected below (2, 3 are children of 1) | | Leaf | Node with no children (5, 6, 7) | | Height | Longest path from root to leaf | | Depth | Distance from root to a node | | Level | All nodes at same depth | | Subtree | A node and all its descendants |
Height and Depth:
1 <- depth 0, height 3
/ \
2 3 <- depth 1
/ \ \
4 5 6 <- depth 2
/
7 <- depth 3 (leaf)
Tree height = 3 (longest path: 1 → 2 → 4 → 7)
Node Implementation
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
struct TreeNode {
val: i32,
left: Option<Box<TreeNode>>,
right: Option<Box<TreeNode>>,
}
Building a Tree
# Create the tree from the diagram
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
root.left.left.left = TreeNode(7)
Types of Binary Trees
Full Binary Tree
Every node has 0 or 2 children:
1
/ \
2 3
/ \
4 5
Complete Binary Tree
All levels filled except possibly the last, which is filled left to right:
1
/ \
2 3
/ \ /
4 5 6
Perfect Binary Tree
All internal nodes have 2 children, all leaves at same level:
1
/ \
2 3
/ \ / \
4 5 6 7
Balanced Binary Tree
Height difference of left and right subtrees ≤ 1 for all nodes.
Why Tree Types Matter
Complete and balanced trees guarantee O(log n) height, enabling efficient operations. Skewed trees degrade to O(n) height, making them equivalent to linked lists.
Properties
For a binary tree with n nodes:
- Minimum height: ⌊log₂(n)⌋ (when balanced/complete)
- Maximum height: n - 1 (when completely skewed)
- Maximum nodes at level k: 2^k
- Maximum total nodes with height h: 2^(h+1) - 1
Balanced tree (n=7, height=2): Skewed tree (n=7, height=6):
1 1
/ \ \
2 3 2
/ \ / \ \
4 5 6 7 3
\
4
\
5
\
6
\
7
Basic Operations
Calculate Height
def height(root):
if root is None:
return -1 # Empty tree has height -1
left_height = height(root.left)
right_height = height(root.right)
return 1 + max(left_height, right_height)
Count Nodes
def count_nodes(root):
if root is None:
return 0
return 1 + count_nodes(root.left) + count_nodes(root.right)
Find Maximum Value
def find_max(root):
if root is None:
return float('-inf')
left_max = find_max(root.left)
right_max = find_max(root.right)
return max(root.val, left_max, right_max)
Check if Value Exists
def contains(root, target):
if root is None:
return False
if root.val == target:
return True
return contains(root.left, target) or contains(root.right, target)
Tree Representation Formats
Array Representation (Complete Trees)
For a complete binary tree, store in array by level:
1
/ \
2 3
/ \ / \
4 5 6 7
Array: [1, 2, 3, 4, 5, 6, 7]
Index: 0 1 2 3 4 5 6
For node at index i:
- Left child: 2*i + 1
- Right child: 2*i + 2
- Parent: (i - 1) // 2
def left_child(i):
return 2 * i + 1
def right_child(i):
return 2 * i + 2
def parent(i):
return (i - 1) // 2
Space Waste
Array representation wastes space for non-complete trees. For a skewed tree of 7 nodes, you'd need an array of 127 elements (2^7 - 1). Use linked representation for sparse trees.
From Array to Tree
def build_tree_from_array(arr, i=0):
if i >= len(arr) or arr[i] is None:
return None
root = TreeNode(arr[i])
root.left = build_tree_from_array(arr, 2 * i + 1)
root.right = build_tree_from_array(arr, 2 * i + 2)
return root
arr = [1, 2, 3, 4, 5, None, 6]
root = build_tree_from_array(arr)
Common Patterns
Mirror/Invert a Tree
def invert_tree(root):
if root is None:
return None
# Swap children
root.left, root.right = root.right, root.left
# Recursively invert subtrees
invert_tree(root.left)
invert_tree(root.right)
return root
Check if Trees are Identical
def is_same_tree(p, q):
if p is None and q is None:
return True
if p is None or q is None:
return False
if p.val != q.val:
return False
return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)
Check if Symmetric
def is_symmetric(root):
def is_mirror(left, right):
if left is None and right is None:
return True
if left is None or right is None:
return False
return (left.val == right.val and
is_mirror(left.left, right.right) and
is_mirror(left.right, right.left))
return root is None or is_mirror(root.left, root.right)
Applications of Binary Trees
- Binary Search Trees: Ordered data for fast lookup
- Heaps: Priority queues
- Expression Trees: Mathematical expressions
- Huffman Trees: Data compression
- Decision Trees: Machine learning
- File Systems: Directory structures
Key Takeaways
- Binary trees have at most 2 children per node
- Key terms: root, leaf, height, depth, balanced
- Complete/balanced trees give O(log n) height
- Skewed trees degrade to O(n) height
- Array representation works well for complete trees
- Most tree algorithms are naturally recursive
- Foundation for BSTs, heaps, and many other structures
Binary trees are the building block for many advanced data structures. Understanding their structure and properties prepares you for binary search trees, heaps, and tree-based algorithms.