Tree

TerminologyTerminology

• Root: top node. Leaf: node with no children. Internal node: has at least one child.
• Depth of a node: edges from the root. Height of a tree: edges on the longest root-to-leaf path (some books count nodes — check the question).
• Degree: number of children.

• Root: sabse upar wala node. Leaf: jiska koi child nahi. Internal node: jiska kam se kam ek child ho.
• Node ki depth: root se kitne edges. Tree ki height: sabse lambe root-to-leaf path ke edges (kuch books nodes ginti hain — question check karo).
• Degree: children ki ginti.

Binary tree propertiesBinary tree properties

TraversalsTraversals

• Level order uses a queue.
• Inorder + preorder, or inorder + postorder → unique tree.
• Preorder + postorder → unique only for full binary trees.

• Level order mein queue use hoti hai.
• Inorder + preorder, ya inorder + postorder → unique tree milta hai.
• Preorder + postorder → sirf full binary trees ke liye unique.

void inorder(Node *t)   { if (t) { inorder(t->left);  visit(t); inorder(t->right); } }
void preorder(Node *t)  { if (t) { visit(t); preorder(t->left);  preorder(t->right); } }
void postorder(Node *t) { if (t) { postorder(t->left); postorder(t->right); visit(t); } }

Binary search tree (BST)Binary search tree (BST)

• Left subtree < node < right subtree, so inorder traversal gives sorted order.
• Search, insert, delete: O(h) — O(log n) if balanced, O(n) if skewed (e.g. inserting sorted data).
• Delete a node with two children: replace it with its inorder successor (or predecessor).
• Given only the preorder of a BST, the tree is unique (inorder is just the sorted order).

• Left subtree < node < right subtree, isliye inorder traversal sorted order deta hai.
• Search, insert, delete: O(h) — balanced ho toh O(log n), skewed ho toh O(n) (jaise sorted data insert karna).
• Do children wala node delete karna: usko inorder successor (ya predecessor) se replace karo.
• Sirf BST ka preorder diya ho toh bhi tree unique hai (inorder toh bas sorted order hai).

AVL treeAVL tree

A self-balancing BST where the balance factor (height of left − height of right) of every node is −1, 0 or +1. Rotations (LL, RR, LR, RL) restore balance after insert/delete.Ek self-balancing BST jisme har node ka balance factor (left height − right height) −1, 0 ya +1 hota hai. Insert/delete ke baad rotations (LL, RR, LR, RL) balance wapas laate hain.

TipN(h) = N(h − 1) + N(h − 2) + 1. All operations are O(log n).N(h) = N(h − 1) + N(h − 2) + 1. Saare operations O(log n).

Binary heapBinary heap

• Complete binary tree stored in an array. Max-heap: parent ≥ children.
• 1-indexed: children of i are 2i and 2i + 1; parent is ⌊i / 2⌋.
• Insert and delete-max: O(log n). Find max: O(1).
• Build-heap (bottom-up heapify): O(n), not O(n log n).
• Leaves are at indices ⌊n/2⌋ + 1 … n.

• Complete binary tree jo array mein store hota hai. Max-heap: parent ≥ children.
• 1-indexed: i ke children 2i aur 2i + 1; parent ⌊i / 2⌋.
• Insert aur delete-max: O(log n). Find max: O(1).
• Build-heap (bottom-up heapify): O(n), O(n log n) nahi.
• Leaves indices ⌊n/2⌋ + 1 … n pe hote hain.

Common mistakeCommon galtiSearching an arbitrary element in a heap is O(n) — a heap is not a BST.Heap mein koi random element search karna O(n) hai — heap BST nahi hai.