Data Structures · topic
Binary search tree search, insertion and deletion in all three cases, inorder successor and predecessor, height bounds, BST from a preorder, insertion orders, valid search paths, and AVL trees (beyond the named syllabus): balance factor, the four rotations, insertion traces and the minimum nodes for a height.
The binary search tree property and its consequences, search and insertion paths, minimum and maximum, inorder successor and predecessor in both cases, deletion of a leaf, a node with one child and a node with two children (successor or predecessor replacement) traced on one tree, height bounds and the cost of every operation. All paths, successors and post-deletion trees come from a verification script.
A partial preview of the top of the sheet. The full sheet is in the Data Structures cheat sheet pack.
Rebuilding a BST from its preorder (GATE CS 2026 Set 1 Q.62), depth after a sequence of insertions (GATE CS 2025 Set 2 Q.35), which keys can come third when building a complete BST (GATE CS 2026 Set 1 Q.40), valid search paths with the range method, how insertion order changes height, how many orders build one BST, k-th smallest and checking the BST property. Every answer is recomputed by a script.
A partial preview of the top of the sheet. The full sheet is in the Data Structures cheat sheet pack.
AVL trees (beyond the named syllabus) as height-balanced binary search trees: balance factor, the four imbalance cases and their single and double rotations, insertion traces with every rotation named, the minimum number of nodes for a height (a Fibonacci-like recurrence), the largest possible height for n nodes, and the cost of search, insertion and deletion. Rotations and counts are checked by an AVL implementation and brute force.
A partial preview of the top of the sheet. The full sheet is in the Data Structures cheat sheet pack.
