Consider a singly linked list with head pointer. What is the time complexity to insert a new node at the END of the list if ONLY the head pointer is given?
Without a tail pointer, one must traverse all N nodes from head to reach the last node before inserting, taking O(N) time.
Consider a Hash Table of size 10 using open addressing with linear probing h(k, i) = (k + i) % 10. Insert keys: 12, 22, 32. At which index will key 32 be stored?
h(12, 0) = 2 (stored at index 2). h(22, 0) = 2 (collision) -> h(22, 1) = 3 (stored at index 3). h(32, 0) = 2 (collision) -> h(32, 1) = 3 (collision) -> h(32, 2) = 4 (stored at index 4).
What is the maximum number of nodes in a Binary Tree of height h (where height of root node alone is 0)?
For height h (root at level 0), max nodes = 2^0 + 2^1 + ... + 2^$h = 2^{h+1} - 1$.
A Perfect Binary Tree has 15 total nodes. What is the height of the tree (root at height 0)?
Formula: N = 2^(h+1) - 1 => 15 = 2^(h+1) - 1 => 2^(h+1) = 16 => h+1 = 4 => h = 3.
Which tree traversal of a Binary Search Tree (BST) produces the keys in strictly ASCENDING sorted order?
Inorder traversal (Left, Root, Right) of a valid BST visits keys in strictly sorted ascending order.