Tree?

A tree is a connected graph with no cycles:
  1 root
  Every node has exactly one parent.

Binary tree

Each node has at most 2 children: left and right.

      
      1                 1
     / \               /
    2   3             2
                     /
                    3   ← this is also a binary tree

Full binary tree (proper / 2-tree)

Every node has 0 children OR exactly 2 children.
Filling of nodes should be done from LEFT TO RIGHT.

      a
     / \
    b   c
   / \
  d   e

      a
     / \
    b   c
       /
      d

Complete binary tree

Every node have 0 or children.

        a
       / \
      b   c
     / \
    d   e

        a
       / \
      b   c
           \
            d

Full ≠ complete. A full tree can have a hole on the last level. A complete tree can have a node with only a left child (the last node).

Perfect binary tree

Full and complete, and every leaf is at the same depth. Every internal node has two children. Node count is always 2h+1 − 1.

      a
     / \
    b   c

        a
       / \
      b   c
     / \ / \
    d  e f  g

Binary search tree (BST)

A binary tree with an order on values: everything in the left subtree is < the node, everything on the right is > the node. Search walks left or right — O(log n) if the tree is reasonably balanced, O(n) if it becomes a stick.

        5
       / \
      3   7
     / \
    1   4

        5
       / \
      6   7

AVL / Red-Black trees are BSTs that rotate so they stay balanced. See also Hash table vs BST.

Sum tree

A binary tree where each node’s value equals the sum of all values in its left subtree plus all values in its right subtree. An empty child counts as 0. A leaf is a sum tree (both sides empty).

          26
         /  \
       10    3
      /  \    \
     4    6    3

leaf 4:  0 + 0 = 0, leaf itself is OK
10 = 4 + 6
3  = 0 + 3
26 = (10+4+6) + (3+3) = 20 + 6

Used in interview checks (“is this tree a sum tree?”) and as a running-total structure, not as a general-purpose search tree.

M-ary tree (M-tree)

A node can have up to M children, not 2.
Examples:
- A filesystem folder tree
- A B-tree (used by databases and filesystems) is a sorted, balanced M-ary search tree.

M = 3
            A
         /  |  \
        B   C   D
       / \
      E   F

Types of M-ary Trees

1. B-Tree (self balanced M-ary search tree)

2. B+ Tree (self balanced M-ary search tree)

Databases store data in B+ trees for efficient retrieval and management.
Most of data on same level. Hence depth of tree is less wrt BST & makes efficient wrt BST.
BTree is better wrt Disk Access: Since DB uses B-Tree/B+Tree. Search time is still better than disk.

struct btree{
    int *keys;  // An array of keys
    int t;      // Minimum degree (defines the range for number of keys)
    BTreeNode **C; // An array of child pointers
    int n;     // Current number of keys
    bool leaf; // Is true when node is leaf. Otherwise false
}    

Insertion Example

Imagine we are inserting employee IDs (1, 2, 3, 4) along with their row data (Data1, Data2, Data3, Data4)
Every node capacity = 2 (max 2 keys per node)

Step 1: Insert (1,Data1), (2,Data2): Insert 2 entries

Root Node: 
[ (1, Data1) | (2, Data2) ]

Step 2: Insert (3,Data3): Insert 3rd entry leading to Overflow and splitting into a B+ Tree structure
NOTICE:
  Middle key (2) is copied upward to form a routing node(ie which does not have data)
  While the actual data stays strictly at the bottom leaf level. The leaves form a horizontal sequence link (-->) to allow for sequential access of data.

             [ 2 ] //Root Node
            /      \
           /        \
Leaf Nodes: 
[ (1, Data1) ] ---> [ (2, Data2) | (3, Data3) ]