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

Recall & Review

beginner

What is a Binary Search Tree (BST)?

A Binary Search Tree is a tree where each node has at most two children. The left child's value is less than the parent's value, and the right child's value is greater than the parent's value.

beginner

What does "Kth Smallest Element in BST" mean?

It means finding the element that would be in position K if all elements of the BST were sorted in ascending order.

beginner

Which traversal method helps find the Kth smallest element in a BST efficiently?

Inorder traversal visits nodes in ascending order in a BST, so it helps find the Kth smallest element by counting nodes visited.

intermediate

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

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

advanced

How can you optimize finding the Kth smallest element if the BST nodes store the count of nodes in their left subtree?

You can use the stored counts to decide whether to go left, right, or return the current node without full traversal, reducing time to O(H).

Which traversal visits BST nodes in ascending order?

A Postorder traversal

B Inorder traversal

C Preorder traversal

D Level order traversal

Inorder traversal visits left subtree, then node, then right subtree, which results in ascending order for BST.

What is the Kth smallest element in a BST?

A The element at position K in sorted order

B The element with value K

C The Kth node visited in preorder traversal

D The largest element minus K

The Kth smallest element is the element that appears at position K when all BST elements are sorted.

If a BST has height H, what is the worst-case time complexity to find the Kth smallest element using inorder traversal?

A O(log H)

B O(K)

C O(H * K)

D O(H + K)

We first go down height H to leftmost node, then visit K nodes, so total O(H + K).

Which data structure property helps quickly find the Kth smallest element in a BST?

A Nodes store color

B Nodes store parent pointers

C Nodes store subtree sizes

D Nodes store depth

Storing subtree sizes allows skipping parts of the tree to find the Kth smallest faster.

What is the first step in finding the Kth smallest element in a BST using inorder traversal?

A Traverse the left subtree

B Traverse the right subtree

C Visit the root node

D Count total nodes

Inorder traversal starts with the left subtree to visit nodes in ascending order.

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

Think about the order nodes are visited in inorder traversal.

Describe one way to optimize finding the Kth smallest element if the BST nodes store extra information.

Consider how extra data in nodes can guide the search.