What is the worst-case space complexity of a Binary Search Tree with n nodes due to call stack frame overhead during recursive search?
In a skewed BST of height n-1, recursive search creates n stack frames, leading to worst-case auxiliary space complexity of O(n).
In a XOR Doubly Linked List, how is the pointer field 'npx' stored in each node?
A XOR Linked List reduces pointer overhead by storing a single field 'npx', calculated as the bitwise XOR of the memory addresses of the previous and next nodes.
What is the number of distinct binary trees that can be constructed with n unlabeled nodes?
The number of structurally unique binary trees with n unlabeled nodes is given by the nth Catalan Number $C_{n} = (1 / (n + 1)) \cdot (2n)$! / (n! * n!).
In a self-balancing Splay Tree, which operation moves a accessed target node to the root via tree rotations?
A Splay Tree performs 'splaying' (using zig, zig-zig, and zig-zag rotations) on every accessed element to move it to the root, guaranteeing amortized O(log n) performance.
Which statements correctly describe a Skip List?
All three statements are correct for the standard randomized Skip List. Its probabilistic levels provide expected O(log n) operations while avoiding the rotation logic of balanced search trees.