In a complete binary tree of n nodes, what is the index of the parent of node at index i (1-based indexing)?
In 1-based array storage of a complete binary tree, the parent of node i is at index floor(i / 2), the left child is at 2i, and the right child is at 2i + 1.
What is the minimum number of nodes in an AVL tree of height 4 (where height of a single node tree is 0)?
Minimum nodes N(h) in an AVL tree of height h satisfies N(h) = N(h-1) + N(h-2) + 1. Base cases: N(0)=1, N(1)=2. N(2)=2+1+1=4. N(3)=4+2+1=7. N(4)=N(3)+N(2)+1 = 7 + 4 + 1 = 12.
Consider a max-heap represented as an array [100, 80, 60, 50, 70, 40, 30, 20, 10]. After deleting the maximum element (100) and performing max-heapify, what is the array representation of the resulting max-heap?
Delete 100: replace root with last element 10 -> [10, 80, 60, 50, 70, 40, 30, 20]. Heapify root 10: swap with max child 80 -> [80, 10, 60, 50, 70, 40, 30, 20]. Heapify 10 at index 1: swap with max child 70 -> [80, 70, 60, 50, 10, 40, 30, 20].
How many distinct Binary Search Trees (BSTs) can be constructed with 4 distinct keys?
The number of distinct BSTs that can be formed with n distinct keys is given by the n-th Catalan number $C_{n} = (1 / (n + 1)) \cdot (2n choose n)$. For n = 4: $C_{4} = (1 / 5) \cdot (8 choose 4) = (1 / 5) \cdot 70 = 14$.
In a fully (double) threaded binary tree with n nodes, where every NULL child pointer is replaced by a predecessor/successor thread, how many threads are there?
A binary tree with n nodes has 2n child pointers and n-1 real child links, leaving n+1 NULL links. In a fully double-threaded representation, these NULL links become threads.