Trees
What is a Tree?
A tree is a hierarchical data structure consisting of nodes connected by edges. Unlike linear data structures (Arrays, LinkedLists, Queues, Stacks), which have a sequential relationship between elements, trees represent a parent-child relationship between nodes.
A
B
C
D
E
F
Key Characteristics
- Hierarchical Structure: Nodes are organized in a parent-child relationship
- Root: The topmost node in a tree, with no parent
- No Cycles: Each node (except the root) has exactly one parent, and there are no cycles
- Connected: There is exactly one path between any two nodes
- Non-Linear: Data doesn't follow a sequential order, allowing for more complex relationships
Real-world Applications
- File Systems: Directories and files in operating systems
- Organization Charts: Hierarchical management structures
- DOM: Document Object Model in web browsers
- Database Indexing: B-trees and B+ trees for efficient search
- Network Routing: Routing algorithms often use tree-based structures
- Syntax Trees: Used in compilers for code parsing
- Decision Trees: In machine learning for classification
Types of Trees
1. Binary Tree At most 2 children
A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.
10
5
15
3
7
12
18
2. Binary Search Tree (BST) Ordered binary tree
A binary search tree is a binary tree with the property that for any node, all elements in its left subtree are less than the node's value, and all elements in its right subtree are greater.
8
3
10
1
6
14
NULL
3. AVL Tree Self-balancing BST
An AVL tree is a self-balancing binary search tree where the difference between heights of left and right subtrees cannot be more than one for all nodes.
10
5
15
2
7
12
20
4. Red-Black Tree Self-balancing BST
A Red-Black tree is a type of self-balancing binary search tree where each node has an extra bit for denoting the color of the node, either red or black.
10
5
15
3
7
12
20
5. B-Tree M-way search tree
A B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. It is commonly used in databases and file systems.
20, 40, 60
10, 15
30, 35
50, 55
70, 80
6. Heap Tree Complete binary tree
A heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C.
100
80
90
50
70
60
40
7. Trie (Prefix Tree) Character-based tree
A trie is a tree-like data structure whose nodes store the letters of an alphabet. Used for efficient retrieval of keys in a dataset of strings, especially useful for dictionary implementations.
*
t
b
o
e
a
p
a
t
Choice of Tree Type: The selection of the appropriate tree structure depends on your specific use case. Each tree type has its own advantages and trade-offs in terms of operation efficiency, memory usage, and implementation complexity.
| Tree Type | Best Use Cases | Time Complexity (Average) | Space Complexity |
|---|---|---|---|
| Binary Tree | Basic hierarchical structures | O(n) for search, insert, delete | O(n) |
| Binary Search Tree | Ordered data, efficient searching | O(log n) for balanced trees, O(n) worst case | O(n) |
| AVL Tree | Frequent searches, infrequent updates | O(log n) for all operations | O(n) |
| Red-Black Tree | Frequent insertions/deletions | O(log n) for all operations | O(n) |
| B-Tree | Databases, file systems | O(log n) for all operations | O(n) |
| Heap | Priority queues, scheduling | O(1) for find-max/min, O(log n) for insert/delete | O(n) |
| Trie | Dictionary, prefix searches | O(k) where k is key length | O(n*k) where n is number of keys |
Tree Terminology
Understanding the terminology associated with trees is crucial for effectively working with these data structures.
A
B
C
D
E
F
G
Basic Tree Concepts
- Node: An entity that contains a value or data and pointers to its child nodes.
- Root: The topmost node of a tree, with no parent.
- Edge: The connection link between two nodes.
- Parent: A node that has one or more child nodes.
- Child: A node that has a parent node.
- Leaf Node: A node with no children.
- Siblings: Nodes that have the same parent.
- Ancestor: Any predecessor node on the path from root to a node.
- Descendant: Any successor node on the path from a node to a leaf node.
Tree Structure Properties
- Depth of a Node: The length of the path from the root to the node (number of edges).
- Height of a Node: The length of the longest path from the node to a leaf.
- Height of a Tree: The height of the root node, or the depth of the deepest node.
- Degree of a Node: The number of children a node has.
- Degree of a Tree: The maximum degree of any node in the tree.
- Level of a Node: The depth of the node plus one.
- Size of a Tree: The total number of nodes in the tree.
Binary Tree Specific Terms
- Left Child: The child node that is on the left side of its parent.
- Right Child: The child node that is on the right side of its parent.
- Full Binary Tree: A binary tree in which every node has either 0 or 2 children.
- Complete Binary Tree: A binary tree in which all levels are completely filled except possibly the last level, which is filled from left to right.
- Perfect Binary Tree: A binary tree in which all internal nodes have two children and all leaf nodes are at the same level.
- Balanced Binary Tree: A binary tree in which the height of the left and right subtrees of any node differ by no more than 1.
- Degenerate (or Pathological) Tree: A tree where each parent node has only one child node, effectively becoming a linked list.
Common Terminology Confusion: Be careful not to confuse depth and height. Depth is measured from the root down, while height is measured from the bottom up. Also, remember that levels are 1-indexed (root is at level 1), while depth is 0-indexed (root has depth 0).
Tree Operations Complexity
| Operation | Binary Tree | Balanced BST | AVL Tree | Red-Black Tree | B-Tree |
|---|---|---|---|---|---|
| Access/Search | O(n) | O(log n) | O(log n) | O(log n) | O(log n) |
| Insert | O(n) | O(log n) | O(log n) | O(log n) | O(log n) |
| Delete | O(n) | O(log n) | O(log n) | O(log n) | O(log n) |
| Space | O(n) | O(n) | O(n) | O(n) | O(n) |
Optimization Tip: The actual performance of tree operations greatly depends on the tree's balance. An unbalanced BST can degrade to O(n) performance, behaving like a linked list. This is why self-balancing trees like AVL and Red-Black trees are important for maintaining reliable performance.
Breakdown of Factors Affecting Tree Performance
- Tree Height: The height of a tree is the main factor in determining the time complexity of most operations. A balanced tree has a height of approximately log(n), while an unbalanced tree can have a height approaching n.
- Balancing Overhead: Self-balancing trees like AVL and Red-Black trees maintain their logarithmic performance by rebalancing after modifications, which adds overhead but ensures consistent performance.
- Node Comparison Cost: For trees storing complex objects, the cost of key comparisons can be significant.
- Memory Access Patterns: Trees can suffer from poor cache locality due to their non-contiguous memory layout, which can affect performance on modern hardware.
Comparing Trees vs Other Data Structures
| Feature | Tree | Array | Linked List | Hash Table |
|---|---|---|---|---|
| Search | O(log n) for balanced | O(n) unsorted O(log n) sorted binary search |
O(n) | O(1) average |
| Insert | O(log n) for balanced | O(n) (might require shifting) | O(1) with reference | O(1) average |
| Delete | O(log n) for balanced | O(n) (might require shifting) | O(1) with reference | O(1) average |
| Ordered Traversal | O(n) in-order for BST | O(n) | O(n) | Not Supported Naturally |
Tree Traversal O(n)
Tree traversal is the process of visiting each node in a tree exactly once. Different traversal methods yield different orderings of the tree nodes.
F
B
G
A
D
NULL
I
NULL
NULL
C
E
NULL
H
Depth-First Traversals
Depth-first traversals explore as far as possible along each branch before backtracking.
Pre-order Traversal Root → Left → Right
In pre-order traversal, the root node is visited first, then the left subtree, and finally the right subtree.
// Recursive pre-order traversal
public void preOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
// Visit the root
System.out.print(root.val + " ");
// Traverse left subtree
preOrderTraversal(root.left);
// Traverse right subtree
preOrderTraversal(root.right);
}
// Iterative pre-order traversal using stack
public void preOrderIterative(TreeNode root) {
if (root == null) {
return;
}
Stack stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
// Pop the top node from stack and print it
TreeNode current = stack.pop();
System.out.print(current.val + " ");
// Push right child first so that left is processed first
if (current.right != null) {
stack.push(current.right);
}
if (current.left != null) {
stack.push(current.left);
}
}
}
# Recursive pre-order traversal
def pre_order_traversal(root):
if root is None:
return
# Visit the root
print(root.val, end=" ")
# Traverse left subtree
pre_order_traversal(root.left)
# Traverse right subtree
pre_order_traversal(root.right)
# Iterative pre-order traversal using stack
def pre_order_iterative(root):
if root is None:
return
stack = [root]
while stack:
# Pop the top node from stack and print it
current = stack.pop()
print(current.val, end=" ")
# Push right child first so that left is processed first
if current.right:
stack.append(current.right)
if current.left:
stack.append(current.left)
// Recursive pre-order traversal
function preOrderTraversal(root) {
if (root === null) {
return;
}
// Visit the root
console.log(root.val);
// Traverse left subtree
preOrderTraversal(root.left);
// Traverse right subtree
preOrderTraversal(root.right);
}
// Iterative pre-order traversal using stack
function preOrderIterative(root) {
if (root === null) {
return;
}
const stack = [root];
while (stack.length > 0) {
// Pop the top node from stack and print it
const current = stack.pop();
console.log(current.val);
// Push right child first so that left is processed first
if (current.right !== null) {
stack.push(current.right);
}
if (current.left !== null) {
stack.push(current.left);
}
}
}
Use Cases: Pre-order traversal is useful for creating a copy of the tree or for getting a prefix expression from an expression tree.
In-order Traversal Left → Root → Right
In in-order traversal, the left subtree is visited first, then the root node, and finally the right subtree.
// Recursive in-order traversal
public void inOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
// Traverse left subtree
inOrderTraversal(root.left);
// Visit the root
System.out.print(root.val + " ");
// Traverse right subtree
inOrderTraversal(root.right);
}
// Iterative in-order traversal using stack
public void inOrderIterative(TreeNode root) {
if (root == null) {
return;
}
Stack stack = new Stack<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
// Reach the leftmost node of the current node
while (current != null) {
stack.push(current);
current = current.left;
}
// Current is now null, pop an element from stack
current = stack.pop();
// Print the node value
System.out.print(current.val + " ");
// Move to the right subtree
current = current.right;
}
}
# Recursive in-order traversal
def in_order_traversal(root):
if root is None:
return
# Traverse left subtree
in_order_traversal(root.left)
# Visit the root
print(root.val, end=" ")
# Traverse right subtree
in_order_traversal(root.right)
# Iterative in-order traversal using stack
def in_order_iterative(root):
if root is None:
return
stack = []
current = root
while current is not None or stack:
# Reach the leftmost node of the current node
while current is not None:
stack.append(current)
current = current.left
# Current is now None, pop an element from stack
current = stack.pop()
# Print the node value
print(current.val, end=" ")
# Move to the right subtree
current = current.right
// Recursive in-order traversal
function inOrderTraversal(root) {
if (root === null) {
return;
}
// Traverse left subtree
inOrderTraversal(root.left);
// Visit the root
console.log(root.val);
// Traverse right subtree
inOrderTraversal(root.right);
}
// Iterative in-order traversal using stack
function inOrderIterative(root) {
if (root === null) {
return;
}
const stack = [];
let current = root;
while (current !== null || stack.length > 0) {
// Reach the leftmost node of the current node
while (current !== null) {
stack.push(current);
current = current.left;
}
// Current is now null, pop an element from stack
current = stack.pop();
// Print the node value
console.log(current.val);
// Move to the right subtree
current = current.right;
}
}
Use Cases: In-order traversal gives nodes in non-decreasing order in a BST and is commonly used for sorting operations.
Post-order Traversal Left → Right → Root
In post-order traversal, the left subtree is visited first, then the right subtree, and finally the root node.
// Recursive post-order traversal
public void postOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
// Traverse left subtree
postOrderTraversal(root.left);
// Traverse right subtree
postOrderTraversal(root.right);
// Visit the root
System.out.print(root.val + " ");
}
// Iterative post-order traversal using two stacks
public void postOrderIterative(TreeNode root) {
if (root == null) {
return;
}
Stack stack1 = new Stack<>();
Stack stack2 = new Stack<>();
// Push root to first stack
stack1.push(root);
// Run while first stack is not empty
while (!stack1.isEmpty()) {
// Pop an item from stack1 and push it to stack2
TreeNode current = stack1.pop();
stack2.push(current);
// Push left and right children of removed item to stack1
if (current.left != null) {
stack1.push(current.left);
}
if (current.right != null) {
stack1.push(current.right);
}
}
// Print all elements of second stack
while (!stack2.isEmpty()) {
TreeNode node = stack2.pop();
System.out.print(node.val + " ");
}
}
# Recursive post-order traversal
def post_order_traversal(root):
if root is None:
return
# Traverse left subtree
post_order_traversal(root.left)
# Traverse right subtree
post_order_traversal(root.right)
# Visit the root
print(root.val, end=" ")
# Iterative post-order traversal using two stacks
def post_order_iterative(root):
if root is None:
return
stack1 = [root]
stack2 = []
# Run while first stack is not empty
while stack1:
# Pop an item from stack1 and push it to stack2
current = stack1.pop()
stack2.append(current)
# Push left and right children of removed item to stack1
if current.left:
stack1.append(current.left)
if current.right:
stack1.append(current.right)
# Print all elements of second stack
while stack2:
node = stack2.pop()
print(node.val, end=" ")
// Recursive post-order traversal
function postOrderTraversal(root) {
if (root === null) {
return;
}
// Traverse left subtree
postOrderTraversal(root.left);
// Traverse right subtree
postOrderTraversal(root.right);
// Visit the root
console.log(root.val);
}
// Iterative post-order traversal using two stacks
function postOrderIterative(root) {
if (root === null) {
return;
}
const stack1 = [root];
const stack2 = [];
// Run while first stack is not empty
while (stack1.length > 0) {
// Pop an item from stack1 and push it to stack2
const current = stack1.pop();
stack2.push(current);
// Push left and right children of removed item to stack1
if (current.left !== null) {
stack1.push(current.left);
}
if (current.right !== null) {
stack1.push(current.right);
}
}
// Print all elements of second stack
while (stack2.length > 0) {
const node = stack2.pop();
console.log(node.val);
}
}
Use Cases: Post-order traversal is used when deleting a tree (to delete child nodes before parent nodes) and for generating postfix notation of an expression tree.
Breadth-First Traversal
Level-order Traversal Time: O(n) | Space: O(n)
Level-order traversal visits nodes level by level from top to bottom and left to right. It uses a queue data structure for the implementation.
// Level-order traversal using queue
public void levelOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
Queue queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
// Remove the head of queue and print it
TreeNode current = queue.poll();
System.out.print(current.val + " ");
// Add left child to queue if it exists
if (current.left != null) {
queue.add(current.left);
}
// Add right child to queue if it exists
if (current.right != null) {
queue.add(current.right);
}
}
}
// Level-order traversal with level information
public List> levelOrderWithLevels(TreeNode root) {
List> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List currentLevel = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode current = queue.poll();
currentLevel.add(current.val);
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
}
result.add(currentLevel);
}
return result;
}
# Level-order traversal using queue
def level_order_traversal(root):
if root is None:
return
queue = [root]
while queue:
# Remove the head of queue and print it
current = queue.pop(0)
print(current.val, end=" ")
# Add left child to queue if it exists
if current.left:
queue.append(current.left)
# Add right child to queue if it exists
if current.right:
queue.append(current.right)
# Level-order traversal with level information
def level_order_with_levels(root):
if root is None:
return []
result = []
queue = [root]
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
current = queue.pop(0)
current_level.append(current.val)
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
result.append(current_level)
return result
// Level-order traversal using queue
function levelOrderTraversal(root) {
if (root === null) {
return;
}
const queue = [root];
while (queue.length > 0) {
// Remove the head of queue and print it
const current = queue.shift();
console.log(current.val);
// Add left child to queue if it exists
if (current.left !== null) {
queue.push(current.left);
}
// Add right child to queue if it exists
if (current.right !== null) {
queue.push(current.right);
}
}
}
// Level-order traversal with level information
function levelOrderWithLevels(root) {
if (root === null) {
return [];
}
const result = [];
const queue = [root];
while (queue.length > 0) {
const levelSize = queue.length;
const currentLevel = [];
for (let i = 0; i < levelSize; i++) {
const current = queue.shift();
currentLevel.push(current.val);
if (current.left !== null) {
queue.push(current.left);
}
if (current.right !== null) {
queue.push(current.right);
}
}
result.push(currentLevel);
}
return result;
}
Stack vs Queue: Depth-first traversals (pre-order, in-order, post-order) typically use a stack (explicit for iterative, implicit for recursive), while breadth-first traversal (level-order) uses a queue. Remember that recursive implementations have function call stack overhead.
Insertion Operations
Insertion operations add new nodes to a tree while maintaining the appropriate tree structure and properties.
10
5
15
3
7
13
NULL
Binary Search Tree Insertion O(log n) for balanced | O(n) worst case
Insertion in a BST involves finding the appropriate position to add a new node while maintaining the BST property (left child < parent < right child).
// Tree Node definition
class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
// Recursive insertion in BST
public TreeNode insert(TreeNode root, int val) {
// If the tree is empty, create a new node and return it
if (root == null) {
return new TreeNode(val);
}
// Otherwise, recur down the tree
if (val < root.val) {
// Insert in the left subtree
root.left = insert(root.left, val);
} else if (val > root.val) {
// Insert in the right subtree
root.right = insert(root.right, val);
}
// Duplicate values are not inserted (BST property)
// Return the unchanged node pointer
return root;
}
// Iterative insertion in BST
public TreeNode insertIterative(TreeNode root, int val) {
// Create new node
TreeNode newNode = new TreeNode(val);
// If the tree is empty, return the new node as root
if (root == null) {
return newNode;
}
// Start with the root and find the position to insert
TreeNode current = root;
TreeNode parent = null;
while (true) {
parent = current;
if (val < current.val) {
// Move to the left subtree
current = current.left;
// If reached a leaf node, insert as left child
if (current == null) {
parent.left = newNode;
return root;
}
} else if (val > current.val) {
// Move to the right subtree
current = current.right;
// If reached a leaf node, insert as right child
if (current == null) {
parent.right = newNode;
return root;
}
} else {
// Duplicate value, do nothing and return
return root;
}
}
}
# Tree Node definition
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Recursive insertion in BST
def insert(root, val):
# If the tree is empty, create a new node and return it
if root is None:
return TreeNode(val)
# Otherwise, recur down the tree
if val < root.val:
# Insert in the left subtree
root.left = insert(root.left, val)
elif val > root.val:
# Insert in the right subtree
root.right = insert(root.right, val)
# Duplicate values are not inserted (BST property)
# Return the unchanged node pointer
return root
# Iterative insertion in BST
def insert_iterative(root, val):
# Create new node
new_node = TreeNode(val)
# If the tree is empty, return the new node as root
if root is None:
return new_node
# Start with the root and find the position to insert
current = root
parent = None
while True:
parent = current
if val < current.val:
# Move to the left subtree
current = current.left
# If reached a leaf node, insert as left child
if current is None:
parent.left = new_node
return root
elif val > current.val:
# Move to the right subtree
current = current.right
# If reached a leaf node, insert as right child
if current is None:
parent.right = new_node
return root
else:
# Duplicate value, do nothing and return
return root
// Tree Node definition
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
// Recursive insertion in BST
function insert(root, val) {
// If the tree is empty, create a new node and return it
if (root === null) {
return new TreeNode(val);
}
// Otherwise, recur down the tree
if (val < root.val) {
// Insert in the left subtree
root.left = insert(root.left, val);
} else if (val > root.val) {
// Insert in the right subtree
root.right = insert(root.right, val);
}
// Duplicate values are not inserted (BST property)
// Return the unchanged node pointer
return root;
}
// Iterative insertion in BST
function insertIterative(root, val) {
// Create new node
const newNode = new TreeNode(val);
// If the tree is empty, return the new node as root
if (root === null) {
return newNode;
}
// Start with the root and find the position to insert
let current = root;
let parent = null;
while (true) {
parent = current;
if (val < current.val) {
// Move to the left subtree
current = current.left;
// If reached a leaf node, insert as left child
if (current === null) {
parent.left = newNode;
return root;
}
} else if (val > current.val) {
// Move to the right subtree
current = current.right;
// If reached a leaf node, insert as right child
if (current === null) {
parent.right = newNode;
return root;
}
} else {
// Duplicate value, do nothing and return
return root;
}
}
}
AVL Tree Insertion O(log n)
AVL tree insertion involves standard BST insertion followed by rebalancing operations to maintain the AVL property (balance factor of every node is -1, 0, or 1).
Balancing After Insertion: After inserting a node into an AVL tree, we need to update the heights of the ancestors and check if any node's balance factor has been violated. If so, we perform rotations to rebalance the tree.
Different Tree Types Insertion Comparison
| Tree Type | Insertion Process | Time Complexity | Balancing Required |
|---|---|---|---|
| Binary Tree | Can be inserted anywhere (no specific order) | O(1) with reference to insertion point | No |
| Binary Search Tree | Must maintain order property | O(log n) average, O(n) worst | No |
| AVL Tree | BST insertion + balancing | O(log n) | Yes (rotations) |
| Red-Black Tree | BST insertion + color adjustments | O(log n) | Yes (rotations + recoloring) |
| B-Tree | Complex, involves key placement and potential splitting | O(log n) | Yes (splitting nodes) |
Deletion Operations
Deletion operations remove nodes from a tree while maintaining the appropriate tree structure and properties.
10
5
15
3
7
13
17
Binary Search Tree Deletion O(log n) for balanced | O(n) worst case
Deletion in a BST is more complex than insertion as it involves three different cases based on the number of children of the node to be deleted.
Case 1: Deleting a Node with No Children
When the node to be deleted is a leaf node (has no children), we simply remove it by updating its parent's reference to null.
// This is part of the complete deletion method shown below
// For a leaf node, we simply set the parent's
// pointer to the node to null.
if (current.left == null && current.right == null) {
// If the node is the root, set the root to null
if (current == root) {
return null;
}
// Set the parent's pointer to null
if (isLeftChild) {
parent.left = null;
} else {
parent.right = null;
}
return root;
}
# For a leaf node, we simply set the parent's
# pointer to the node to null.
if current.left is None and current.right is None:
# If the node is the root, set the root to null
if current == root:
return None
# Set the parent's pointer to null
if is_left_child:
parent.left = None
else:
parent.right = None
return root
// For a leaf node, we simply set the parent's
// pointer to the node to null.
if (current.left === null && current.right === null) {
// If the node is the root, set the root to null
if (current === root) {
return null;
}
// Set the parent's pointer to null
if (isLeftChild) {
parent.left = null;
} else {
parent.right = null;
}
return root;
}
Case 2: Deleting a Node with One Child
When the node to be deleted has only one child, we bypass the node by connecting its parent directly to its child.
// If the node has only left child
if (current.right == null) {
// If the node is the root, make the left child the new root
if (current == root) {
return current.left;
}
// Connect parent to the left child
if (isLeftChild) {
parent.left = current.left;
} else {
parent.right = current.left;
}
return root;
}
// If the node has only right child
if (current.left == null) {
// If the node is the root, make the right child the new root
if (current == root) {
return current.right;
}
// Connect parent to the right child
if (isLeftChild) {
parent.left = current.right;
} else {
parent.right = current.right;
}
return root;
}
# If the node has only left child
if current.right is None:
# If the node is the root, make the left child the new root
if current == root:
return current.left
# Connect parent to the left child
if is_left_child:
parent.left = current.left
else:
parent.right = current.left
return root
# If the node has only right child
if current.left is None:
# If the node is the root, make the right child the new root
if current == root:
return current.right
# Connect parent to the right child
if is_left_child:
parent.left = current.right
else:
parent.right = current.right
return root
// If the node has only left child
if (current.right === null) {
// If the node is the root, make the left child the new root
if (current === root) {
return current.left;
}
// Connect parent to the left child
if (isLeftChild) {
parent.left = current.left;
} else {
parent.right = current.left;
}
return root;
}
// If the node has only right child
if (current.left === null) {
// If the node is the root, make the right child the new root
if (current === root) {
return current.right;
}
// Connect parent to the right child
if (isLeftChild) {
parent.left = current.right;
} else {
parent.right = current.right;
}
return root;
}
Case 3: Deleting a Node with Two Children
When the node to be deleted has two children, we typically find the inorder successor (or inorder predecessor) to replace the node, then delete the successor (or predecessor).
// Node has two children
// First, find the inorder successor (smallest node in right subtree)
TreeNode successorParent = current;
TreeNode successor = current.right;
while (successor.left != null) {
successorParent = successor;
successor = successor.left;
}
// If the successor is not the direct right child, handle its right subtree
if (successorParent != current) {
successorParent.left = successor.right;
successor.right = current.right;
}
// Replace the current node with the successor
if (current == root) {
successor.left = current.left;
return successor;
}
if (isLeftChild) {
parent.left = successor;
} else {
parent.right = successor;
}
// Connect the successor to the current node's left subtree
// if successor was not the direct right child
if (successorParent != current) {
successor.left = current.left;
}
return root;
# Node has two children
# First, find the inorder successor (smallest node in right subtree)
successor_parent = current
successor = current.right
while successor.left is not None:
successor_parent = successor
successor = successor.left
# If the successor is not the direct right child, handle its right subtree
if successor_parent != current:
successor_parent.left = successor.right
successor.right = current.right
# Replace the current node with the successor
if current == root:
successor.left = current.left
return successor
if is_left_child:
parent.left = successor
else:
parent.right = successor
# Connect the successor to the current node's left subtree
# if successor was not the direct right child
if successor_parent != current:
successor.left = current.left
return root
// Node has two children
// First, find the inorder successor (smallest node in right subtree)
let successorParent = current;
let successor = current.right;
while (successor.left !== null) {
successorParent = successor;
successor = successor.left;
}
// If the successor is not the direct right child, handle its right subtree
if (successorParent !== current) {
successorParent.left = successor.right;
successor.right = current.right;
}
// Replace the current node with the successor
if (current === root) {
successor.left = current.left;
return successor;
}
if (isLeftChild) {
parent.left = successor;
} else {
parent.right = successor;
}
// Connect the successor to the current node's left subtree
// if successor was not the direct right child
if (successorParent !== current) {
successor.left = current.left;
}
return root;
Complete BST Deletion Implementation
// Delete a node from BST
public TreeNode delete(TreeNode root, int key) {
if (root == null) {
return null;
}
// Search for the node to delete
TreeNode parent = null;
TreeNode current = root;
boolean isLeftChild = false;
while (current != null && current.val != key) {
parent = current;
if (key < current.val) {
current = current.left;
isLeftChild = true;
} else {
current = current.right;
isLeftChild = false;
}
}
// If the node was not found
if (current == null) {
return root;
}
// Case 1: Node with no children (leaf node)
if (current.left == null && current.right == null) {
if (current == root) {
return null; // The tree becomes empty
}
if (isLeftChild) {
parent.left = null;
} else {
parent.right = null;
}
}
// Case 2: Node with one child
// If the node has only a left child
else if (current.right == null) {
if (current == root) {
return current.left; // The left child becomes the new root
}
if (isLeftChild) {
parent.left = current.left;
} else {
parent.right = current.left;
}
}
// If the node has only a right child
else if (current.left == null) {
if (current == root) {
return current.right; // The right child becomes the new root
}
if (isLeftChild) {
parent.left = current.right;
} else {
parent.right = current.right;
}
}
// Case 3: Node with two children
else {
// Find the inorder successor (smallest node in right subtree)
TreeNode successorParent = current;
TreeNode successor = current.right;
while (successor.left != null) {
successorParent = successor;
successor = successor.left;
}
// If the successor is not the direct right child, handle its right subtree
if (successorParent != current) {
successorParent.left = successor.right;
successor.right = current.right;
}
// Replace the current node with the successor
if (current == root) {
successor.left = current.left;
return successor; // The successor becomes the new root
}
if (isLeftChild) {
parent.left = successor;
} else {
parent.right = successor;
}
// Connect the successor to the current node's left subtree
if (successorParent != current) {
successor.left = current.left;
}
}
return root;
}
# Delete a node from BST
def delete(root, key):
if root is None:
return None
# Search for the node to delete
parent = None
current = root
is_left_child = False
while current is not None and current.val != key:
parent = current
if key < current.val:
current = current.left
is_left_child = True
else:
current = current.right
is_left_child = False
# If the node was not found
if current is None:
return root
# Case 1: Node with no children (leaf node)
if current.left is None and current.right is None:
if current == root:
return None # The tree becomes empty
if is_left_child:
parent.left = None
else:
parent.right = None
# Case 2: Node with one child
# If the node has only a left child
elif current.right is None:
if current == root:
return current.left # The left child becomes the new root
if is_left_child:
parent.left = current.left
else:
parent.right = current.left
# If the node has only a right child
elif current.left is None:
if current == root:
return current.right # The right child becomes the new root
if is_left_child:
parent.left = current.right
else:
parent.right = current.right
# Case 3: Node with two children
else:
# Find the inorder successor (smallest node in right subtree)
successor_parent = current
successor = current.right
while successor.left is not None:
successor_parent = successor
successor = successor.left
# If the successor is not the direct right child, handle its right subtree
if successor_parent != current:
successor_parent.left = successor.right
successor.right = current.right
# Replace the current node with the successor
if current == root:
successor.left = current.left
return successor # The successor becomes the new root
if is_left_child:
parent.left = successor
else:
parent.right = successor
# Connect the successor to the current node's left subtree
if successor_parent != current:
successor.left = current.left
return root
// Delete a node from BST
function deleteNode(root, key) {
if (root === null) {
return null;
}
// Search for the node to delete
let parent = null;
let current = root;
let isLeftChild = false;
while (current !== null && current.val !== key) {
parent = current;
if (key < current.val) {
current = current.left;
isLeftChild = true;
} else {
current = current.right;
isLeftChild = false;
}
}
// If the node was not found
if (current === null) {
return root;
}
// Case 1: Node with no children (leaf node)
if (current.left === null && current.right === null) {
if (current === root) {
return null; // The tree becomes empty
}
if (isLeftChild) {
parent.left = null;
} else {
parent.right = null;
}
}
// Case 2: Node with one child
// If the node has only a left child
else if (current.right === null) {
if (current === root) {
return current.left; // The left child becomes the new root
}
if (isLeftChild) {
parent.left = current.left;
} else {
parent.right = current.left;
}
}
// If the node has only a right child
else if (current.left === null) {
if (current === root) {
return current.right; // The right child becomes the new root
}
if (isLeftChild) {
parent.left = current.right;
} else {
parent.right = current.right;
}
}
// Case 3: Node with two children
else {
// Find the inorder successor (smallest node in right subtree)
let successorParent = current;
let successor = current.right;
while (successor.left !== null) {
successorParent = successor;
successor = successor.left;
}
// If the successor is not the direct right child, handle its right subtree
if (successorParent !== current) {
successorParent.left = successor.right;
successor.right = current.right;
}
// Replace the current node with the successor
if (current === root) {
successor.left = current.left;
return successor; // The successor becomes the new root
}
if (isLeftChild) {
parent.left = successor;
} else {
parent.right = successor;
}
// Connect the successor to the current node's left subtree
if (successorParent !== current) {
successor.left = current.left;
}
}
return root;
}
Node Deletion in Self-Balancing Trees: For AVL and Red-Black trees, deletion follows a similar process as BST but requires additional balancing operations after deletion to maintain the tree's balance properties.
Searching in Trees
Efficient search operations are one of the primary advantages of tree data structures, especially for ordered trees like BSTs.
10
5
15
3
7
13
17
Binary Search Tree Search O(log n) for balanced | O(n) worst case
Searching in a BST leverages the ordered property of the tree to efficiently find elements, similar to binary search on a sorted array.
// Recursive search in BST
public TreeNode search(TreeNode root, int key) {
// Base cases: root is null or the key is at root
if (root == null || root.val == key) {
return root;
}
// Key is greater than root's value, search in right subtree
if (root.val < key) {
return search(root.right, key);
}
// Key is smaller than root's value, search in left subtree
return search(root.left, key);
}
// Iterative search in BST
public TreeNode searchIterative(TreeNode root, int key) {
TreeNode current = root;
while (current != null) {
// If the key is found
if (current.val == key) {
return current;
}
// If key is greater than current's value, go to right subtree
if (current.val < key) {
current = current.right;
}
// If key is smaller than current's value, go to left subtree
else {
current = current.left;
}
}
// Key not found
return null;
}
# Recursive search in BST
def search(root, key):
# Base cases: root is null or the key is at root
if root is None or root.val == key:
return root
# Key is greater than root's value, search in right subtree
if root.val < key:
return search(root.right, key)
# Key is smaller than root's value, search in left subtree
return search(root.left, key)
# Iterative search in BST
def search_iterative(root, key):
current = root
while current is not None:
# If the key is found
if current.val == key:
return current
# If key is greater than current's value, go to right subtree
if current.val < key:
current = current.right
# If key is smaller than current's value, go to left subtree
else:
current = current.left
# Key not found
return None
// Recursive search in BST
function search(root, key) {
// Base cases: root is null or the key is at root
if (root === null || root.val === key) {
return root;
}
// Key is greater than root's value, search in right subtree
if (root.val < key) {
return search(root.right, key);
}
// Key is smaller than root's value, search in left subtree
return search(root.left, key);
}
// Iterative search in BST
function searchIterative(root, key) {
let current = root;
while (current !== null) {
// If the key is found
if (current.val === key) {
return current;
}
// If key is greater than current's value, go to right subtree
if (current.val < key) {
current = current.right;
}
// If key is smaller than current's value, go to left subtree
else {
current = current.left;
}
}
// Key not found
return null;
}
Finding Min and Max Values in BST O(log n) for balanced | O(n) worst case
In a BST, finding the minimum value means traversing left as far as possible, while finding the maximum means traversing right as far as possible.
// Find minimum value in BST
public TreeNode findMin(TreeNode root) {
if (root == null) {
return null;
}
// Keep going left until we reach a leaf
while (root.left != null) {
root = root.left;
}
return root;
}
// Find maximum value in BST
public TreeNode findMax(TreeNode root) {
if (root == null) {
return null;
}
// Keep going right until we reach a leaf
while (root.right != null) {
root = root.right;
}
return root;
}
# Find minimum value in BST
def find_min(root):
if root is None:
return None
# Keep going left until we reach a leaf
while root.left is not None:
root = root.left
return root
# Find maximum value in BST
def find_max(root):
if root is None:
return None
# Keep going right until we reach a leaf
while root.right is not None:
root = root.right
return root
// Find minimum value in BST
function findMin(root) {
if (root === null) {
return null;
}
// Keep going left until we reach a leaf
while (root.left !== null) {
root = root.left;
}
return root;
}
// Find maximum value in BST
function findMax(root) {
if (root === null) {
return null;
}
// Keep going right until we reach a leaf
while (root.right !== null) {
root = root.right;
}
return root;
}
Finding Successor and Predecessor in BST O(log n) for balanced | O(n) worst case
The inorder successor of a node is the node with the smallest key greater than the key of the given node. Similarly, the inorder predecessor is the node with the largest key smaller than the key of the given node.
Searching in Different Tree Types: The search operation's efficiency varies dramatically based on the tree type. While a degenerate BST might take O(n) time, balanced trees like AVL and Red-Black trees guarantee O(log n) search time. For non-ordered trees like general binary trees, a full traversal may be needed to find an element.
Depth-First Search (DFS) O(n)
Depth-First Search is an algorithm for traversing or searching tree or graph data structures that explores as far as possible along each branch before backtracking.
A
B
C
D
E
F
G
Recursive vs Iterative DFS
DFS can be implemented using either recursion or iteration with a stack. Each approach has its advantages and trade-offs.
Recursive DFS Implementation
The recursive implementation of DFS uses the function call stack to keep track of nodes to visit, making the code clean and intuitive.
// Recursive DFS implementation
public List dfsRecursive(TreeNode root) {
List result = new ArrayList<>();
dfsHelper(root, result);
return result;
}
private void dfsHelper(TreeNode node, List result) {
// Base case: if node is null, return
if (node == null) {
return;
}
// Process the current node (pre-order)
result.add(node.val);
// Recursively process left subtree
dfsHelper(node.left, result);
// Recursively process right subtree
dfsHelper(node.right, result);
}
// For in-order traversal, just change the order of operations:
private void inOrderDfsHelper(TreeNode node, List result) {
if (node == null) return;
inOrderDfsHelper(node.left, result);
result.add(node.val);
inOrderDfsHelper(node.right, result);
}
// For post-order traversal:
private void postOrderDfsHelper(TreeNode node, List result) {
if (node == null) return;
postOrderDfsHelper(node.left, result);
postOrderDfsHelper(node.right, result);
result.add(node.val);
}
# Recursive DFS implementation
def dfs_recursive(root):
result = []
dfs_helper(root, result)
return result
def dfs_helper(node, result):
# Base case: if node is null, return
if node is None:
return
# Process the current node (pre-order)
result.append(node.val)
# Recursively process left subtree
dfs_helper(node.left, result)
# Recursively process right subtree
dfs_helper(node.right, result)
# For in-order traversal, just change the order of operations:
def in_order_dfs_helper(node, result):
if node is None:
return
in_order_dfs_helper(node.left, result)
result.append(node.val)
in_order_dfs_helper(node.right, result)
# For post-order traversal:
def post_order_dfs_helper(node, result):
if node is None:
return
post_order_dfs_helper(node.left, result)
post_order_dfs_helper(node.right, result)
result.append(node.val)
// Recursive DFS implementation
function dfsRecursive(root) {
const result = [];
dfsHelper(root, result);
return result;
}
function dfsHelper(node, result) {
// Base case: if node is null, return
if (node === null) {
return;
}
// Process the current node (pre-order)
result.push(node.val);
// Recursively process left subtree
dfsHelper(node.left, result);
// Recursively process right subtree
dfsHelper(node.right, result);
}
// For in-order traversal, just change the order of operations:
function inOrderDfsHelper(node, result) {
if (node === null) return;
inOrderDfsHelper(node.left, result);
result.push(node.val);
inOrderDfsHelper(node.right, result);
}
// For post-order traversal:
function postOrderDfsHelper(node, result) {
if (node === null) return;
postOrderDfsHelper(node.left, result);
postOrderDfsHelper(node.right, result);
result.push(node.val);
}
Advantages of Recursive DFS: The recursive implementation is simple to understand and implement. It naturally follows the tree structure and is often the preferred approach for tree traversals.
Stack Overflow Risk: For very deep trees, the recursive approach might lead to a stack overflow error due to excessive function calls. In such cases, the iterative approach is preferred.
Iterative DFS Implementation
The iterative implementation of DFS uses an explicit stack data structure to keep track of nodes to visit, avoiding the function call overhead.
// Iterative DFS implementation (pre-order)
public List dfsIterative(TreeNode root) {
List result = new ArrayList<>();
if (root == null) {
return result;
}
Stack stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
// Pop a node from stack and add to result
TreeNode current = stack.pop();
result.add(current.val);
// Push right child first so that left is processed first
if (current.right != null) {
stack.push(current.right);
}
if (current.left != null) {
stack.push(current.left);
}
}
return result;
}
// Iterative in-order traversal
public List inOrderIterative(TreeNode root) {
List result = new ArrayList<>();
if (root == null) {
return result;
}
Stack stack = new Stack<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
// Reach the leftmost node
while (current != null) {
stack.push(current);
current = current.left;
}
// Current is now null, process the node at the top of the stack
current = stack.pop();
result.add(current.val);
// Move to the right subtree
current = current.right;
}
return result;
}
// Iterative post-order traversal (more complex, uses two stacks)
public List postOrderIterative(TreeNode root) {
List result = new ArrayList<>();
if (root == null) {
return result;
}
Stack stack1 = new Stack<>();
Stack stack2 = new Stack<>();
stack1.push(root);
// Fill stack2 with post-order traversal
while (!stack1.isEmpty()) {
TreeNode current = stack1.pop();
stack2.push(current);
if (current.left != null) {
stack1.push(current.left);
}
if (current.right != null) {
stack1.push(current.right);
}
}
// Pop from stack2 to get post-order traversal
while (!stack2.isEmpty()) {
result.add(stack2.pop().val);
}
return result;
}
# Iterative DFS implementation (pre-order)
def dfs_iterative(root):
result = []
if root is None:
return result
stack = [root]
while stack:
# Pop a node from stack and add to result
current = stack.pop()
result.append(current.val)
# Push right child first so that left is processed first
if current.right:
stack.append(current.right)
if current.left:
stack.append(current.left)
return result
# Iterative in-order traversal
def in_order_iterative(root):
result = []
if root is None:
return result
stack = []
current = root
while current or stack:
# Reach the leftmost node
while current:
stack.append(current)
current = current.left
# Current is now None, process the node at the top of the stack
current = stack.pop()
result.append(current.val)
# Move to the right subtree
current = current.right
return result
# Iterative post-order traversal (using two stacks)
def post_order_iterative(root):
result = []
if root is None:
return result
stack1 = [root]
stack2 = []
# Fill stack2 with post-order traversal
while stack1:
current = stack1.pop()
stack2.append(current)
if current.left:
stack1.append(current.left)
if current.right:
stack1.append(current.right)
# Pop from stack2 to get post-order traversal
while stack2:
result.append(stack2.pop().val)
return result
// Iterative DFS implementation (pre-order)
function dfsIterative(root) {
const result = [];
if (root === null) {
return result;
}
const stack = [root];
while (stack.length > 0) {
// Pop a node from stack and add to result
const current = stack.pop();
result.push(current.val);
// Push right child first so that left is processed first
if (current.right !== null) {
stack.push(current.right);
}
if (current.left !== null) {
stack.push(current.left);
}
}
return result;
}
// Iterative in-order traversal
function inOrderIterative(root) {
const result = [];
if (root === null) {
return result;
}
const stack = [];
let current = root;
while (current !== null || stack.length > 0) {
// Reach the leftmost node
while (current !== null) {
stack.push(current);
current = current.left;
}
// Current is now null, process the node at the top of the stack
current = stack.pop();
result.push(current.val);
// Move to the right subtree
current = current.right;
}
return result;
}
// Iterative post-order traversal (using two stacks)
function postOrderIterative(root) {
const result = [];
if (root === null) {
return result;
}
const stack1 = [root];
const stack2 = [];
// Fill stack2 with post-order traversal
while (stack1.length > 0) {
const current = stack1.pop();
stack2.push(current);
if (current.left !== null) {
stack1.push(current.left);
}
if (current.right !== null) {
stack1.push(current.right);
}
}
// Pop from stack2 to get post-order traversal
while (stack2.length > 0) {
result.push(stack2.pop().val);
}
return result;
}
Advantages of Iterative DFS: The iterative approach avoids potential stack overflow issues for deep trees. It also gives you more control over the traversal process, allowing you to pause, resume, or modify the traversal on the fly.
DFS Applications
- Topological Sorting: Finding a linear ordering of vertices in a directed acyclic graph.
- Pathfinding: Finding paths between nodes in a graph or tree.
- Solving Puzzles: Such as mazes or games like Chess, where exploring all possible moves is required.
- Connected Components: Finding connected components in a graph.
- Tree Operations: Used in tree operations like finding height, checking if a binary tree is a BST, etc.
Breadth-First Search (BFS) O(n)
Breadth-First Search is an algorithm for traversing or searching tree or graph data structures that explores all neighbor nodes at the present depth before moving on to nodes at the next depth level.
A
B
C
D
E
F
G
BFS Implementation Using Queue
BFS uses a queue data structure to keep track of nodes to visit, ensuring that we process nodes level by level.
// BFS implementation
public List bfs(TreeNode root) {
List result = new ArrayList<>();
if (root == null) {
return result;
}
Queue queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
result.add(current.val);
// Add left child to queue if exists
if (current.left != null) {
queue.add(current.left);
}
// Add right child to queue if exists
if (current.right != null) {
queue.add(current.right);
}
}
return result;
}
// Level-order traversal (BFS with level information)
public List> levelOrder(TreeNode root) {
List> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List currentLevel = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode current = queue.poll();
currentLevel.add(current.val);
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
}
result.add(currentLevel);
}
return result;
}
# BFS implementation
def bfs(root):
result = []
if root is None:
return result
queue = [root]
while queue:
current = queue.pop(0)
result.append(current.val)
# Add left child to queue if exists
if current.left:
queue.append(current.left)
# Add right child to queue if exists
if current.right:
queue.append(current.right)
return result
# Level-order traversal (BFS with level information)
def level_order(root):
result = []
if root is None:
return result
queue = [root]
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
current = queue.pop(0)
current_level.append(current.val)
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
result.append(current_level)
return result
// BFS implementation
function bfs(root) {
const result = [];
if (root === null) {
return result;
}
const queue = [root];
while (queue.length > 0) {
const current = queue.shift();
result.push(current.val);
// Add left child to queue if exists
if (current.left !== null) {
queue.push(current.left);
}
// Add right child to queue if exists
if (current.right !== null) {
queue.push(current.right);
}
}
return result;
}
// Level-order traversal (BFS with level information)
function levelOrder(root) {
const result = [];
if (root === null) {
return result;
}
const queue = [root];
while (queue.length > 0) {
const levelSize = queue.length;
const currentLevel = [];
for (let i = 0; i < levelSize; i++) {
const current = queue.shift();
currentLevel.push(current.val);
if (current.left !== null) {
queue.push(current.left);
}
if (current.right !== null) {
queue.push(current.right);
}
}
result.push(currentLevel);
}
return result;
}
BFS Applications
- Shortest Path: Finding the shortest path between two nodes in an unweighted graph.
- Level Order Traversal: Processing tree nodes level by level.
- Connected Components: Finding all connected components in an undirected graph.
- Bipartite Graph: Checking if a graph is bipartite.
- Clone a Graph: Creating a deep copy of a graph.
- Minimum Spanning Tree: Finding a minimum spanning tree in an unweighted graph.
BFS Memory Usage: BFS may require more memory than DFS because it needs to store all nodes of a level before going to the next level. For wide trees (trees with many nodes at each level), BFS can consume a significant amount of memory.
BFS vs DFS Comparison
| Feature | BFS | DFS |
|---|---|---|
| Data Structure | Queue | Stack (explicit or call stack) |
| Space Complexity | O(w) where w is the maximum width | O(h) where h is the height |
| Time Complexity | O(V + E) for graph, O(n) for tree | O(V + E) for graph, O(n) for tree |
| Traversal Order | Level by level (breadth-first) | Path by path (depth-first) |
| Completeness | Complete (finds all nodes at current distance) | May not be complete without backtracking |
| Best Use Cases | Shortest path, level order processing | Pathfinding, topological sorting, cycle detection |
Tree Balancing Algorithms
Balancing algorithms ensure that trees maintain optimal structure for efficient operations. Unbalanced trees can degrade to O(n) performance, while balanced trees guarantee O(log n) operations.
Basic Tree Rotations
Rotations are the fundamental operations used for balancing trees. They rearrange nodes while preserving the binary search tree property.
Left Rotation
A left rotation at node X makes its right child Y the new root of the subtree, with X becoming Y's left child and Y's left child becoming X's right child.
X
A
Y
B
C
Y
X
C
A
B
// Left rotation
TreeNode leftRotate(TreeNode x) {
TreeNode y = x.right; // y is right child of x
TreeNode T2 = y.left; // T2 is left child of y
// Perform rotation
y.left = x;
x.right = T2;
// Update heights (for AVL trees)
// 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;
}
# Left rotation
def left_rotate(x):
y = x.right # y is right child of x
T2 = y.left # T2 is left child of y
# Perform rotation
y.left = x
x.right = T2
# Update heights (for AVL trees)
# x.height = max(height(x.left), height(x.right)) + 1
# y.height = max(height(y.left), height(y.right)) + 1
# Return new root
return y
// Left rotation
function leftRotate(x) {
const y = x.right; // y is right child of x
const T2 = y.left; // T2 is left child of y
// Perform rotation
y.left = x;
x.right = T2;
// Update heights (for AVL trees)
// 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;
}
Right Rotation
A right rotation at node Y makes its left child X the new root of the subtree, with Y becoming X's right child and X's right child becoming Y's left child.
Y
X
C
A
B
X
A
Y
B
C
// Right rotation
TreeNode rightRotate(TreeNode y) {
TreeNode x = y.left; // x is left child of y
TreeNode T2 = x.right; // T2 is right child of x
// Perform rotation
x.right = y;
y.left = T2;
// Update heights (for AVL trees)
// 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;
}
# Right rotation
def right_rotate(y):
x = y.left # x is left child of y
T2 = x.right # T2 is right child of x
# Perform rotation
x.right = y
y.left = T2
# Update heights (for AVL trees)
# y.height = max(height(y.left), height(y.right)) + 1
# x.height = max(height(x.left), height(x.right)) + 1
# Return new root
return x
// Right rotation
function rightRotate(y) {
const x = y.left; // x is left child of y
const T2 = x.right; // T2 is right child of x
// Perform rotation
x.right = y;
y.left = T2;
// Update heights (for AVL trees)
// 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-Right (LR) Rotation
A Left-Right rotation is a combination of a left rotation followed by a right rotation. It's used when an imbalance occurs on the right of the left child of a node.
Z
X
Y
Y
X
Z
// Left-Right rotation
TreeNode leftRightRotate(TreeNode z) {
// First left rotation on left child
z.left = leftRotate(z.left);
// Then right rotation on root
return rightRotate(z);
}
# Left-Right rotation
def left_right_rotate(z):
# First left rotation on left child
z.left = left_rotate(z.left)
# Then right rotation on root
return right_rotate(z)
// Left-Right rotation
function leftRightRotate(z) {
// First left rotation on left child
z.left = leftRotate(z.left);
// Then right rotation on root
return rightRotate(z);
}
Right-Left (RL) Rotation
A Right-Left rotation is a combination of a right rotation followed by a left rotation. It's used when an imbalance occurs on the left of the right child of a node.
X
Z
Y
Y
X
Z
// Right-Left rotation
TreeNode rightLeftRotate(TreeNode x) {
// First right rotation on right child
x.right = rightRotate(x.right);
// Then left rotation on root
return leftRotate(x);
}
# Right-Left rotation
def right_left_rotate(x):
# First right rotation on right child
x.right = right_rotate(x.right)
# Then left rotation on root
return left_rotate(x)
// Right-Left rotation
function rightLeftRotate(x) {
// First right rotation on right child
x.right = rightRotate(x.right);
// Then left rotation on root
return leftRotate(x);
}
AVL Tree Balancing Balance Factor = Height(Left) - Height(Right)
AVL trees maintain balance by ensuring that for every node, the difference between the heights of left and right subtrees is at most 1.
// AVL Tree node
class AVLNode {
int val;
AVLNode left;
AVLNode right;
int height; // Height of the node
public AVLNode(int val) {
this.val = val;
this.height = 1; // Leaf nodes have height 1
}
}
// Get height of a node
int height(AVLNode node) {
if (node == null) {
return 0;
}
return node.height;
}
// Get balance factor of a node
int getBalance(AVLNode node) {
if (node == null) {
return 0;
}
return height(node.left) - height(node.right);
}
// Insertion in AVL Tree
AVLNode insert(AVLNode node, int val) {
// Standard BST insertion
if (node == null) {
return new AVLNode(val);
}
if (val < node.val) {
node.left = insert(node.left, val);
} else if (val > node.val) {
node.right = insert(node.right, val);
} else {
// Duplicate values are not allowed
return node;
}
// Update height of this ancestor node
node.height = 1 + Math.max(height(node.left), height(node.right));
// Get the balance factor to check if this node became unbalanced
int balance = getBalance(node);
// Left Left Case
if (balance > 1 && val < node.left.val) {
return rightRotate(node);
}
// Right Right Case
if (balance < -1 && val > node.right.val) {
return leftRotate(node);
}
// Left Right Case
if (balance > 1 && val > node.left.val) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && val < node.right.val) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
// No imbalance, return the unchanged node
return node;
}
# AVL Tree node
class AVLNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.height = 1 # Leaf nodes have height 1
# Get height of a node
def height(node):
if node is None:
return 0
return node.height
# Get balance factor of a node
def get_balance(node):
if node is None:
return 0
return height(node.left) - height(node.right)
# Insertion in AVL Tree
def insert(node, val):
# Standard BST insertion
if node is None:
return AVLNode(val)
if val < node.val:
node.left = insert(node.left, val)
elif val > node.val:
node.right = insert(node.right, val)
else:
# Duplicate values are not allowed
return node
# Update height of this ancestor node
node.height = 1 + max(height(node.left), height(node.right))
# Get the balance factor to check if this node became unbalanced
balance = get_balance(node)
# Left Left Case
if balance > 1 and val < node.left.val:
return right_rotate(node)
# Right Right Case
if balance < -1 and val > node.right.val:
return left_rotate(node)
# Left Right Case
if balance > 1 and val > node.left.val:
node.left = left_rotate(node.left)
return right_rotate(node)
# Right Left Case
if balance < -1 and val < node.right.val:
node.right = right_rotate(node.right)
return left_rotate(node)
# No imbalance, return the unchanged node
return node
// AVL Tree node
class AVLNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
this.height = 1; // Leaf nodes have height 1
}
}
// Get height of a node
function height(node) {
if (node === null) {
return 0;
}
return node.height;
}
// Get balance factor of a node
function getBalance(node) {
if (node === null) {
return 0;
}
return height(node.left) - height(node.right);
}
// Insertion in AVL Tree
function insert(node, val) {
// Standard BST insertion
if (node === null) {
return new AVLNode(val);
}
if (val < node.val) {
node.left = insert(node.left, val);
} else if (val > node.val) {
node.right = insert(node.right, val);
} else {
// Duplicate values are not allowed
return node;
}
// Update height of this ancestor node
node.height = 1 + Math.max(height(node.left), height(node.right));
// Get the balance factor to check if this node became unbalanced
const balance = getBalance(node);
// Left Left Case
if (balance > 1 && val < node.left.val) {
return rightRotate(node);
}
// Right Right Case
if (balance < -1 && val > node.right.val) {
return leftRotate(node);
}
// Left Right Case
if (balance > 1 && val > node.left.val) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && val < node.right.val) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
// No imbalance, return the unchanged node
return node;
}
Red-Black Tree Balancing
Red-Black trees maintain balance by enforcing a set of properties, using node coloring and rotations to ensure that no path from root to leaf is more than twice as long as any other.
Balancing Trade-offs: While AVL trees maintain stricter balance, Red-Black trees provide more efficient insertion and deletion at the cost of potentially less optimal search performance. The choice between them depends on the frequency of different operations in your use case.
Common Tree Algorithms
Beyond the basic operations, several algorithms are commonly used for solving tree-related problems.
Lowest Common Ancestor (LCA) O(h) where h is height
The lowest common ancestor of two nodes p and q in a tree is the deepest node that has both p and q as descendants.
// Find LCA in a Binary Search Tree
TreeNode findLCAInBST(TreeNode root, TreeNode p, TreeNode q) {
// Base case
if (root == null) {
return null;
}
// If both p and q are smaller than root, LCA must be in left subtree
if (p.val < root.val && q.val < root.val) {
return findLCAInBST(root.left, p, q);
}
// If both p and q are greater than root, LCA must be in right subtree
if (p.val > root.val && q.val > root.val) {
return findLCAInBST(root.right, p, q);
}
// Otherwise, current node is the LCA (one node in left subtree, one in right,
// or one of the nodes is the current node)
return root;
}
// Find LCA in a Binary Tree
TreeNode findLCA(TreeNode root, TreeNode p, TreeNode q) {
// Base case
if (root == null || root == p || root == q) {
return root;
}
// Look for keys in left and right subtrees
TreeNode left = findLCA(root.left, p, q);
TreeNode right = findLCA(root.right, p, q);
// If both of the above calls return non-NULL, then one key is present in
// the left subtree and the other in right subtree, so current node is the LCA
if (left != null && right != null) {
return root;
}
// Otherwise check if left subtree or right subtree is LCA
return (left != null) ? left : right;
}
# Find LCA in a Binary Search Tree
def find_lca_in_bst(root, p, q):
# Base case
if root is None:
return None
# If both p and q are smaller than root, LCA must be in left subtree
if p.val < root.val and q.val < root.val:
return find_lca_in_bst(root.left, p, q)
# If both p and q are greater than root, LCA must be in right subtree
if p.val > root.val and q.val > root.val:
return find_lca_in_bst(root.right, p, q)
# Otherwise, current node is the LCA (one node in left subtree, one in right,
# or one of the nodes is the current node)
return root
# Find LCA in a Binary Tree
def find_lca(root, p, q):
# Base case
if root is None or root == p or root == q:
return root
# Look for keys in left and right subtrees
left = find_lca(root.left, p, q)
right = find_lca(root.right, p, q)
# If both of the above calls return non-None, then one key is present in
# the left subtree and the other in right subtree, so current node is the LCA
if left is not None and right is not None:
return root
# Otherwise check if left subtree or right subtree is LCA
return left if left is not None else right
// Find LCA in a Binary Search Tree
function findLCAInBST(root, p, q) {
// Base case
if (root === null) {
return null;
}
// If both p and q are smaller than root, LCA must be in left subtree
if (p.val < root.val && q.val < root.val) {
return findLCAInBST(root.left, p, q);
}
// If both p and q are greater than root, LCA must be in right subtree
if (p.val > root.val && q.val > root.val) {
return findLCAInBST(root.right, p, q);
}
// Otherwise, current node is the LCA (one node in left subtree, one in right,
// or one of the nodes is the current node)
return root;
}
// Find LCA in a Binary Tree
function findLCA(root, p, q) {
// Base case
if (root === null || root === p || root === q) {
return root;
}
// Look for keys in left and right subtrees
const left = findLCA(root.left, p, q);
const right = findLCA(root.right, p, q);
// If both of the above calls return non-null, then one key is present in
// the left subtree and the other in right subtree, so current node is the LCA
if (left !== null && right !== null) {
return root;
}
// Otherwise check if left subtree or right subtree is LCA
return (left !== null) ? left : right;
}
Path Finding Between Nodes O(n)
Finding a path between two nodes involves traversing the tree from one node to another.
// Find path from root to a node
boolean findPath(TreeNode root, TreeNode target, List path) {
// Base case
if (root == null) {
return false;
}
// Add current node to path
path.add(root);
// If current node is the target, return true
if (root == target) {
return true;
}
// Check if target is in left or right subtree
if (findPath(root.left, target, path) || findPath(root.right, target, path)) {
return true;
}
// If target not in subtrees, remove current node and return false
path.remove(path.size() - 1);
return false;
}
// Find path between two nodes
List findPathBetweenNodes(TreeNode root, TreeNode p, TreeNode q) {
// Find LCA of the two nodes
TreeNode lca = findLCA(root, p, q);
// Find path from LCA to p
List pathToP = new ArrayList<>();
findPath(lca, p, pathToP);
// Find path from LCA to q
List pathToQ = new ArrayList<>();
findPath(lca, q, pathToQ);
// Combine paths: reverse path to p (excluding LCA) + LCA + path to q (excluding LCA)
List result = new ArrayList<>();
for (int i = pathToP.size() - 1; i > 0; i--) {
result.add(pathToP.get(i));
}
result.add(lca);
for (int i = 1; i < pathToQ.size(); i++) {
result.add(pathToQ.get(i));
}
return result;
}
# Find path from root to a node
def find_path(root, target, path):
# Base case
if root is None:
return False
# Add current node to path
path.append(root)
# If current node is the target, return True
if root == target:
return True
# Check if target is in left or right subtree
if find_path(root.left, target, path) or find_path(root.right, target, path):
return True
# If target not in subtrees, remove current node and return False
path.pop()
return False
# Find path between two nodes
def find_path_between_nodes(root, p, q):
# Find LCA of the two nodes
lca = find_lca(root, p, q)
# Find path from LCA to p
path_to_p = []
find_path(lca, p, path_to_p)
# Find path from LCA to q
path_to_q = []
find_path(lca, q, path_to_q)
# Combine paths: reverse path to p (excluding LCA) + LCA + path to q (excluding LCA)
result = []
for node in path_to_p[-1:0:-1]:
result.append(node)
result.append(lca)
for node in path_to_q[1:]:
result.append(node)
return result
// Find path from root to a node
function findPath(root, target, path) {
// Base case
if (root === null) {
return false;
}
// Add current node to path
path.push(root);
// If current node is the target, return true
if (root === target) {
return true;
}
// Check if target is in left or right subtree
if (findPath(root.left, target, path) || findPath(root.right, target, path)) {
return true;
}
// If target not in subtrees, remove current node and return false
path.pop();
return false;
}
// Find path between two nodes
function findPathBetweenNodes(root, p, q) {
// Find LCA of the two nodes
const lca = findLCA(root, p, q);
// Find path from LCA to p
const pathToP = [];
findPath(lca, p, pathToP);
// Find path from LCA to q
const pathToQ = [];
findPath(lca, q, pathToQ);
// Combine paths: reverse path to p (excluding LCA) + LCA + path to q (excluding LCA)
const result = [];
for (let i = pathToP.length - 1; i > 0; i--) {
result.push(pathToP[i]);
}
result.push(lca);
for (let i = 1; i < pathToQ.length; i++) {
result.push(pathToQ[i]);
}
return result;
}
Tree Height and Depth Calculation O(n)
Calculating the height or depth of a tree is a fundamental operation for many tree algorithms.
// Calculate height of a tree (maximum depth)
int height(TreeNode root) {
// Base case: empty tree has height 0
if (root == null) {
return 0;
}
// Recursively calculate height of left and right subtrees
int leftHeight = height(root.left);
int rightHeight = height(root.right);
// Return height of the taller subtree + 1 (for current node)
return Math.max(leftHeight, rightHeight) + 1;
}
// Calculate depth of a specific node
int findDepth(TreeNode root, TreeNode node, int depth) {
// Base case
if (root == null) {
return -1; // Node not found
}
// If the target node is found
if (root == node) {
return depth;
}
// Check in left subtree
int leftDepth = findDepth(root.left, node, depth + 1);
if (leftDepth != -1) {
return leftDepth;
}
// If not in left subtree, check in right subtree
return findDepth(root.right, node, depth + 1);
}
# Calculate height of a tree (maximum depth)
def height(root):
# Base case: empty tree has height 0
if root is None:
return 0
# Recursively calculate height of left and right subtrees
left_height = height(root.left)
right_height = height(root.right)
# Return height of the taller subtree + 1 (for current node)
return max(left_height, right_height) + 1
# Calculate depth of a specific node
def find_depth(root, node, depth=0):
# Base case
if root is None:
return -1 # Node not found
# If the target node is found
if root == node:
return depth
# Check in left subtree
left_depth = find_depth(root.left, node, depth + 1)
if left_depth != -1:
return left_depth
# If not in left subtree, check in right subtree
return find_depth(root.right, node, depth + 1)
// Calculate height of a tree (maximum depth)
function height(root) {
// Base case: empty tree has height 0
if (root === null) {
return 0;
}
// Recursively calculate height of left and right subtrees
const leftHeight = height(root.left);
const rightHeight = height(root.right);
// Return height of the taller subtree + 1 (for current node)
return Math.max(leftHeight, rightHeight) + 1;
}
// Calculate depth of a specific node
function findDepth(root, node, depth = 0) {
// Base case
if (root === null) {
return -1; // Node not found
}
// If the target node is found
if (root === node) {
return depth;
}
// Check in left subtree
const leftDepth = findDepth(root.left, node, depth + 1);
if (leftDepth !== -1) {
return leftDepth;
}
// If not in left subtree, check in right subtree
return findDepth(root.right, node, depth + 1);
}
Check if a Binary Tree is a BST O(n)
Verifying if a binary tree satisfies the Binary Search Tree property (left subtree values < node value < right subtree values).
// Check if a binary tree is a BST
boolean isBST(TreeNode root) {
return isBSTUtil(root, null, null);
}
// Utility function to check if a tree is BST
boolean isBSTUtil(TreeNode node, Integer min, Integer max) {
// Base case: empty tree is a BST
if (node == null) {
return true;
}
// Check if current node's value is within valid range
if ((min != null && node.val <= min) ||
(max != null && node.val >= max)) {
return false;
}
// Recursively check left and right subtrees
// Left subtree values must be < node.val
// Right subtree values must be > node.val
return isBSTUtil(node.left, min, node.val) &&
isBSTUtil(node.right, node.val, max);
}
// Alternative approach using inorder traversal
boolean isBSTInorder(TreeNode root) {
List inorderList = new ArrayList<>();
inorderTraversal(root, inorderList);
// Check if the list is sorted in ascending order
for (int i = 1; i < inorderList.size(); i++) {
if (inorderList.get(i) <= inorderList.get(i - 1)) {
return false;
}
}
return true;
}
// Helper function for inorder traversal
void inorderTraversal(TreeNode node, List result) {
if (node == null) {
return;
}
inorderTraversal(node.left, result);
result.add(node.val);
inorderTraversal(node.right, result);
}
# Check if a binary tree is a BST
def is_bst(root):
return is_bst_util(root, None, None)
# Utility function to check if a tree is BST
def is_bst_util(node, min_val, max_val):
# Base case: empty tree is a BST
if node is None:
return True
# Check if current node's value is within valid range
if ((min_val is not None and node.val <= min_val) or
(max_val is not None and node.val >= max_val)):
return False
# Recursively check left and right subtrees
# Left subtree values must be < node.val
# Right subtree values must be > node.val
return (is_bst_util(node.left, min_val, node.val) and
is_bst_util(node.right, node.val, max_val))
# Alternative approach using inorder traversal
def is_bst_inorder(root):
inorder_list = []
inorder_traversal(root, inorder_list)
# Check if the list is sorted in ascending order
for i in range(1, len(inorder_list)):
if inorder_list[i] <= inorder_list[i - 1]:
return False
return True
# Helper function for inorder traversal
def inorder_traversal(node, result):
if node is None:
return
inorder_traversal(node.left, result)
result.append(node.val)
inorder_traversal(node.right, result)
// Check if a binary tree is a BST
function isBST(root) {
return isBSTUtil(root, null, null);
}
// Utility function to check if a tree is BST
function isBSTUtil(node, min, max) {
// Base case: empty tree is a BST
if (node === null) {
return true;
}
// Check if current node's value is within valid range
if ((min !== null && node.val <= min) ||
(max !== null && node.val >= max)) {
return false;
}
// Recursively check left and right subtrees
// Left subtree values must be < node.val
// Right subtree values must be > node.val
return isBSTUtil(node.left, min, node.val) &&
isBSTUtil(node.right, node.val, max);
}
// Alternative approach using inorder traversal
function isBSTInorder(root) {
const inorderList = [];
inorderTraversal(root, inorderList);
// Check if the list is sorted in ascending order
for (let i = 1; i < inorderList.length; i++) {
if (inorderList[i] <= inorderList[i - 1]) {
return false;
}
}
return true;
}
// Helper function for inorder traversal
function inorderTraversal(node, result) {
if (node === null) {
return;
}
inorderTraversal(node.left, result);
result.push(node.val);
inorderTraversal(node.right, result);
}
Serialize and Deserialize Trees O(n)
Converting a tree to a string representation (serialization) and reconstructing the tree from that representation (deserialization).
// Serialize a binary tree to a string
String serialize(TreeNode root) {
if (root == null) {
return "null,";
}
// Use preorder traversal (root, left, right)
StringBuilder sb = new StringBuilder();
sb.append(root.val).append(",");
sb.append(serialize(root.left));
sb.append(serialize(root.right));
return sb.toString();
}
// Deserialize a string to a binary tree
TreeNode deserialize(String data) {
String[] nodes = data.split(",");
List nodesList = new LinkedList<>(Arrays.asList(nodes));
return deserializeHelper(nodesList);
}
// Helper function for deserialization
TreeNode deserializeHelper(List nodes) {
String val = nodes.remove(0);
if (val.equals("null")) {
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(val));
root.left = deserializeHelper(nodes);
root.right = deserializeHelper(nodes);
return root;
}
# Serialize a binary tree to a string
def serialize(root):
if root is None:
return "null,"
# Use preorder traversal (root, left, right)
result = str(root.val) + ","
result += serialize(root.left)
result += serialize(root.right)
return result
# Deserialize a string to a binary tree
def deserialize(data):
nodes = data.split(",")
return deserialize_helper(nodes)
# Helper function for deserialization
def deserialize_helper(nodes):
val = nodes.pop(0)
if val == "null":
return None
root = TreeNode(int(val))
root.left = deserialize_helper(nodes)
root.right = deserialize_helper(nodes)
return root
// Serialize a binary tree to a string
function serialize(root) {
if (root === null) {
return "null,";
}
// Use preorder traversal (root, left, right)
let result = root.val + ",";
result += serialize(root.left);
result += serialize(root.right);
return result;
}
// Deserialize a string to a binary tree
function deserialize(data) {
const nodes = data.split(",");
return deserializeHelper(nodes);
}
// Helper function for deserialization
function deserializeHelper(nodes) {
const val = nodes.shift();
if (val === "null") {
return null;
}
const root = new TreeNode(parseInt(val));
root.left = deserializeHelper(nodes);
root.right = deserializeHelper(nodes);
return root;
}
Algorithm Selection: When working with trees, selecting the appropriate algorithm based on the tree type and problem constraints is crucial for optimal performance. For example, while general recursive algorithms work on any tree, BSTs often have more efficient specialized algorithms.
Tree Design Principles
Effective tree data structure design requires understanding the trade-offs between different tree types and implementation approaches.
Choosing the Right Tree Structure
The selection of an appropriate tree structure depends on the specific requirements of your application.
| Tree Type | Best Used When | Avoid When |
|---|---|---|
| Binary Tree | - Simple hierarchical representation - Binary decisions/relationships |
- Need for efficient search - Multiple children per node |
| Binary Search Tree | - Ordered data storage - Frequent lookups - Dynamic insertions/deletions |
- Input data is already sorted - Need for worst-case guarantees |
| AVL Tree | - Frequent lookups/searches - Need for strict balance - Predictable performance |
- Frequent insertions/deletions - Memory constraints |
| Red-Black Tree | - Frequent insertions/deletions - Good average-case performance - System-level applications |
- Strict balance is critical - Need for optimal search time |
| B-Tree / B+ Tree | - Disk-based storage - Database indexing - Large datasets |
- Small datasets - Memory-based applications - Simple hierarchy needs |
| Trie (Prefix Tree) | - String/prefix operations - Dictionary implementation - Autocompletion features |
- Numerical data - Limited character set diversity - Memory constraints |
| Segment Tree | - Range queries - Frequent updates - Competitive programming |
- Simple queries only - Static data - Memory constraints |
Memory vs. Performance Considerations
Tree data structures involve trade-offs between memory usage and operation performance.
- Memory Overhead:
- Each node requires memory for data and pointers
- Self-balancing trees require additional metadata (heights, colors)
- More complex trees (B-trees, tries) have higher node overhead
- Performance Factors:
- Tree height directly impacts search/insertion/deletion time
- Balancing operations add overhead but provide consistency
- Cache locality affects real-world performance (compact vs. scattered nodes)
Design Tip: For memory-constrained environments, consider using more compact representations like arrays for complete binary trees, or bit-optimized nodes for tries. For performance-critical applications, prioritize tree types that guarantee logarithmic operations like AVL or Red-Black trees.
Design Patterns for Tree Structures
Several design patterns can be applied to tree implementations to make them more flexible and maintainable.
- Composite Pattern: Treat individual nodes and compositions of nodes uniformly
- Visitor Pattern: Separate algorithms from the tree structure for easy addition of new operations
- Iterator Pattern: Provide sequential access to tree elements without exposing the structure
- Factory Method: Create different types of trees based on requirements
- Strategy Pattern: Switch between different traversal or balancing strategies
Practical Design Considerations
- Thread Safety: Consider concurrent access requirements (read/write locks, immutable trees)
- Serialization: Plan for persistence and data transfer needs
- Customization: Allow for custom comparators or key extractors for flexible ordering
- Error Handling: Decide how to handle invalid operations or corrupted structures
- Memory Management: Consider pooling for frequent node creation/deletion
- Monitoring: Add instrumentation for tree health metrics (balance, depth, etc.)
Design Trade-offs: No single tree structure is optimal for all use cases. Be prepared to change your tree implementation as requirements evolve. Start with the simplest structure that meets your needs, and optimize only when necessary based on actual performance measurements.
Advanced Tree Implementations
Beyond basic implementations, several advanced techniques can be used to optimize tree data structures for specific use cases.
Memory-Efficient Binary Trees
For memory-constrained environments, specialized binary tree implementations can significantly reduce memory overhead.
// Array-based implementation of a complete binary tree
class CompleteBinaryTree {
private int[] tree;
private int size;
private int capacity;
public CompleteBinaryTree(int capacity) {
this.capacity = capacity;
this.tree = new int[capacity];
this.size = 0;
}
// Get index of parent node
public int parent(int index) {
if (index <= 0 || index >= size) {
throw new IllegalArgumentException("Invalid index");
}
return (index - 1) / 2;
}
// Get index of left child
public int leftChild(int index) {
int left = 2 * index + 1;
if (left >= size) {
throw new IllegalArgumentException("Left child doesn't exist");
}
return left;
}
// Get index of right child
public int rightChild(int index) {
int right = 2 * index + 2;
if (right >= size) {
throw new IllegalArgumentException("Right child doesn't exist");
}
return right;
}
// Insert a value (for a complete binary tree)
public void insert(int value) {
if (size >= capacity) {
throw new IllegalStateException("Tree is full");
}
tree[size++] = value;
}
// Get value at index
public int get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Invalid index");
}
return tree[index];
}
// Print the tree
public void print() {
for (int i = 0; i < size; i++) {
System.out.print(tree[i] + " ");
}
System.out.println();
}
}
# Array-based implementation of a complete binary tree
class CompleteBinaryTree:
def __init__(self, capacity):
self.capacity = capacity
self.tree = [0] * capacity
self.size = 0
# Get index of parent node
def parent(self, index):
if index <= 0 or index >= self.size:
raise ValueError("Invalid index")
return (index - 1) // 2
# Get index of left child
def left_child(self, index):
left = 2 * index + 1
if left >= self.size:
raise ValueError("Left child doesn't exist")
return left
# Get index of right child
def right_child(self, index):
right = 2 * index + 2
if right >= self.size:
raise ValueError("Right child doesn't exist")
return right
# Insert a value (for a complete binary tree)
def insert(self, value):
if self.size >= self.capacity:
raise ValueError("Tree is full")
self.tree[self.size] = value
self.size += 1
# Get value at index
def get(self, index):
if index < 0 or index >= self.size:
raise ValueError("Invalid index")
return self.tree[index]
# Print the tree
def print(self):
for i in range(self.size):
print(self.tree[i], end=" ")
print()
// Array-based implementation of a complete binary tree
class CompleteBinaryTree {
constructor(capacity) {
this.capacity = capacity;
this.tree = new Array(capacity).fill(0);
this.size = 0;
}
// Get index of parent node
parent(index) {
if (index <= 0 || index >= this.size) {
throw new Error("Invalid index");
}
return Math.floor((index - 1) / 2);
}
// Get index of left child
leftChild(index) {
const left = 2 * index + 1;
if (left >= this.size) {
throw new Error("Left child doesn't exist");
}
return left;
}
// Get index of right child
rightChild(index) {
const right = 2 * index + 2;
if (right >= this.size) {
throw new Error("Right child doesn't exist");
}
return right;
}
// Insert a value (for a complete binary tree)
insert(value) {
if (this.size >= this.capacity) {
throw new Error("Tree is full");
}
this.tree[this.size++] = value;
}
// Get value at index
get(index) {
if (index < 0 || index >= this.size) {
throw new Error("Invalid index");
}
return this.tree[index];
}
// Print the tree
print() {
for (let i = 0; i < this.size; i++) {
process.stdout.write(this.tree[i] + " ");
}
console.log();
}
}
Cache-Friendly B-Trees
B-Trees are designed for efficient disk access, but can also be optimized for cache locality in memory-based applications.
Implementation Tip: When implementing B-Trees, choose node size based on hardware characteristics. For disk-based systems, align with disk blocks (typically 4KB or 8KB). For in-memory applications, consider CPU cache line size (64-128 bytes). This alignment maximizes I/O efficiency and cache utilization.
Lock-Free Trees for Concurrency
In multi-threaded environments, specialized concurrent tree implementations can provide better performance than traditionally locked trees.
- Read-Copy-Update (RCU): Allows multiple readers to proceed without locking while writers create new versions
- Lock-Free BSTs: Using atomic operations to ensure thread safety without traditional locks
- Concurrent Skip Lists: Probabilistic alternative to balanced trees with good concurrent performance
Persistent Trees
Persistent (or immutable) tree data structures preserve previous versions when modified, providing efficient historical access.
- Path Copying: Copy the path from root to the modified node, reusing unaffected subtrees
- Fat Nodes: Store multiple values per node to track changes over time
- Applications: Version control systems, functional programming, undo/redo functionality
Advanced Implementation Challenges: Advanced tree implementations often increase code complexity. Carefully consider whether the performance benefits justify the added complexity and potential for bugs. Thoroughly test and benchmark any optimized implementations against simpler alternatives with representative workloads.
Specialized Tree Structures
Beyond the common tree types, several specialized tree structures have been developed to solve specific problems efficiently.
Segment Trees
Segment trees are specialized trees used for storing intervals or segments, allowing for efficient range queries and updates.
// Segment Tree for range sum queries
class SegmentTree {
int[] tree;
int n;
public SegmentTree(int[] nums) {
n = nums.length;
// Height of segment tree is ceil(log2(n))
int height = (int) Math.ceil(Math.log(n) / Math.log(2));
// Maximum size of segment tree is 2*2^h - 1
int maxSize = 2 * (1 << height) - 1;
tree = new int[maxSize];
buildTree(nums, 0, 0, n - 1);
}
// Build segment tree
private void buildTree(int[] nums, int index, int start, int end) {
// Leaf node (single element)
if (start == end) {
tree[index] = nums[start];
return;
}
int mid = (start + end) / 2;
// Build left and right subtrees
buildTree(nums, 2 * index + 1, start, mid);
buildTree(nums, 2 * index + 2, mid + 1, end);
// Internal node stores sum of elements in range
tree[index] = tree[2 * index + 1] + tree[2 * index + 2];
}
// Range sum query
public int sumRange(int left, int right) {
return sumRangeQuery(0, 0, n - 1, left, right);
}
private int sumRangeQuery(int index, int start, int end, int left, int right) {
// No overlap case
if (start > right || end < left) {
return 0;
}
// Total overlap case
if (start >= left && end <= right) {
return tree[index];
}
// Partial overlap case
int mid = (start + end) / 2;
return sumRangeQuery(2 * index + 1, start, mid, left, right) +
sumRangeQuery(2 * index + 2, mid + 1, end, left, right);
}
// Update value at given index
public void update(int i, int val) {
updateTreeNode(0, 0, n - 1, i, val);
}
private void updateTreeNode(int index, int start, int end, int i, int val) {
// Index out of range
if (i < start || i > end) {
return;
}
// Leaf node found
if (start == end) {
tree[index] = val;
return;
}
int mid = (start + end) / 2;
// Update in left or right subtree
if (i <= mid) {
updateTreeNode(2 * index + 1, start, mid, i, val);
} else {
updateTreeNode(2 * index + 2, mid + 1, end, i, val);
}
// Update current node
tree[index] = tree[2 * index + 1] + tree[2 * index + 2];
}
}
# Segment Tree for range sum queries
class SegmentTree:
def __init__(self, nums):
self.n = len(nums)
# Height of segment tree is ceil(log2(n))
height = math.ceil(math.log2(self.n))
# Maximum size of segment tree is 2*2^h - 1
max_size = 2 * (2 ** height) - 1
self.tree = [0] * max_size
self._build_tree(nums, 0, 0, self.n - 1)
# Build segment tree
def _build_tree(self, nums, index, start, end):
# Leaf node (single element)
if start == end:
self.tree[index] = nums[start]
return
mid = (start + end) // 2
# Build left and right subtrees
self._build_tree(nums, 2 * index + 1, start, mid)
self._build_tree(nums, 2 * index + 2, mid + 1, end)
# Internal node stores sum of elements in range
self.tree[index] = self.tree[2 * index + 1] + self.tree[2 * index + 2]
# Range sum query
def sum_range(self, left, right):
return self._sum_range_query(0, 0, self.n - 1, left, right)
def _sum_range_query(self, index, start, end, left, right):
# No overlap case
if start > right or end < left:
return 0
# Total overlap case
if start >= left and end <= right:
return self.tree[index]
# Partial overlap case
mid = (start + end) // 2
return (self._sum_range_query(2 * index + 1, start, mid, left, right) +
self._sum_range_query(2 * index + 2, mid + 1, end, left, right))
# Update value at given index
def update(self, i, val):
self._update_tree_node(0, 0, self.n - 1, i, val)
def _update_tree_node(self, index, start, end, i, val):
# Index out of range
if i < start or i > end:
return
# Leaf node found
if start == end:
self.tree[index] = val
return
mid = (start + end) // 2
# Update in left or right subtree
if i <= mid:
self._update_tree_node(2 * index + 1, start, mid, i, val)
else:
self._update_tree_node(2 * index + 2, mid + 1, end, i, val)
# Update current node
self.tree[index] = self.tree[2 * index + 1] + self.tree[2 * index + 2]
// Segment Tree for range sum queries
class SegmentTree {
constructor(nums) {
this.n = nums.length;
// Height of segment tree is ceil(log2(n))
const height = Math.ceil(Math.log2(this.n));
// Maximum size of segment tree is 2*2^h - 1
const maxSize = 2 * (1 << height) - 1;
this.tree = new Array(maxSize).fill(0);
this.buildTree(nums, 0, 0, this.n - 1);
}
// Build segment tree
buildTree(nums, index, start, end) {
// Leaf node (single element)
if (start === end) {
this.tree[index] = nums[start];
return;
}
const mid = Math.floor((start + end) / 2);
// Build left and right subtrees
this.buildTree(nums, 2 * index + 1, start, mid);
this.buildTree(nums, 2 * index + 2, mid + 1, end);
// Internal node stores sum of elements in range
this.tree[index] = this.tree[2 * index + 1] + this.tree[2 * index + 2];
}
// Range sum query
sumRange(left, right) {
return this.sumRangeQuery(0, 0, this.n - 1, left, right);
}
sumRangeQuery(index, start, end, left, right) {
// No overlap case
if (start > right || end < left) {
return 0;
}
// Total overlap case
if (start >= left && end <= right) {
return this.tree[index];
}
// Partial overlap case
const mid = Math.floor((start + end) / 2);
return this.sumRangeQuery(2 * index + 1, start, mid, left, right) +
this.sumRangeQuery(2 * index + 2, mid + 1, end, left, right);
}
// Update value at given index
update(i, val) {
this.updateTreeNode(0, 0, this.n - 1, i, val);
}
updateTreeNode(index, start, end, i, val) {
// Index out of range
if (i < start || i > end) {
return;
}
// Leaf node found
if (start === end) {
this.tree[index] = val;
return;
}
const mid = Math.floor((start + end) / 2);
// Update in left or right subtree
if (i <= mid) {
this.updateTreeNode(2 * index + 1, start, mid, i, val);
} else {
this.updateTreeNode(2 * index + 2, mid + 1, end, i, val);
}
// Update current node
this.tree[index] = this.tree[2 * index + 1] + this.tree[2 * index + 2];
}
}
Segment Tree Applications: Segment trees excel in scenarios requiring range operations like sum, minimum, maximum, or GCD. They're commonly used in computational geometry, competitive programming, and database systems for efficient range queries.
Trie (Prefix Tree)
A trie is a specialized tree used for storing a dynamic set of strings, where keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key.
// Trie node
class TrieNode {
TrieNode[] children;
boolean isEndOfWord;
public TrieNode() {
children = new TrieNode[26]; // Assuming lowercase English letters
isEndOfWord = false;
}
}
// Trie (Prefix Tree)
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Insert a word into the trie
public void insert(String word) {
TrieNode current = root;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (current.children[index] == null) {
current.children[index] = new TrieNode();
}
current = current.children[index];
}
// Mark the current node as end of word
current.isEndOfWord = true;
}
// Search for a word in the trie
public boolean search(String word) {
TrieNode current = root;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (current.children[index] == null) {
return false;
}
current = current.children[index];
}
// Return true if the current node is marked as end of word
return current.isEndOfWord;
}
// Check if there is any word in the trie that starts with the given prefix
public boolean startsWith(String prefix) {
TrieNode current = root;
for (char c : prefix.toCharArray()) {
int index = c - 'a';
if (current.children[index] == null) {
return false;
}
current = current.children[index];
}
return true;
}
}
# Trie node
class TrieNode:
def __init__(self):
self.children = {} # Dictionary for all possible characters
self.is_end_of_word = False
# Trie (Prefix Tree)
class Trie:
def __init__(self):
self.root = TrieNode()
# Insert a word into the trie
def insert(self, word):
current = self.root
for char in word:
if char not in current.children:
current.children[char] = TrieNode()
current = current.children[char]
# Mark the current node as end of word
current.is_end_of_word = True
# Search for a word in the trie
def search(self, word):
current = self.root
for char in word:
if char not in current.children:
return False
current = current.children[char]
# Return true if the current node is marked as end of word
return current.is_end_of_word
# Check if there is any word in the trie that starts with the given prefix
def starts_with(self, prefix):
current = self.root
for char in prefix:
if char not in current.children:
return False
current = current.children[char]
return True
// Trie node
class TrieNode {
constructor() {
this.children = {}; // Object for all possible characters
this.isEndOfWord = false;
}
}
// Trie (Prefix Tree)
class Trie {
constructor() {
this.root = new TrieNode();
}
// Insert a word into the trie
insert(word) {
let current = this.root;
for (const char of word) {
if (!current.children[char]) {
current.children[char] = new TrieNode();
}
current = current.children[char];
}
// Mark the current node as end of word
current.isEndOfWord = true;
}
// Search for a word in the trie
search(word) {
let current = this.root;
for (const char of word) {
if (!current.children[char]) {
return false;
}
current = current.children[char];
}
// Return true if the current node is marked as end of word
return current.isEndOfWord;
}
// Check if there is any word in the trie that starts with the given prefix
startsWith(prefix) {
let current = this.root;
for (const char of prefix) {
if (!current.children[char]) {
return false;
}
current = current.children[char];
}
return true;
}
}
Fenwick Tree (Binary Indexed Tree)
Fenwick trees provide efficient methods for calculating prefix sums in an array of numbers, with operations taking O(log n) time.
// Fenwick Tree (Binary Indexed Tree)
class FenwickTree {
private int[] tree;
private int n;
public FenwickTree(int n) {
this.n = n;
tree = new int[n + 1];
}
// Build Fenwick tree from an array
public FenwickTree(int[] nums) {
n = nums.length;
tree = new int[n + 1];
for (int i = 0; i < n; i++) {
update(i, nums[i]);
}
}
// Update value at index i by delta
public void update(int i, int delta) {
i++; // Convert to 1-based indexing
while (i <= n) {
tree[i] += delta;
i += i & (-i); // Add least significant bit
}
}
// Get sum of elements from index 0 to i
public int sum(int i) {
i++; // Convert to 1-based indexing
int sum = 0;
while (i > 0) {
sum += tree[i];
i -= i & (-i); // Remove least significant bit
}
return sum;
}
// Get sum of elements from index i to j
public int rangeSum(int i, int j) {
return sum(j) - sum(i - 1);
}
}
# Fenwick Tree (Binary Indexed Tree)
class FenwickTree:
def __init__(self, n_or_nums):
if isinstance(n_or_nums, int):
self.n = n_or_nums
self.tree = [0] * (n_or_nums + 1)
else:
self.n = len(n_or_nums)
self.tree = [0] * (self.n + 1)
for i, val in enumerate(n_or_nums):
self.update(i, val)
# Update value at index i by delta
def update(self, i, delta):
i += 1 # Convert to 1-based indexing
while i <= self.n:
self.tree[i] += delta
i += i & (-i) # Add least significant bit
# Get sum of elements from index 0 to i
def sum(self, i):
i += 1 # Convert to 1-based indexing
sum_val = 0
while i > 0:
sum_val += self.tree[i]
i -= i & (-i) # Remove least significant bit
return sum_val
# Get sum of elements from index i to j
def range_sum(self, i, j):
return self.sum(j) - self.sum(i - 1)
// Fenwick Tree (Binary Indexed Tree)
class FenwickTree {
constructor(nOrNums) {
if (typeof nOrNums === 'number') {
this.n = nOrNums;
this.tree = new Array(nOrNums + 1).fill(0);
} else {
this.n = nOrNums.length;
this.tree = new Array(this.n + 1).fill(0);
for (let i = 0; i < this.n; i++) {
this.update(i, nOrNums[i]);
}
}
}
// Update value at index i by delta
update(i, delta) {
i += 1; // Convert to 1-based indexing
while (i <= this.n) {
this.tree[i] += delta;
i += i & (-i); // Add least significant bit
}
}
// Get sum of elements from index 0 to i
sum(i) {
i += 1; // Convert to 1-based indexing
let sum = 0;
while (i > 0) {
sum += this.tree[i];
i -= i & (-i); // Remove least significant bit
}
return sum;
}
// Get sum of elements from index i to j
rangeSum(i, j) {
return this.sum(j) - this.sum(i - 1);
}
}
Other Specialized Tree Structures
- Quad Trees: Used for 2D space partitioning, common in image processing and collision detection
- KD Trees: Specialized for multi-dimensional key searches, used in nearest neighbor searches
- Suffix Trees: Store all suffixes of a string, used for complex string operations
- Splay Trees: Self-adjusting BSTs that move recently accessed nodes to the root
- Interval Trees: Store intervals and allow efficient queries for overlapping intervals
Choosing Specialized Structures: Each specialized tree structure comes with its own trade-offs in terms of implementation complexity, memory usage, and operation performance. Choose the right structure based on your specific use case and performance requirements, rather than defaulting to the most complex or general-purpose option.
Advanced Tree Applications
Tree data structures are used in numerous advanced applications across various domains of computer science.
Expression Trees
Expression trees represent arithmetic or logical expressions, where leaf nodes are operands and internal nodes are operators.
// Node in expression tree
class ExpressionNode {
String value; // Operator or operand
ExpressionNode left;
ExpressionNode right;
public ExpressionNode(String value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// Expression Tree
class ExpressionTree {
ExpressionNode root;
// Evaluate expression tree
public double evaluate(ExpressionNode node) {
// If node is leaf (operand)
if (node.left == null && node.right == null) {
return Double.parseDouble(node.value);
}
// Evaluate left and right subtrees
double leftValue = evaluate(node.left);
double rightValue = evaluate(node.right);
// Apply operator
switch (node.value) {
case "+": return leftValue + rightValue;
case "-": return leftValue - rightValue;
case "*": return leftValue * rightValue;
case "/": return leftValue / rightValue;
case "^": return Math.pow(leftValue, rightValue);
default: throw new IllegalArgumentException("Invalid operator: " + node.value);
}
}
// Build expression tree from postfix notation
public ExpressionNode buildFromPostfix(String[] tokens) {
Stack stack = new Stack<>();
for (String token : tokens) {
if (isOperator(token)) {
// Operator: pop two operands
ExpressionNode right = stack.pop();
ExpressionNode left = stack.pop();
// Create new node with operator
ExpressionNode node = new ExpressionNode(token);
node.left = left;
node.right = right;
// Push node back to stack
stack.push(node);
} else {
// Operand: push to stack
stack.push(new ExpressionNode(token));
}
}
// The final element in stack is the root
root = stack.pop();
return root;
}
// Check if a token is an operator
private boolean isOperator(String token) {
return token.equals("+") || token.equals("-") ||
token.equals("*") || token.equals("/") ||
token.equals("^");
}
}
# Node in expression tree
class ExpressionNode:
def __init__(self, value):
self.value = value # Operator or operand
self.left = None
self.right = None
# Expression Tree
class ExpressionTree:
def __init__(self):
self.root = None
# Evaluate expression tree
def evaluate(self, node):
# If node is leaf (operand)
if node.left is None and node.right is None:
return float(node.value)
# Evaluate left and right subtrees
left_value = self.evaluate(node.left)
right_value = self.evaluate(node.right)
# Apply operator
if node.value == '+':
return left_value + right_value
elif node.value == '-':
return left_value - right_value
elif node.value == '*':
return left_value * right_value
elif node.value == '/':
return left_value / right_value
elif node.value == '^':
return left_value ** right_value
else:
raise ValueError(f"Invalid operator: {node.value}")
# Build expression tree from postfix notation
def build_from_postfix(self, tokens):
stack = []
for token in tokens:
if self.is_operator(token):
# Operator: pop two operands
right = stack.pop()
left = stack.pop()
# Create new node with operator
node = ExpressionNode(token)
node.left = left
node.right = right
# Push node back to stack
stack.append(node)
else:
# Operand: push to stack
stack.append(ExpressionNode(token))
# The final element in stack is the root
self.root = stack.pop()
return self.root
# Check if a token is an operator
def is_operator(self, token):
return token in ['+', '-', '*', '/', '^']
// Node in expression tree
class ExpressionNode {
constructor(value) {
this.value = value; // Operator or operand
this.left = null;
this.right = null;
}
}
// Expression Tree
class ExpressionTree {
constructor() {
this.root = null;
}
// Evaluate expression tree
evaluate(node) {
// If node is leaf (operand)
if (node.left === null && node.right === null) {
return parseFloat(node.value);
}
// Evaluate left and right subtrees
const leftValue = this.evaluate(node.left);
const rightValue = this.evaluate(node.right);
// Apply operator
switch (node.value) {
case '+': return leftValue + rightValue;
case '-': return leftValue - rightValue;
case '*': return leftValue * rightValue;
case '/': return leftValue / rightValue;
case '^': return Math.pow(leftValue, rightValue);
default: throw new Error(`Invalid operator: ${node.value}`);
}
}
// Build expression tree from postfix notation
buildFromPostfix(tokens) {
const stack = [];
for (const token of tokens) {
if (this.isOperator(token)) {
// Operator: pop two operands
const right = stack.pop();
const left = stack.pop();
// Create new node with operator
const node = new ExpressionNode(token);
node.left = left;
node.right = right;
// Push node back to stack
stack.push(node);
} else {
// Operand: push to stack
stack.push(new ExpressionNode(token));
}
}
// The final element in stack is the root
this.root = stack.pop();
return this.root;
}
// Check if a token is an operator
isOperator(token) {
return ['+', '-', '*', '/', '^'].includes(token);
}
}
Huffman Coding for Compression
Huffman coding uses a binary tree to assign variable-length codes to characters based on their frequencies, resulting in efficient data compression.
// Node in Huffman tree
class HuffmanNode implements Comparable {
char character;
int frequency;
HuffmanNode left;
HuffmanNode right;
public HuffmanNode(char character, int frequency) {
this.character = character;
this.frequency = frequency;
}
public HuffmanNode(int frequency, HuffmanNode left, HuffmanNode right) {
this.frequency = frequency;
this.left = left;
this.right = right;
}
@Override
public int compareTo(HuffmanNode other) {
return this.frequency - other.frequency;
}
}
// Huffman Coding
class HuffmanCoding {
// Build Huffman tree from character frequencies
public HuffmanNode buildHuffmanTree(char[] chars, int[] frequencies) {
PriorityQueue queue = new PriorityQueue<>();
// Create leaf nodes for all characters
for (int i = 0; i < chars.length; i++) {
queue.add(new HuffmanNode(chars[i], frequencies[i]));
}
// Build Huffman tree by combining nodes
while (queue.size() > 1) {
// Remove two nodes with lowest frequencies
HuffmanNode left = queue.poll();
HuffmanNode right = queue.poll();
// Create internal node with these two as children
HuffmanNode parent = new HuffmanNode(
left.frequency + right.frequency, left, right);
// Add the new node to the queue
queue.add(parent);
}
// The remaining node is the root of the tree
return queue.poll();
}
// Generate Huffman codes from the tree
public Map generateCodes(HuffmanNode root) {
Map codes = new HashMap<>();
generateCodesRecursive(root, "", codes);
return codes;
}
// Helper method to generate codes recursively
private void generateCodesRecursive(HuffmanNode node, String code, Map codes) {
if (node == null) {
return;
}
// If this is a leaf node (has a character), add to codes
if (node.left == null && node.right == null) {
codes.put(node.character, code);
return;
}
// Traverse left (add 0 to code)
generateCodesRecursive(node.left, code + "0", codes);
// Traverse right (add 1 to code)
generateCodesRecursive(node.right, code + "1", codes);
}
// Encode a string using Huffman coding
public String encode(String text, Map codes) {
StringBuilder encoded = new StringBuilder();
for (char c : text.toCharArray()) {
encoded.append(codes.get(c));
}
return encoded.toString();
}
// Decode a Huffman-encoded string
public String decode(String encoded, HuffmanNode root) {
StringBuilder decoded = new StringBuilder();
HuffmanNode current = root;
for (char bit : encoded.toCharArray()) {
// Navigate tree based on bit
if (bit == '0') {
current = current.left;
} else {
current = current.right;
}
// If leaf node is reached, add character to result and reset to root
if (current.left == null && current.right == null) {
decoded.append(current.character);
current = root;
}
}
return decoded.toString();
}
}
import heapq
# Node in Huffman tree
class HuffmanNode:
def __init__(self, char=None, freq=0, left=None, right=None):
self.char = char
self.freq = freq
self.left = left
self.right = right
def __lt__(self, other):
return self.freq < other.freq
# Huffman Coding
class HuffmanCoding:
# Build Huffman tree from character frequencies
def build_huffman_tree(self, chars, frequencies):
heap = []
# Create leaf nodes for all characters
for i in range(len(chars)):
node = HuffmanNode(chars[i], frequencies[i])
heapq.heappush(heap, node)
# Build Huffman tree by combining nodes
while len(heap) > 1:
# Remove two nodes with lowest frequencies
left = heapq.heappop(heap)
right = heapq.heappop(heap)
# Create internal node with these two as children
parent = HuffmanNode(freq=left.freq + right.freq, left=left, right=right)
# Add the new node to the heap
heapq.heappush(heap, parent)
# The remaining node is the root of the tree
return heapq.heappop(heap)
# Generate Huffman codes from the tree
def generate_codes(self, root):
codes = {}
self._generate_codes_recursive(root, "", codes)
return codes
# Helper method to generate codes recursively
def _generate_codes_recursive(self, node, code, codes):
if node is None:
return
# If this is a leaf node (has a character), add to codes
if node.left is None and node.right is None:
codes[node.char] = code
return
# Traverse left (add 0 to code)
self._generate_codes_recursive(node.left, code + "0", codes)
# Traverse right (add 1 to code)
self._generate_codes_recursive(node.right, code + "1", codes)
# Encode a string using Huffman coding
def encode(self, text, codes):
encoded = ""
for char in text:
encoded += codes[char]
return encoded
# Decode a Huffman-encoded string
def decode(self, encoded, root):
decoded = ""
current = root
for bit in encoded:
# Navigate tree based on bit
if bit == '0':
current = current.left
else:
current = current.right
# If leaf node is reached, add character to result and reset to root
if current.left is None and current.right is None:
decoded += current.char
current = root
return decoded
// Node in Huffman tree
class HuffmanNode {
constructor(char = null, freq = 0, left = null, right = null) {
this.char = char;
this.freq = freq;
this.left = left;
this.right = right;
}
}
// Priority Queue implementation (simplified)
class PriorityQueue {
constructor() {
this.queue = [];
}
add(node) {
this.queue.push(node);
this.queue.sort((a, b) => a.freq - b.freq);
}
poll() {
return this.queue.shift();
}
size() {
return this.queue.length;
}
}
// Huffman Coding
class HuffmanCoding {
// Build Huffman tree from character frequencies
buildHuffmanTree(chars, frequencies) {
const queue = new PriorityQueue();
// Create leaf nodes for all characters
for (let i = 0; i < chars.length; i++) {
queue.add(new HuffmanNode(chars[i], frequencies[i]));
}
// Build Huffman tree by combining nodes
while (queue.size() > 1) {
// Remove two nodes with lowest frequencies
const left = queue.poll();
const right = queue.poll();
// Create internal node with these two as children
const parent = new HuffmanNode(
null, left.freq + right.freq, left, right);
// Add the new node to the queue
queue.add(parent);
}
// The remaining node is the root of the tree
return queue.poll();
}
// Generate Huffman codes from the tree
generateCodes(root) {
const codes = {};
this.generateCodesRecursive(root, "", codes);
return codes;
}
// Helper method to generate codes recursively
generateCodesRecursive(node, code, codes) {
if (node === null) {
return;
}
// If this is a leaf node (has a character), add to codes
if (node.left === null && node.right === null) {
codes[node.char] = code;
return;
}
// Traverse left (add 0 to code)
this.generateCodesRecursive(node.left, code + "0", codes);
// Traverse right (add 1 to code)
this.generateCodesRecursive(node.right, code + "1", codes);
}
// Encode a string using Huffman coding
encode(text, codes) {
let encoded = "";
for (const char of text) {
encoded += codes[char];
}
return encoded;
}
// Decode a Huffman-encoded string
decode(encoded, root) {
let decoded = "";
let current = root;
for (const bit of encoded) {
// Navigate tree based on bit
if (bit === '0') {
current = current.left;
} else {
current = current.right;
}
// If leaf node is reached, add character to result and reset to root
if (current.left === null && current.right === null) {
decoded += current.char;
current = root;
}
}
return decoded;
}
}
Decision Trees in Machine Learning
Decision trees are powerful models for classification and regression in machine learning, where each internal node represents a feature, each branch represents a decision rule, and each leaf represents an outcome.
Syntax Trees in Compilers
Syntax trees (abstract syntax trees) are used in compilers to represent the syntactic structure of source code, with each node representing a construct in the code.
Game Trees
Game trees represent possible game states and moves in games like chess or tic-tac-toe, using algorithms like Minimax and Alpha-Beta pruning for decision making.
// Minimax algorithm for Tic-Tac-Toe
public class TicTacToe {
// Define players
static final char PLAYER_X = 'X';
static final char PLAYER_O = 'O';
static final char EMPTY = '_';
// Minimax function to find the best move
public static int[] findBestMove(char[][] board) {
int bestVal = Integer.MIN_VALUE;
int[] bestMove = {-1, -1};
// Evaluate all possible moves
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
// Check if cell is empty
if (board[i][j] == EMPTY) {
// Make the move
board[i][j] = PLAYER_X;
// Compute evaluation function for this move
int moveVal = minimax(board, 0, false);
// Undo the move
board[i][j] = EMPTY;
// If the current move is better than the best move
if (moveVal > bestVal) {
bestMove[0] = i;
bestMove[1] = j;
bestVal = moveVal;
}
}
}
}
return bestMove;
}
// Minimax function with alpha-beta pruning
private static int minimax(char[][] board, int depth, boolean isMax) {
// Evaluate board for terminal state
int score = evaluate(board);
// If Maximizer has won, return score
if (score == 10) {
return score - depth;
}
// If Minimizer has won, return score
if (score == -10) {
return score + depth;
}
// If no moves left, it's a tie
if (!isMovesLeft(board)) {
return 0;
}
// Maximizer's move
if (isMax) {
int best = Integer.MIN_VALUE;
// Traverse all cells
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
// Check if cell is empty
if (board[i][j] == EMPTY) {
// Make the move
board[i][j] = PLAYER_X;
// Call minimax recursively and choose maximum value
best = Math.max(best, minimax(board, depth + 1, !isMax));
// Undo the move
board[i][j] = EMPTY;
}
}
}
return best;
}
// Minimizer's move
else {
int best = Integer.MAX_VALUE;
// Traverse all cells
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
// Check if cell is empty
if (board[i][j] == EMPTY) {
// Make the move
board[i][j] = PLAYER_O;
// Call minimax recursively and choose minimum value
best = Math.min(best, minimax(board, depth + 1, !isMax));
// Undo the move
board[i][j] = EMPTY;
}
}
}
return best;
}
}
// Helper functions for the minimax algorithm
private static boolean isMovesLeft(char[][] board) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j] == EMPTY) {
return true;
}
}
}
return false;
}
private static int evaluate(char[][] board) {
// Check rows for victory
for (int row = 0; row < 3; row++) {
if (board[row][0] == board[row][1] && board[row][1] == board[row][2]) {
if (board[row][0] == PLAYER_X) {
return 10;
} else if (board[row][0] == PLAYER_O) {
return -10;
}
}
}
// Check columns for victory
for (int col = 0; col < 3; col++) {
if (board[0][col] == board[1][col] && board[1][col] == board[2][col]) {
if (board[0][col] == PLAYER_X) {
return 10;
} else if (board[0][col] == PLAYER_O) {
return -10;
}
}
}
// Check diagonals for victory
if (board[0][0] == board[1][1] && board[1][1] == board[2][2]) {
if (board[0][0] == PLAYER_X) {
return 10;
} else if (board[0][0] == PLAYER_O) {
return -10;
}
}
if (board[0][2] == board[1][1] && board[1][1] == board[2][0]) {
if (board[0][2] == PLAYER_X) {
return 10;
} else if (board[0][2] == PLAYER_O) {
return -10;
}
}
// No winner
return 0;
}
}
# Minimax algorithm for Tic-Tac-Toe
class TicTacToe:
# Define players
PLAYER_X = 'X'
PLAYER_O = 'O'
EMPTY = '_'
@staticmethod
def find_best_move(board):
best_val = float('-inf')
best_move = [-1, -1]
# Evaluate all possible moves
for i in range(3):
for j in range(3):
# Check if cell is empty
if board[i][j] == TicTacToe.EMPTY:
# Make the move
board[i][j] = TicTacToe.PLAYER_X
# Compute evaluation function for this move
move_val = TicTacToe.minimax(board, 0, False)
# Undo the move
board[i][j] = TicTacToe.EMPTY
# If the current move is better than the best move
if move_val > best_val:
best_move = [i, j]
best_val = move_val
return best_move
@staticmethod
def minimax(board, depth, is_max):
# Evaluate board for terminal state
score = TicTacToe.evaluate(board)
# If Maximizer has won, return score
if score == 10:
return score - depth
# If Minimizer has won, return score
if score == -10:
return score + depth
# If no moves left, it's a tie
if not TicTacToe.is_moves_left(board):
return 0
# Maximizer's move
if is_max:
best = float('-inf')
# Traverse all cells
for i in range(3):
for j in range(3):
# Check if cell is empty
if board[i][j] == TicTacToe.EMPTY:
# Make the move
board[i][j] = TicTacToe.PLAYER_X
# Call minimax recursively and choose maximum value
best = max(best, TicTacToe.minimax(board, depth + 1, not is_max))
# Undo the move
board[i][j] = TicTacToe.EMPTY
return best
# Minimizer's move
else:
best = float('inf')
# Traverse all cells
for i in range(3):
for j in range(3):
# Check if cell is empty
if board[i][j] == TicTacToe.EMPTY:
# Make the move
board[i][j] = TicTacToe.PLAYER_O
# Call minimax recursively and choose minimum value
best = min(best, TicTacToe.minimax(board, depth + 1, not is_max))
# Undo the move
board[i][j] = TicTacToe.EMPTY
return best
# Helper functions for the minimax algorithm
@staticmethod
def is_moves_left(board):
for i in range(3):
for j in range(3):
if board[i][j] == TicTacToe.EMPTY:
return True
return False
@staticmethod
def evaluate(board):
# Check rows for victory
for row in range(3):
if board[row][0] == board[row][1] == board[row][2]:
if board[row][0] == TicTacToe.PLAYER_X:
return 10
elif board[row][0] == TicTacToe.PLAYER_O:
return -10
# Check columns for victory
for col in range(3):
if board[0][col] == board[1][col] == board[2][col]:
if board[0][col] == TicTacToe.PLAYER_X:
return 10
elif board[0][col] == TicTacToe.PLAYER_O:
return -10
# Check diagonals for victory
if board[0][0] == board[1][1] == board[2][2]:
if board[0][0] == TicTacToe.PLAYER_X:
return 10
elif board[0][0] == TicTacToe.PLAYER_O:
return -10
if board[0][2] == board[1][1] == board[2][0]:
if board[0][2] == TicTacToe.PLAYER_X:
return 10
elif board[0][2] == TicTacToe.PLAYER_O:
return -10
# No winner
return 0
// Minimax algorithm for Tic-Tac-Toe
class TicTacToe {
// Define players
static PLAYER_X = 'X';
static PLAYER_O = 'O';
static EMPTY = '_';
// Minimax function to find the best move
static findBestMove(board) {
let bestVal = -Infinity;
const bestMove = [-1, -1];
// Evaluate all possible moves
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
// Check if cell is empty
if (board[i][j] === this.EMPTY) {
// Make the move
board[i][j] = this.PLAYER_X;
// Compute evaluation function for this move
const moveVal = this.minimax(board, 0, false);
// Undo the move
board[i][j] = this.EMPTY;
// If the current move is better than the best move
if (moveVal > bestVal) {
bestMove[0] = i;
bestMove[1] = j;
bestVal = moveVal;
}
}
}
}
return bestMove;
}
// Minimax function with alpha-beta pruning
static minimax(board, depth, isMax) {
// Evaluate board for terminal state
const score = this.evaluate(board);
// If Maximizer has won, return score
if (score === 10) {
return score - depth;
}
// If Minimizer has won, return score
if (score === -10) {
return score + depth;
}
// If no moves left, it's a tie
if (!this.isMovesLeft(board)) {
return 0;
}
// Maximizer's move
if (isMax) {
let best = -Infinity;
// Traverse all cells
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
// Check if cell is empty
if (board[i][j] === this.EMPTY) {
// Make the move
board[i][j] = this.PLAYER_X;
// Call minimax recursively and choose maximum value
best = Math.max(best, this.minimax(board, depth + 1, !isMax));
// Undo the move
board[i][j] = this.EMPTY;
}
}
}
return best;
}
// Minimizer's move
else {
let best = Infinity;
// Traverse all cells
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
// Check if cell is empty
if (board[i][j] === this.EMPTY) {
// Make the move
board[i][j] = this.PLAYER_O;
// Call minimax recursively and choose minimum value
best = Math.min(best, this.minimax(board, depth + 1, !isMax));
// Undo the move
board[i][j] = this.EMPTY;
}
}
}
return best;
}
}
// Helper functions for the minimax algorithm
static isMovesLeft(board) {
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (board[i][j] === this.EMPTY) {
return true;
}
}
}
return false;
}
static evaluate(board) {
// Check rows for victory
for (let row = 0; row < 3; row++) {
if (board[row][0] === board[row][1] && board[row][1] === board[row][2]) {
if (board[row][0] === this.PLAYER_X) {
return 10;
} else if (board[row][0] === this.PLAYER_O) {
return -10;
}
}
}
// Check columns for victory
for (let col = 0; col < 3; col++) {
if (board[0][col] === board[1][col] && board[1][col] === board[2][col]) {
if (board[0][col] === this.PLAYER_X) {
return 10;
} else if (board[0][col] === this.PLAYER_O) {
return -10;
}
}
}
// Check diagonals for victory
if (board[0][0] === board[1][1] && board[1][1] === board[2][2]) {
if (board[0][0] === this.PLAYER_X) {
return 10;
} else if (board[0][0] === this.PLAYER_O) {
return -10;
}
}
if (board[0][2] === board[1][1] && board[1][1] === board[2][0]) {
if (board[0][2] === this.PLAYER_X) {
return 10;
} else if (board[0][2] === this.PLAYER_O) {
return -10;
}
}
// No winner
return 0;
}
}
Spatial Data Structures
Tree structures like Quadtrees and Octrees are used for efficient spatial partitioning, crucial in graphics, geographic information systems, and physics simulations.
Application Domain Knowledge: When applying tree data structures to specific domains, it's important to understand the domain requirements and constraints. The choice and implementation of a tree structure should be guided by domain-specific needs rather than generic performance metrics.
Recent Advances in Tree Structures
- Cache-Oblivious Trees: Trees designed to perform well without explicit knowledge of cache parameters
- Succinct Trees: Tree representations that approach the information-theoretic lower bound for space while supporting efficient operations
- Parallel Trees: Tree structures optimized for parallel processing and multi-core architectures
- Neural Tree Indexing: Combining tree structures with neural networks for learned indexes