LearnDSA.me - Master Data Structures & Algorithms

Trees are hierarchical data structures that consist of nodes connected by edges. Unlike linear structures (arrays, linked lists), trees represent data in a parent-child relationship, making them perfect for organizing hierarchical information.

Key Characteristics:

Hierarchical structure with parent-child relationships

One root node at the top

No cycles (acyclic graph)

Each node has zero or more children

Real-World Examples:

🗂️ File Systems: Folders containing files and subfolders

🏢 Organization Charts: Company hierarchy structure

🧬 Family Trees: Genealogical relationships

📚 Decision Trees: AI/ML decision making processes

🌐 HTML DOM: Web page element hierarchy

Basic Tree Visualization

Root: Node A (top level)

Parents: A is parent of B,C; B is parent of D,E

Children: B,C are children of A

Leaves: D, E, F (no children)

Height: 3 levels from root to leaves

Essential Tree Terminology

Node

Basic unit containing data and links to children

Example: Each circle in the tree diagram above

Root

Top-most node with no parent

Example: Node A in our example tree

Parent

Node with one or more children

Example: A is parent of B and C

Child

Node connected below another node

Example: B and C are children of A

Leaf

Node with no children (terminal node)

Example: Nodes D, E, F in our example

Sibling

Nodes sharing the same parent

Example: B and C are siblings

Ancestor

Node on the path from root to current node

Example: A is ancestor of all nodes

Descendant

Node reachable by going down the tree

Example: D and E are descendants of B

Subtree

Tree formed by a node and all its descendants

Example: Node B with D,E forms a subtree

Height

Maximum number of edges from root to leaf

Example: Our example tree has height 2

Depth/Level

Number of edges from root to a node

Example: Node B is at depth 1

Degree

Number of children a node has

Example: Node A has degree 2

Types of Trees

Binary Tree

Each node has at most 2 children (left and right)

Key Properties:

Max 2 children per node
Left and right child distinction
Most common tree type

Common Uses:

Expression treesDecision treesHeap data structure

Binary Search Tree (BST)

Binary tree where left child < parent < right child

Key Properties:

Sorted structure
Fast search/insert/delete
In-order gives sorted sequence

Common Uses:

Database indexingSearch algorithmsSymbol tables

Complete Binary Tree

All levels filled except possibly the last (filled left to right)

Key Properties:

Efficient array representation
Height is log(n)
Used in heaps

Common Uses:

Priority queuesHeap sortBinary heaps

Perfect Binary Tree

All internal nodes have 2 children, all leaves at same level

Key Properties:

2^h - 1 total nodes
Perfectly balanced
Rare in practice

Common Uses:

Theoretical analysisMemory layoutParallel algorithms

AVL Tree

Self-balancing BST where heights of subtrees differ by at most 1

Key Properties:

Automatically balanced
Guaranteed O(log n) operations
Rotations on insert/delete

Common Uses:

DatabasesMemory managementCompiler symbol tables

N-ary Tree

Tree where each node can have up to N children

Key Properties:

Variable number of children
More than 2 children allowed
Flexible structure

Common Uses:

File systemsOrganization chartsGame trees

Important Tree Properties

Mathematical Properties:

Number of Nodes: In a complete binary tree of height h: 2^h - 1 to 2^(h+1) - 1 nodes

Number of Leaves: In a binary tree with n internal nodes: n + 1 leaves

Maximum Nodes: At level i: 2^i nodes (starting from level 0)

Minimum Height: For n nodes: ⌊log₂(n)⌋ (perfectly balanced tree)

Performance Characteristics:

Operation	Balanced	Worst Case
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Traversal	O(n)	O(n)

Tree vs Other Structures:

vs Arrays:

✅ Dynamic size, efficient insertion/deletion
❌ No direct indexing, more memory overhead

vs Linked Lists:

✅ Faster search (O(log n) vs O(n))
❌ More complex implementation

vs Hash Tables:

✅ Ordered data, range queries
❌ Slower average case access

Common Pitfalls:

Unbalanced Trees: Can degrade to O(n) performance

Memory Overhead: Each node needs extra pointer storage

Recursion Depth: Stack overflow risk with deep trees

Not Cache-Friendly: Nodes may be scattered in memory

Back to Module Overview Next: Binary Trees

Operation

Balanced

Worst Case

O(log n)

O(n)

Insert

O(log n)

O(n)

Delete

O(log n)

O(n)

Traversal

O(n)