Trees — Part 1 | AlgoCrux

Introduction to Trees

What is a Tree?

A Tree is a hierarchical data structure consisting of nodes connected by edges. Unlike linear structures (arrays, linked lists), trees organize data in a parent-child relationship, enabling efficient searching, insertion, and deletion.

A tree with n nodes has exactly n-1 edges. There is exactly one path between any two nodes, and no cycles exist.

Why Trees are used

// Trees provide O(log n) operations
struct Node {
  int data;
  Node* left;
  Node* right;
};

// vs O(n) for linear search

💡 Why Trees? Because they represent hierarchical relationships naturally. A file system, an organization chart, or an HTML DOM — all are trees. Trees enable binary search (O(log n)), efficient sorting, and expressive power in AI decision-making.

Characteristics & Real-world Applications

🌳 Hierarchical Structure

Data is organized in levels with a root at the top and leaves at the bottom, mirroring real-world hierarchies.

🔗 No Cycles

A valid tree has no cycles. There is exactly one unique path from the root to any node.

📐 n-1 Edges

A tree with n nodes always has exactly n-1 edges. This is a fundamental invariant.

💾 File Systems

Directories and files form a tree: root (/) → folders → subfolders → files.

🏢 Organization Charts

CEO → VPs → Directors → Managers → Employees — a perfect tree structure.

🌐 HTML DOM

The Document Object Model is a tree: html → head/body → div → p → span.

📁 Folders

Nested folders in any OS are inherently tree-structured for navigation.

👨‍👩‍👧‍👦 Genealogy Trees

Family trees trace ancestry from a common ancestor through generations.

🤖 Decision Trees

AI/ML uses trees to model decisions: each node is a test, each branch an outcome.

✓ Advantages

Efficient searching with O(log n) in balanced trees.
Natural representation of hierarchical data.
Flexible structure — easy to grow and shrink.
Enables powerful algorithms: BST, AVL, Red-Black, Trie.
Optimal for range queries and ordered data.

✕ Disadvantages

Unbalanced trees degrade to O(n) performance.
No random access — must traverse from root.
More complex to implement than arrays or lists.
Extra memory overhead for pointers in each node.
Rebalancing operations add overhead.

Tree Terminology

Types of Trees

Binary Tree Basics

Node Structure

Each node in a binary tree contains data, a left pointer, and a right pointer. The left pointer references the left child; the right pointer references the right child. Null pointers indicate no child.

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

Recursive Thinking

Trees are inherently recursive. Every subtree is itself a tree. This means most tree algorithms follow a simple pattern: do something at the current node, then recurse on left, then recurse on right.

Base case: if node is null, return. Recursive case: process node, then left subtree, then right subtree.

💡 Recursive Power: Because every subtree is a tree, recursive solutions are often the most elegant and readable. A function that works on a single node + its children automatically works on the entire tree.

Pointer Representation

Each node stores pointers to its children. This is the most common and flexible representation, allowing dynamic growth and arbitrary tree shapes.

Memory: O(n) for n nodes. Each node uses space for data + 2 pointers (typically 8-16 bytes overhead per node on 64-bit systems).

Array Representation

For complete binary trees, we can store nodes in an array using index arithmetic:

// For node at index i (0-based):
left_child = 2*i + 1
right_child = 2*i + 2
parent = (i-1) / 2

// Used in heaps and segment trees

Interactive Tree Visualization

Build & Explore a Binary Tree

Tree Controls

Height

max depth

Depth

selected node

Levels

total levels

Total Nodes

count

Leaf Nodes

no children

Internal

has children

Tree Traversals

Depth First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It uses a stack (implicit via recursion or explicit).

Preorder: Root → Left → Right
Inorder: Left → Root → Right
Postorder: Left → Right → Root

Breadth First Search (BFS)

BFS explores all nodes at the present depth before moving to the next level. It uses a queue.

Level Order: Visit nodes level by level, left to right. Essential for finding shortest paths in unweighted graphs and for tree serialization.

💡 Traversal Insight: Inorder traversal of a BST yields values in sorted ascending order. This is why BSTs are so powerful — they embed sorting into their structure.

Iterative Traversals

Using explicit stacks to avoid recursion overhead:

// Stack-based Preorder
stack.push(root);
while (!stack.empty()) {
  node = stack.top(); stack.pop();
  visit(node);
  if (node.right) stack.push(node.right);
  if (node.left) stack.push(node.left);
}

Morris Traversal

Morris traversal achieves O(n) time and O(1) space by temporarily modifying tree pointers (threading) to create links back to ancestors, then restoring them.

// Morris Inorder — no stack, no recursion
while (current) {
if (!current.left) { visit(current); current = current.right; }
else { /* find predecessor, thread, traverse */ }
}

Interactive Traversal Visualization

Animated Traversal Explorer

Stack:

Select a traversal type and press Play to see the animation.

Speed Medium

Tree Complexity

Traversal (DFS/BFS)

O(n)

Must visit every node exactly once. n = number of nodes.

Search (BST)

O(log n)

Balanced BST: height is log n. Unbalanced: degrades to O(n).

Insertion (BST)

O(log n)

Find correct position and insert. Same as search complexity.

Deletion (BST)

O(log n)

Find node, handle 0/1/2 children cases. Same as search.

Recursive Space

O(h)

Call stack depth equals tree height h. Worst case O(n) for skewed.

Iterative Space

O(h)

Explicit stack/queue size. Morris achieves O(1) space.

⚠️ Practical Note: These complexities assume a balanced tree. In the worst case (degenerate/skewed tree), all operations degrade to O(n) because height h = n. Self-balancing trees (AVL, Red-Black) guarantee O(log n) by maintaining balance.

Applications of Trees

📁

File Systems

Hierarchical directory structures with nested folders and files.

📄

XML / JSON

Document parsing and validation using tree-based parsers (DOM).

🌐

HTML DOM

Browser renders web pages by traversing the DOM tree.

➗

Expression Trees

Compilers use trees to represent and evaluate mathematical expressions.

🤖

Decision Trees

Machine learning algorithms classify data by traversing decision nodes.

🧠

AI / Games

Minimax trees for game AI, alpha-beta pruning for optimization.

💾

Databases

B-Trees and B+ Trees power database indexing for fast lookups.

⚙️

Compiler Design

Abstract Syntax Trees (AST) represent program structure for compilation.

🖥️

Operating Systems

Process scheduling, memory management, and file allocation use trees.

🔍

Search Engines

Trie structures enable fast prefix-based autocomplete and spell checking.

C++ Implementation

tree_implementation.cpp · C++ Binary Tree

#include <iostream>
#include <queue>
using namespace std;

// ── Tree Node Structure ──
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// ── Recursive Traversals ──
void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->val << " ";     // visit root
    preorder(root->left);        // traverse left
    preorder(root->right);       // traverse right
}

void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);         // traverse left
    cout << root->val << " ";      // visit root
    inorder(root->right);        // traverse right
}

void postorder(TreeNode* root) {
    if (!root) return;
    postorder(root->left);       // traverse left
    postorder(root->right);      // traverse right
    cout << root->val << " ";     // visit root
}

// ── Level Order (BFS) ──
void levelOrder(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* curr = q.front(); q.pop();
        cout << curr->val << " ";
        if (curr->left)  q.push(curr->left);
        if (curr->right) q.push(curr->right);
    }
}

// ── Iterative Preorder using Stack ──
void iterativePreorder(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* curr = s.top(); s.pop();
        cout << curr->val << " ";
        if (curr->right) s.push(curr->right);
        if (curr->left)  s.push(curr->left);
    }
}

// ── Helper: Create a sample tree ──
TreeNode* createSampleTree() {
    TreeNode* root = new TreeNode(1);
    root->left  = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left  = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);
    return root;
}

int main() {
    TreeNode* root = createSampleTree();

    cout << "Preorder:  "; preorder(root); cout << endl;
    cout << "Inorder:   "; inorder(root); cout << endl;
    cout << "Postorder: "; postorder(root); cout << endl;
    cout << "Level:     "; levelOrder(root); cout << endl;

    return 0;
}

🤖 Ask AI — Explain any Tree concept

Ask a question above to get an AI explanation of any Tree concept.

Interview Preparation

What is the maximum number of nodes in a binary tree of height h?

2^(h+1) - 1 for a perfect binary tree. At level k, there are at most 2^k nodes.

How do you check if two trees are identical?

Recursive: if both null → true. If one null → false. If values differ → false. Recurse on left and right subtrees.

What is the time complexity of tree traversal?

O(n) for all traversals (DFS and BFS) because each node is visited exactly once.

How to find the height of a binary tree?

max(height(left), height(right)) + 1. Base case: null node has height -1 or 0 depending on convention.

What is a degenerate tree?

A tree where each node has only one child, effectively becoming a linked list. Height = n-1.

Explain recursive thinking in trees.

Every subtree is a tree. Solve for root, assume function works for children, combine results. Trust the recursion.

Interactive Quiz

Test Your Tree Knowledge

Score: 0 / 10

Loading question...

Cheat Sheet

📚 Terminology

Root: Topmost node, no parent

Leaf: Node with no children

Height: Max edges from node to leaf

Depth: Edges from root to node

Degree: Number of children

Subtree: Any node + its descendants

🌲 Tree Types

Binary: Max 2 children per node

Full: Every node has 0 or 2 children

Complete: All levels filled except last, left-packed

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

Balanced: Height difference ≤ 1 for all subtrees

Skewed: Each node has only one child

🔄 Traversals

Preorder: Root → Left → Right

Inorder: Left → Root → Right

Postorder: Left → Right → Root

Level Order: BFS using queue

Morris: O(1) space, threaded traversal

⏱️ Complexities

Traversal: O(n) time, O(h) space

Search BST: O(log n) balanced, O(n) skewed

Insert/Delete: O(log n) balanced, O(n) skewed

Morris: O(n) time, O(1) space

Space: O(n) for n nodes

Key Takeaways

What You Learned

A Tree is a hierarchical data structure with n nodes and n-1 edges, containing no cycles.
Binary Trees restrict each node to at most 2 children, enabling efficient O(log n) operations when balanced.
Tree Traversals (Preorder, Inorder, Postorder, Level Order) visit nodes in different orders for different use cases.
Inorder traversal of a BST produces sorted output — a powerful property for ordered data.
Recursive thinking is natural for trees: every subtree is itself a tree.
Morris Traversal achieves O(n) time with O(1) space using threaded pointers.
Trees power file systems, databases, compilers, AI, and countless real-world applications.
Always consider tree balance — unbalanced trees degrade to linked-list performance (O(n)).

Next Learning Path

Trees — Part 2

Binary Tree Mastery · BST · AVL · Red-Black Trees · Advanced Traversals

→