LeetCode: 230 Kth Smallest Element in a BST

LeetCode 230: Kth Smallest Element in a BST

https://leetcode.com/problems/kth-smallest-element-in-a-bst/

Problem Description:

Given the root of a binary search tree (BST), write a function to find the k-th 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

Solution Approach:

Because of the in-order traversal property of BSTs (i.e., elements are in ascending order), we can use in-order traversal to find the k-th smallest element.

Detailed Steps:

Use a stack for in-order traversal:
- Perform an iterative in-order traversal (left, root, right) using a stack.
- The stack is used to simulate recursion, pushing each node until the leftmost node is reached.
Pop elements from the stack:
- For each node popped from the stack, decrease k by 1.
- If k reaches 0, we have found the k-th smallest element, so return its value.
Continue to the right subtree:
- If the k-th element has not been found, move to the right subtree and continue the traversal.

Code Implementation (with detailed comments):

from typing import Optional

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

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stk = []  # Initialize the stack
        cur = root  # Start from the root node

        # Iterative in-order traversal
        while cur or stk:
            # Traverse to the leftmost node
            while cur:
                stk.append(cur)  # Push current node to stack
                cur = cur.left  # Move to the left child

            # Pop from stack
            cur = stk.pop()

            # Decrement k
            k -= 1
            # If k becomes 0, return the current node's value
            if k == 0:
                return cur.val

            # Move to the right subtree
            cur = cur.right

Code Explanation:

Initialize stack and pointer:
- Use a stack stk to simulate recursion, and a pointer cur to start at the root.
In-order traversal:
- Use a loop to push the current node and all its left children onto the stack until the leftmost node is reached.
- Once a node is popped from the stack, decrement k by 1.
- If k becomes 0, return the value of the current node because it is the k-th smallest element.
Continue with the right subtree:
- If the k-th element is not found, move to the right child and continue the in-order traversal.
Return the result:
- Return the value of the k-th smallest element when k reaches 0.

Complexity Analysis:

Time Complexity: O(H + k), where H is the height of the tree. In the worst case, we might need to visit all the left children (H depth), and then continue to visit up to k nodes.
Space Complexity: O(H), where H is the height of the tree. The stack can contain up to H nodes.

Example Analysis:

Example 1:

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

In-order traversal order: [1, 2, 3, 4].
The 1st smallest element is 1, so return 1.

Example 2:

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

In-order traversal order: [1, 2, 3, 4, 5, 6].
The 3rd smallest element is 3, so return 3.

Summary:

By using in-order traversal, we can efficiently find the k-th smallest element in a binary search tree.
This approach uses a stack to simulate recursion, making the code more concise and easier to understand.

Post Views: 31

CODEBITWAVE