All types of trees in data structures

Here are all types of trees used in computer science, their purpose, and how to implement them (mainly using Java-like pseudocode).

---

🌳 1. What is a Tree?

A tree is a hierarchical data structure consisting of nodes connected by edges.

Root: Topmost node

Parent / Child: Relationship between nodes

Leaf: Node with no children

Height: Longest path from root to a leaf

Depth: Distance from root to the node

Example:

    A
   / \
  B   C
 / \
D   E

---

🌲 2. Basic Tree Implementation (Generic)

class TreeNode { T value; List<TreeNode> children = new ArrayList<>();

TreeNode(T value) {
    this.value = value;
}

void addChild(TreeNode<T> child) {
    children.add(child);
}

}

Use it for any generic (non-binary) tree.

---

🌴 3. Binary Tree (Each node has max 2 children)

Structure

    1
   / \
  2   3
 / \
4   5

Implementation

class Node { int data; Node left, right;

Node(int data) {
    this.data = data;
}

}

Traversals

Preorder (Root → Left → Right)

Inorder (Left → Root → Right)

Postorder (Left → Right → Root)

Level Order (BFS)

void inorder(Node root) { if (root == null) return; inorder(root.left); System.out.print(root.data + " "); inorder(root.right); }

---

🌵 4. Binary Search Tree (BST)

Rule: Left child < Parent < Right child

Example

8 /
3 10 / \
1 6 14

Operations

Node insert(Node root, int key) { if (root == null) return new Node(key); if (key < root.data) root.left = insert(root.left, key); else root.right = insert(root.right, key); return root; }

boolean search(Node root, int key) { if (root == null) return false; if (root.data == key) return true; return key < root.data ? search(root.left, key) : search(root.right, key); }

---

🎋 5. AVL Tree (Self-Balancing BST)

Keeps tree height small (O(log n))

Each node stores balance factor = height(left) - height(right)

Rotations fix imbalance:

Left rotation

Right rotation

Left-Right

Right-Left

Used in databases, memory indexing, etc.

---

🌿 6. Red-Black Tree (Self-Balancing BST)

Each node is Red or Black

Ensures longest path ≤ 2 × shortest path

Common in TreeMap, TreeSet (Java), and Linux kernel.

Rules maintain balance using color flips and rotations.

---

🌱 7. B-Tree

Multi-branching (not binary)

Used in databases and file systems

Each node can have many keys and children

Keeps data sorted and allows O(log n) search/insert/delete

Example: used in MySQL, NTFS, PostgreSQL indexes.

---

🌾 8. B+ Tree

Extension of B-Tree

All data stored in leaf nodes

Internal nodes only store keys (for fast lookup)

Leaves are linked for fast range queries

Used in databases and storage systems.

---

🌰 9. Trie (Prefix Tree)

Used for strings / prefix matching

Example: autocomplete, dictionary lookup

insert("car") insert("cat")

Structure:

(root) └── c └── a ├── r └── t

Implementation:

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd;
}

void insert(TrieNode root, String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        node.children.putIfAbsent(c, new TrieNode());
        node = node.children.get(c);
    }
    node.isEnd = true;
}

---

🌺 10. Heap (Binary Heap)

Complete binary tree

Heap property:

Min-Heap → parent ≤ children

Max-Heap → parent ≥ children

Implemented using array

int left(int i) { return 2 * i + 1; }
int right(int i) { return 2 * i + 2; }

Used in:

Priority Queue

Heap sort

Dijkstra’s algorithm

---

🌼 11. Segment Tree

Used for range queries and updates on arrays e.g., sum, min, max in range [L, R]

Time complexity: O(log n) for both query & update.

---

🌻 12. Fenwick Tree (Binary Indexed Tree)

Efficient structure for prefix sums

Space-efficient compared to Segment Tree

Common in competitive programming.

---

🌳 13. N-ary Tree

Each node can have N children.

Example: Used in HTML DOM, game trees, AI decision trees.

Implementation:

class NNode {
    int data;
    List<NNode> children = new ArrayList<>();
}

---

🌲 14. Suffix Tree

Used for pattern matching in strings.

Helps find substring occurrences in O(m) time.

---

🌴 15. Expression Tree

Used to represent and evaluate mathematical expressions.

Example:

    *
   / \
  +   -
 / \ / \
3  2 4  5

Evaluate using postorder traversal.

---