This blog is about trees
2025-3-22
"The best time to plant a tree was 20 years ago. The second best time is now."
Understanding Binary Trees in Computer Science
Binary trees are fundamental data structures in computer science that form the backbone of many algorithms and applications. Unlike their biological counterparts, these digital trees grow downward, with their roots at the top and branches extending below.
What Is a Binary Tree?
A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and the right child. This simple constraint creates a powerful organizational framework that enables efficient data storage, retrieval, and manipulation.
The structure begins with a root node at the top and branches out below. Nodes with no children are called leaf nodes, marking the endpoints of the tree's paths.
Basic Implementation in Python
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
With this simple class, we can create a binary tree structure:
# Create a simple binary tree
# 10
# / \
# 5 15
# / \ / \
# 3 7 12 18
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.left = TreeNode(12)
root.right.right = TreeNode(18)
Key Binary Tree Types
Binary Search Trees (BST)
Binary search trees maintain a specific ordering property: for any node, all elements in its left subtree have values less than the node's value, and all elements in its right subtree have values greater than the node's value. This ordering enables efficient searching, insertion, and deletion operations, typically with O(log n) time complexity in balanced trees.
50
/ \
30 70
/ \ / \
20 40 60 80
BST Implementation in JavaScript
class BSTNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new BSTNode(value);
if (!this.root) {
this.root = newNode;
return this;
}
let current = this.root;
while (true) {
if (value === current.value) return undefined;
if (value < current.value) {
if (!current.left) {
current.left = newNode;
return this;
}
current = current.left;
} else {
if (!current.right) {
current.right = newNode;
return this;
}
current = current.right;
}
}
}
search(value) {
if (!this.root) return false;
let current = this.root;
while (current) {
if (value === current.value) return true;
current = value < current.value ? current.left : current.right;
}
return false;
}
}
// Usage
const bst = new BinarySearchTree();
bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(40);
bst.insert(60);
bst.insert(80);
console.log(bst.search(40)); // true
console.log(bst.search(90)); // false
AVL Trees
Named after their inventors (Adelson-Velsky and Landis), AVL trees are self-balancing binary search trees. They maintain balance by ensuring the height difference between left and right subtrees of any node never exceeds one. When this balance is violated after an insertion or deletion, the tree performs rotations to restore balance.
AVL Tree Rotations in Java
class AVLNode {
int value;
int height;
AVLNode left, right;
AVLNode(int value) {
this.value = value;
this.height = 1;
}
}
class AVLTree {
AVLNode root;
// Get height of node
int height(AVLNode node) {
if (node == null) return 0;
return node.height;
}
// Get balance factor
int getBalance(AVLNode node) {
if (node == null) return 0;
return height(node.left) - height(node.right);
}
// Right rotation
AVLNode rightRotate(AVLNode y) {
AVLNode x = y.left;
AVLNode T2 = x.right;
// Perform rotation
x.right = y;
y.left = T2;
// Update heights
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
// Return new root
return x;
}
// Left rotation
AVLNode leftRotate(AVLNode x) {
AVLNode y = x.right;
AVLNode T2 = y.left;
// Perform rotation
y.left = x;
x.right = T2;
// Update heights
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
// Return new root
return y;
}
}
Red-Black Trees
Red-black trees use color properties and specific rules to maintain balance. Each node is colored either red or black, with constraints ensuring no path from the root to a leaf is more than twice as long as any other path. These trees provide efficient worst-case guarantees for search, insert, and delete operations.
Complete Binary Trees
In a complete binary tree, all levels are fully filled except possibly the last level, which is filled from left to right. This property makes complete binary trees ideal for array implementations, as used in binary heaps.
Binary Heap Implementation in Python
class MinHeap:
def __init__(self):
self.heap = []
def parent(self, i):
return (i - 1) // 2
def left_child(self, i):
return 2 * i + 1
def right_child(self, i):
return 2 * i + 2
def insert(self, value):
self.heap.append(value)
self._sift_up(len(self.heap) - 1)
def extract_min(self):
if not self.heap:
return None
min_value = self.heap[0]
last_value = self.heap.pop()
if self.heap:
self.heap[0] = last_value
self._sift_down(0)
return min_value
def _sift_up(self, i):
parent = self.parent(i)
if i > 0 and self.heap[parent] > self.heap[i]:
self.heap[parent], self.heap[i] = self.heap[i], self.heap[parent]
self._sift_up(parent)
def _sift_down(self, i):
min_index = i
left = self.left_child(i)
right = self.right_child(i)
if left < len(self.heap) and self.heap[left] < self.heap[min_index]:
min_index = left
if right < len(self.heap) and self.heap[right] < self.heap[min_index]:
min_index = right
if i != min_index:
self.heap[i], self.heap[min_index] = self.heap[min_index], self.heap[i]
self._sift_down(min_index)
Full Binary Trees
A full binary tree (sometimes called a proper binary tree) is one in which every node has either 0 or 2 children—no node has exactly one child.
Tree Traversals
Trees can be traversed in several ways, each providing a different order of node visits:
def in_order_traversal(node):
if node:
in_order_traversal(node.left)
print(node.value, end=" ")
in_order_traversal(node.right)
def pre_order_traversal(node):
if node:
print(node.value, end=" ")
pre_order_traversal(node.left)
pre_order_traversal(node.right)
def post_order_traversal(node):
if node:
post_order_traversal(node.left)
post_order_traversal(node.right)
print(node.value, end=" ")
def level_order_traversal(root):
if not root:
return
queue = [root]
while queue:
node = queue.pop(0)
print(node.value, end=" ")
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
Applications of Binary Trees
Binary trees power numerous computer applications:
- Database indexing: B-trees and their variants optimize data access in databases
- Expression evaluation: Binary expression trees represent and evaluate arithmetic expressions
- Huffman coding: Used for data compression
- Priority queues: Implemented efficiently using binary heaps
- Routing algorithms: Specialized binary trees help route network traffic
Binary Trees in the Wild
The concept of binary trees extends beyond computer science. Decision trees in machine learning, game trees in artificial intelligence, and even organizational hierarchies all utilize tree-like structures to model relationships and decision paths.
Problem Solving with Binary Trees
Let's solve a classic problem: determining if a binary tree is balanced.
def is_balanced(root):
"""
Check if a binary tree is height-balanced:
A height-balanced tree is defined as a tree in which
the height of the left and right subtrees of any node
differ by no more than 1.
"""
def check_height(node):
if not node:
return 0
left_height = check_height(node.left)
if left_height == -1:
return -1
right_height = check_height(node.right)
if right_height == -1:
return -1
if abs(left_height - right_height) > 1:
return -1
return max(left_height, right_height) + 1
return check_height(root) != -1