Trees organize hierarchical data and support efficient search, insertion and traversal. PSC questions often ask traversal output, BST operation, height, balanced tree advantage and differences among AVL, red-black and splay trees.
Engineering Definitions
Tree
Standard definition: A hierarchical non-linear data structure consisting of nodes connected by edges with one root.
Exam meaning: Root बाट सुरु हुने parent-child hierarchy भएको structure।
Binary search tree
Standard definition: A binary tree where left subtree keys are smaller and right subtree keys are larger than node key.
Exam meaning: Search-friendly binary tree जसमा left smaller र right larger हुन्छ।
AVL tree
Standard definition: A self-balancing BST where balance factor of each node is -1, 0 or +1.
Exam meaning: Height strictly balanced राख्ने BST।
Red-black tree
Standard definition: A self-balancing BST using node colors and rules to keep height logarithmic.
Exam meaning: Color rules प्रयोग गरेर approximate balance राख्ने BST।
Splay tree
Standard definition: A self-adjusting BST that moves accessed nodes to root using rotations.
Exam meaning: Access भएको node लाई rotations बाट root नजिक ल्याउने tree।
Concept Teaching
A normal BST is fast only if height stays small. Sorted insertion can make it a chain with O(n) search. Balanced trees maintain logarithmic height using rotations or restructuring. Traversals provide systematic ways to visit nodes.
Tree Terminology
Terminology MCQs are common.
- Root has no parent.
- Leaf has no child.
- Degree is number of children.
- Height is longest path down to a leaf.
- Depth is distance from root.
- Subtree is a tree formed by a node and descendants.
Traversals
Traversal order is a frequent tracing question.
| Traversal | Order | Use |
|---|---|---|
| Preorder | Root, Left, Right | Copy tree/prefix expression |
| Inorder | Left, Root, Right | Sorted order in BST |
| Postorder | Left, Right, Root | Delete/evaluate expression tree |
| Level order | Breadth-first by levels | Queue-based traversal |
BST Operations
BST operation complexity depends on height.
- Search compares key and moves left/right.
- Insertion follows search path and adds leaf.
- Deletion has cases: leaf, one child, two children.
- Two-child deletion uses inorder successor or predecessor.
- Average balanced BST operations are O(log n).
- Skewed BST operations become O(n).
Balanced Trees
Balancing prevents degeneration.
| Tree | Balance idea | Tradeoff |
|---|---|---|
| AVL | Strict height balance | Fast lookup, more rotations |
| Red-black | Color rules, looser balance | Good update performance |
| Splay | Recently accessed nodes moved to root | Amortized efficiency, no explicit balance field |
Engineering Mechanism
- Compare key at current node.
- Move left or right based on ordering rule.
- Insert/delete changes structure.
- Balanced tree detects imbalance or rule violation.
- Rotations restore balance while preserving inorder order.
- Traversal visits nodes in defined order.
Diagrams / Models To Draw
- Draw binary tree with root/leaf/height labels.
- Draw BST insertion path.
- Draw inorder/preorder/postorder traversal numbering.
- Draw AVL rotation LL/RR/LR/RL concept.
- Draw red-black color idea.
Formulas, Algorithms and Code Patterns
- BST search time = O(h), where h is tree height.
- Balanced BST height = O(log n).
- Skewed BST height = O(n).
- AVL balance factor = height(left) – height(right).
- Inorder traversal of BST gives sorted keys.
| Tree | Search/update behavior | Exam point |
|---|---|---|
| BST | O(h) | Can become skewed |
| AVL | O(log n) | Strict balance factor |
| Red-black | O(log n) | Color rules |
| Splay | Amortized O(log n) | Splay accessed node |
| Heap | Priority structure | Not a BST |
| B-tree | Multiway balanced disk tree | Database/file systems |
Exam Point
- Inorder of BST is sorted.
- Mention O(h), then explain balanced vs skewed.
- AVL balance factor must be -1, 0 or +1.
- Rotations preserve BST ordering.
- Do not confuse heap order with BST order.
Worked Example
Insert 10, 5, 15, 3, 7 into BST. Root is 10; 5 goes left, 15 right, 3 left of 5, 7 right of 5. Inorder traversal gives 3, 5, 7, 10, 15.
Subjective Answer Pattern
- Define tree and BST.
- Explain traversal types.
- Describe search/insert/delete.
- Discuss balancing and rotations.
- Compare AVL, red-black and splay trees.
- Add complexity.
Common Engineering Mistakes
- Calling every binary tree a BST.
- Forgetting deletion two-child case.
- Confusing height and depth.
- Giving preorder when asked inorder.
- Saying AVL allows any balance factor.
MCQ Revision
- Which traversal gives sorted BST keys?
- BST search complexity in terms of height?
- AVL allowed balance factors?
- Which tree uses colors?
- Which tree splays accessed node?
- Which traversal uses queue?
Final Summary
- Trees model hierarchy and support efficient search.
- BST ordering enables search by comparison.
- Traversal order must be traced carefully.
- Balanced trees keep operations logarithmic.
- AVL, red-black and splay trees use different balancing strategies.