algoadvance

Given the root of a binary search tree (BST) and an integer k, return the kth smallest element in the tree.

Example:

Input: root = [3,1,4,null,2], k = 1
Output: 1

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

Constraints:

• The number of nodes in the tree is n.
• 1 <= k <= n <= 10^4
• 0 <= Node.val <= 10^4

Clarifying Questions

1. Is the k value always valid?
   • Yes, it is guaranteed that 1 <= k <= n, where n is the number of nodes in the BST.
2. Is the BST valid without any duplicate values?
   • Yes, by definition BST should not have duplicate values.

Strategy

1. Inorder Traversal:
   • The most straightforward way to solve this problem is through inorder traversal of the BST. Inorder traversal of a BST gives nodes in non-decreasing order.
   • We can keep a counter while traversing to keep track of the number of nodes visited.
   • Once we have visited k nodes, the kth node’s value is the kth smallest element.
2. Algorithm:
   • Perform an inorder traversal (Left, Root, Right).
   • Use a stack to iteratively traverse the tree.
   • Keep a count of nodes visited.
   • Return the value of the node when the count equals k.
3. Time Complexity:
   • The solution will have a time complexity of O(H + k), where H is the height of the tree. This is because we might have to traverse the height of the tree to get to the leftmost node and then traverse k nodes.

Code

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def kthSmallest(root: TreeNode, k: int) -> int:
    stack = []
    current = root
    count = 0
    
    # Inorder traversal loop
    while stack or current:
        # Reach the left most Node of the current Node
        while current:
            stack.append(current)
            current = current.left
        
        # current must be None at this point
        current = stack.pop()
        count += 1
        
        # If count is equal to k, return the current node's value
        if count == k:
            return current.val
            
        # Move to the right subtree
        current = current.right

# Example Usage:
# Let's create a test tree [3,1,4,null,2]
#       3
#      / \
#     1   4
#      \
#       2

root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)

k = 1
print(kthSmallest(root, k))  # Output: 1

Explanation:

• A stack is used to simulate the inorder traversal iteratively.
• The outer while loop runs until there are nodes left to process.
• The inner while loop processes all the left nodes of the current subtree.
• Nodes are popped from the stack and processed, and the right subtree is then processed.
• The count variable ensures that we stop and return the kth node’s value.

This approach ensures we efficiently find the kth smallest element without the need for additional space beyond the recursion stack or maintaining a separate sorted list of elements.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?