Pre-order traversal of a tree visits nodes in which sequence?
Pre-order traversal visits the current Root node first, followed recursively by the Left subtree, and then the Right subtree. Pre-order is Root, Left, Right (NLR). It is useful for copying/serializing a tree and, together with in-order traversal and distinct keys, can reconstruct a binary tree.
Post-order traversal of a binary tree visits nodes in which order?
Post-order traversal processes the Left subtree, then Right subtree, and finally the Root node last. Post-order is Left, Right, Root (LRN). It is useful when a parent should be processed after its children, such as deleting a tree or evaluating an expression tree.
For a binary tree with distinct keys, which traversal must be paired with Pre-order or Post-order to reconstruct the tree uniquely?
For distinct keys, in-order traversal separates the left and right subtrees at each root. Pairing in-order with preorder or postorder therefore determines the tree uniquely. The in-order sequence identifies which keys belong to the left and right subtrees. The reconstruction is unique when node keys are distinct; with repeated keys, extra information may be required.
What is the worst-case time complexity of searching in a skewed (unbalanced) Binary Search Tree?
When a BST becomes completely skewed (like a linked list), searching degenerate nodes degrades to linear time O(n). A skewed BST has height n-1, so a search may inspect every node. Balanced BSTs keep height O(log n), which is why balancing matters.
What is the worst-case time complexity of the Quick Sort algorithm?
Quick Sort has a worst-case complexity of O($n^2)$ when the chosen pivot is consistently the minimum or maximum element (e.g., already sorted array). The worst case occurs when partitioning repeatedly produces subarrays of sizes 0 and n-1, such as with consistently poor pivot choices. Randomized or median-based pivot strategies reduce the likelihood of this case but do not change the classic worst-case bound.