Introduction to Trees
Trees are hierarchical data structures consisting of nodes connected by edges. They're fundamental to computer science and used in databases, file systems, and algorithms.
What is a Tree?
A tree is a connected acyclic graph with exactly one path between any two nodes. It consists of nodes (vertices) connected by edges, with one designated root node.
• Hierarchical: Natural parent-child relationships• Acyclic: No cycles or loops• Connected: Path exists between any two nodes
Basic Terms
Root: Top node, no parent
Leaf: Node with no children
Height: Root to deepest leaf
Depth: Distance from root
Key Formulas
Edges = Nodes - 1Max nodes = 2^(h+1) - 1Min height = ⌊log₂(n)⌋Relationships
Parent: Node directly above
Child: Node directly below
Sibling: Same parent nodes
Subtree: Node + descendants
Tree Structure & Terminology
Tree Traversal Methods
Pre-order
Root → Left → Right
Visit root first, then recursively traverse left and right subtrees
In-order
Left → Root → Right
Traverse left subtree, visit root, then right subtree (gives sorted order in BST)
Post-order
Left → Right → Root
Traverse both subtrees first, then visit root (useful for deletion)
Level-order (BFS)
Level by level
Visit nodes level by level from top to bottom, left to right
Types of Trees
Binary Tree
Each node has at most 2 children (left and right)