Kth Smallest Element in BST in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Kth Smallest Element in a Binary Search Tree (BST)?

It is the element that would appear in the Kth position if all the elements of the BST were sorted in ascending order.

beginner

Why does an inorder traversal of a BST give elements in sorted order?

Because inorder traversal visits nodes in the order: left child, current node, right child. In a BST, left child nodes are smaller and right child nodes are larger, so this order produces sorted elements.

intermediate

What is the time complexity of finding the Kth smallest element using inorder traversal in a BST?

The time complexity is O(H + K), where H is the height of the tree. This is because we traverse down to the leftmost node (height H) and then visit K nodes in order.

advanced

How can you optimize finding the Kth smallest element if the BST is frequently queried?

By augmenting each node with the count of nodes in its left subtree, you can decide whether to go left, right, or return the current node without full traversal, reducing time complexity to O(H).

intermediate

What is the role of a stack in iterative inorder traversal to find the Kth smallest element?

The stack keeps track of nodes to visit next, simulating the recursive call stack. It helps traverse the tree without recursion, visiting nodes in sorted order until the Kth element is found.

What traversal method is best suited to find the Kth smallest element in a BST?

A Level order traversal

B Preorder traversal

C Postorder traversal

D Inorder traversal

Inorder traversal visits nodes in ascending order in a BST, making it ideal to find the Kth smallest element.

If K is 1, what element does the Kth smallest element represent in a BST?

A The largest element

B The root element

C The smallest element

D The median element

The 1st smallest element is the smallest element in the BST.

What data structure is commonly used to implement iterative inorder traversal?

A Queue

B Stack

C Linked list

D Hash map

A stack is used to keep track of nodes during iterative inorder traversal.

What is the worst-case time complexity to find the Kth smallest element in a skewed BST using inorder traversal?

A O(N)

B O(1)

C O(log N)

D O(N log N)

In a skewed BST, height H can be N, so time complexity is O(N).

How can augmenting BST nodes with subtree counts help in finding the Kth smallest element?

A It helps skip unnecessary nodes

B It sorts the tree

C It balances the tree

D It stores the Kth element directly

Subtree counts allow deciding which subtree to explore, skipping nodes that are not needed.

Explain how inorder traversal helps find the Kth smallest element in a BST.

Think about the order nodes are visited in a BST.

Describe one optimization to improve the efficiency of finding the Kth smallest element in a BST.

Consider adding extra information to nodes.