Loading...
Comprehensive guide to tree data structures, covering fundamental concepts, various tree types, and essential algorithms for tree operations.
A tree is a hierarchical data structure consisting of nodes connected by edges. It's called a tree because it resembles an inverted tree with the root at the top and leaves at the bottom.
Key Properties:
A binary tree is a tree where each node has at most two children, typically called left and right child.
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
class BinaryTree {
constructor() {
this.root = null;
}
insert(val) {
const newNode = new TreeNode(val);
if (!this.root) {
this.root = newNode;
return;
}
// Insert logic here
this.insertHelper(this.root, newNode);
}
insertHelper(node, newNode) {
if (newNode.val < node.val) {
if (!node.left) {
node.left = newNode;
} else {
this.insertHelper(node.left, newNode);
}
} else {
if (!node.right) {
node.right = newNode;
} else {
this.insertHelper(node.right, newNode);
}
}
}
}Tree traversal is the process of visiting each node in a tree exactly once. There are different ways to traverse a tree, each useful for different purposes.
Visit left subtree, then root, then right subtree
function inorder(node) {
if (node) {
inorder(node.left);
console.log(node.val);
inorder(node.right);
}
}Result for BST: 20, 30, 40, 50, 60, 70, 80 (sorted order)
Visit root, then left subtree, then right subtree
function preorder(node) {
if (node) {
console.log(node.val);
preorder(node.left);
preorder(node.right);
}
}Result: 50, 30, 20, 40, 70, 60, 80 (useful for copying tree)
Visit left subtree, then right subtree, then root
function postorder(node) {
if (node) {
postorder(node.left);
postorder(node.right);
console.log(node.val);
}
}Result: 20, 40, 30, 60, 80, 70, 50 (useful for deleting tree)
Visit nodes level by level from left to right
function levelOrder(root) {
if (!root) return;
const queue = [root];
while (queue.length > 0) {
const node = queue.shift();
console.log(node.val);
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
}
}Result: 50, 30, 70, 20, 40, 60, 80 (level by level)
where n = number of nodes, h = height of tree
A Binary Search Tree is a binary tree with the following property:
For every node in the tree:
function search(root, val) {
if (!root || root.val === val) {
return root;
}
if (val < root.val) {
return search(root.left, val);
} else {
return search(root.right, val);
}
}function insert(root, val) {
if (!root) {
return new TreeNode(val);
}
if (val < root.val) {
root.left = insert(root.left, val);
} else if (val > root.val) {
root.right = insert(root.right, val);
}
return root;
}Three cases to handle:
Self-balancing BST where height difference between left and right subtrees is at most 1.
Self-balancing BST with colored nodes that satisfy specific color properties.
Complete binary tree that satisfies the heap property.
Directory structures in operating systems use tree hierarchies to organize files and folders.
B-trees and B+ trees enable efficient searching, insertion, and deletion in database systems.
Abstract syntax trees represent mathematical expressions and code structure in compilers.
Machine learning algorithms use decision trees for classification and regression problems.
Routing algorithms use tree structures to find optimal paths in computer networks.
AI algorithms like minimax use game trees to evaluate possible moves in strategy games.
Note: Balanced trees guarantee O(log n) for all operations