🌳 Trees - Hierarchical Data Structure
🟡 Intermediate Non-Linear DS 90 min read
🎯 What is a Tree?
A Tree is a non-linear, hierarchical data structure consisting of nodes connected by edges. It has a single root node, and every node (except root) has exactly one parent. Trees are the foundation for file systems, databases, AI, and more.
[1] ← Root (no parent)
/ \
[2] [3] ← Children of 1
/ \ \
[4] [5] [6] ← Leaf nodes (no children)
Terminology:
- Root: Topmost node (1)
- Parent: Node with children (1 is parent of 2,3)
- Child: Node with a parent (2,3 are children of 1)
- Leaf: Node with no children (4,5,6)
- Edge: Connection between nodes
- Height: Longest path from root to leaf (here: 2)
- Depth: Distance from root to node🔄 Tree Traversals (The Most Important Concept)
DFS (Depth-First Search)
1
/ \
2 3
/ \
4 5
Preorder: 1→2→4→5→3 (Root→Left→Right)
Inorder: 4→2→5→1→3 (Left→Root→Right)
Postorder: 4→5→2→3→1 (Left→Right→Root)BFS (Breadth-First Search)
Level Order: 1→2→3→4→5
(Level by level, left to right)
Uses a Queue:
Enqueue root, while queue not empty:
Dequeue, process, enqueue children💻 PHP Tree Implementation
<?php
class TreeNode {
public int $val;
public ?TreeNode $left = null;
public ?TreeNode $right = null;
public function __construct(int $val) {
$this->val = $val;
}
}
class BinaryTree {
public ?TreeNode $root = null;
// Preorder: Root → Left → Right
public function preorder(?TreeNode $node): void {
if ($node === null) return;
echo $node->val . ' ';
$this->preorder($node->left);
$this->preorder($node->right);
}
// Inorder: Left → Root → Right
public function inorder(?TreeNode $node): void {
if ($node === null) return;
$this->inorder($node->left);
echo $node->val . ' ';
$this->inorder($node->right);
}
// Postorder: Left → Right → Root
public function postorder(?TreeNode $node): void {
if ($node === null) return;
$this->postorder($node->left);
$this->postorder($node->right);
echo $node->val . ' ';
}
// Level Order (BFS) using Queue
public function levelOrder(): array {
if ($this->root === null) return [];
$result = []; $queue = [$this->root];
while (!empty($queue)) {
$node = array_shift($queue);
$result[] = $node->val;
if ($node->left) $queue[] = $node->left;
if ($node->right) $queue[] = $node->right;
}
return $result;
}
// Height of tree
public function height(?TreeNode $node): int {
if ($node === null) return 0;
return 1 + max($this->height($node->left), $this->height($node->right));
}
// Count nodes
public function count(?TreeNode $node): int {
if ($node === null) return 0;
return 1 + $this->count($node->left) + $this->count($node->right);
}
// Iterative Preorder (no recursion)
public function preorderIterative(): array {
if ($this->root === null) return [];
$result = []; $stack = [$this->root];
while (!empty($stack)) {
$node = array_pop($stack);
$result[] = $node->val;
if ($node->right) $stack[] = $node->right; // right first
if ($node->left) $stack[] = $node->left; // so left pops first
}
return $result;
}
}
// Create tree: [1,2,3,4,5]
$tree = new BinaryTree();
$tree->root = new TreeNode(1);
$tree->root->left = new TreeNode(2);
$tree->root->right = new TreeNode(3);
$tree->root->left->left = new TreeNode(4);
$tree->root->left->right = new TreeNode(5);
echo "Preorder: "; $tree->preorder($tree->root); // 1 2 4 5 3
echo "Inorder: "; $tree->inorder($tree->root); // 4 2 5 1 3
echo "Height: " . $tree->height($tree->root); // 3📂 Types of Trees
| Binary Tree | Each node has ≤2 children | Expression trees |
| Binary Search Tree | Left < Root < Right | Databases, search |
| AVL Tree | Self-balancing BST (|balance| ≤ 1) | Fast lookups |
| Red-Black Tree | Self-balancing BST with colors | Linux kernel, HashMap |
| B-Tree / B+Tree | Multi-way tree for disk I/O | Database indexing |
| Trie (Prefix Tree) | String-based tree | Autocomplete, IP routing |
| Segment Tree | Range query tree | Range sum/min queries |
| Fenwick Tree (BIT) | Prefix sum tree | Cumulative frequency |
💼 Interview Questions
2^L nodes. Level 0 = 1 node (root), Level 1 = 2, Level 2 = 4, etc. Total nodes in full tree of height h: 2^h - 1.
BFS: shortest path, level-order, closer nodes first. DFS: path existence, topological sort, uses less memory for deep trees. BFS uses Queue; DFS uses Stack (or recursion).