Binary Trees: Types and Properties

Binary Tree ek aisi tree data structure hoti hai jisme har node ke at most 2 children ho sakte hain, jinhe typically Left Child aur Right Child kaha jata hai (Degree of every node <= 2).

Types of Binary Trees

Full Binary Tree:       Complete Binary Tree:       Perfect Binary Tree:
       (A)                      (A)                         (A)
      /   \                    /   \                       /   \
    (B)   (C)                (B)   (C)                   (B)   (C)
   /   \                    /   \                       / \   / \
 (D)   (E)                (D)   (E)                   (D) (E)(F) (G)
(Every node 0 or 2)     (All levels full except      (All internal nodes 2,
                         last, filled left-to-right)  all leaves at same level)

1. Full / Strict Binary Tree: Har node ke paas ya toh exactly 0 children hote hain ya exactly 2 children hote hain. Koi bhi node single child nahi rakhta.
2. Complete Binary Tree: Sabhi levels completely filled hote hain, except possibly the last level, aur last level ke saare nodes as far left as possible pack hote hain. (Binary Heap ka foundation).
3. Perfect Binary Tree: Sabhi internal nodes ke 2 children hote hain aur saare leaf nodes strictly same level par hote hain.
4. Degenerate / Skewed Binary Tree: Har internal node ke paas sirf 1 child hota hai (Left-skewed ya Right-skewed). Yeh functionally ek linked list ban jata hai with O(n) height.
5. Balanced Binary Tree: Har node par left aur right subtrees ki height ka difference at most 1 hota hai (e.g. AVL Tree). Height hamesha O(log n) hoti hai.

Important Mathematical Properties (GATE & Exam Formulas)

• Level i par maximum nodes = 2^i (jahan root level 0 par hai).
• Height h ke binary tree me maximum nodes = 2^(h+1) - 1.
• N nodes ke binary tree ki minimum possible height = ceil(log2(N + 1)) - 1.
• Kisi bhi non-empty binary tree me, agar n0 leaf nodes hain aur n2 degree-2 nodes hain, toh hamesha: n0 = n2 + 1.

Agli post me hum cover karenge Binary Tree Traversals: Inorder, Preorder, and Postorder.