Questions
3 questions
Difficulty
Medium
Importance
High yield for core Data Structures papers
Overview
Trees are hierarchical non-linear data structures consisting of nodes connected by edges, fundamental to organizing data efficiently. In university exams, mastering trees is essential as they bridge the gap between simple linked lists and complex database indexing structures, frequently appearing in algorithm design questions.
Binary Trees & Traversals
A binary tree is a structure where each node has at most two children, referred to as the left and right child. Traversals represent systematic ways to visit every node, which is a frequent focus for implementation-based exam questions.
- Pre-order: Root -> Left -> Right
- In-order: Left -> Root -> Right
- Post-order: Left -> Right -> Root
- Max nodes at level i: 2^i
- Max nodes in tree of height h: 2^(h+1) - 1
Binary Search Trees (BST)
A BST is a specialized binary tree where the left child is smaller than the parent and the right child is larger. This property allows for efficient searching, insertion, and deletion operations, typically resulting in O(log n) time complexity for balanced trees.
- In-order traversal always produces a sorted list
- Search complexity: O(h) where h is height
- Deletion requires finding the in-order successor or predecessor
- Worst-case: O(n) for degenerate skewed trees
AVL & B-Trees
AVL trees are self-balancing BSTs that use rotation to maintain height, while B-Trees are generalized multi-way search trees optimized for disk storage. Both are critical for high-performance systems and appear often in long-form university theory questions.
- AVL balance factor = height(left) - height(right)
- AVL allowed balance factors: -1, 0, +1
- B-Tree nodes can have more than two children
- B-Trees are perfectly balanced by design
- Minimum degree 't' defines B-Tree capacity
Formula Sheet
Number of leaf nodes = Number of degree-2 nodes + 1
Height of AVL tree: O(log n)
B-Tree node minimum keys: t-1
B-Tree node maximum keys: 2t-1
Exam Tip
When asked to perform a traversal, always draw the tree first to visualize the path, as it significantly reduces calculation errors in recursive steps.
Common Mistakes
- Confusing the order of node visits in pre-order versus post-order traversals
- Failing to maintain balance factor invariants during AVL insertion/deletion operations
- Assuming all binary trees are automatically binary search trees without validating the node property
More Revision Notes
Ready to test yourself?
Play topic-wise Trees questions in Aspirant Arcade — gamified MCQ practice.
Download Free