Kth Smallest Element in a BST medium

Problem Statement

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

Example 1:

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

Example 2:

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

Steps and Explanation

The key to efficiently solving this problem is leveraging the inherent properties of a Binary Search Tree (BST). In a BST, the left subtree contains nodes with values smaller than the root, and the right subtree contains nodes with values larger than the root. We can use an inorder traversal to visit the nodes in ascending order. The k^th smallest element will be the k^th node visited during this traversal.

Instead of performing a full inorder traversal and storing all the nodes, we can use an iterative approach with a stack to keep track of the nodes to visit. This approach avoids unnecessary space usage, especially for large trees.

The algorithm works as follows:

1. Initialization: Create an empty stack stack. Start at the root node.
2. Iteration: While the stack is not empty or the current node is not null:
   • If the current node is not null: push the current node onto the stack and move to its left child (to visit smaller nodes first).
   • Otherwise (the stack is not empty): pop a node from the stack. Decrement k. If k becomes 0, the popped node's value is the k^th smallest element. Otherwise, move to the popped node's right child (to explore larger values).
3. Return: Return the value of the k^th smallest node.

Code

using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public int KthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode curr = root;

        while (stack.Count > 0 || curr != null) {
            while (curr != null) {
                stack.Push(curr);
                curr = curr.left;
            }

            curr = stack.Pop();
            k--;
            if (k == 0) {
                return curr.val;
            }
            curr = curr.right;
        }
        return -1; //Should not reach here if k is valid
    }
}

Complexity Analysis

• Time Complexity: O(H + k), where H is the height of the BST. In the worst case (a skewed tree), H can be equal to N (number of nodes), resulting in O(N) time. However, for balanced BSTs, H is log(N), making the complexity closer to O(k). The iterative approach avoids the O(N) space complexity of a recursive inorder traversal.

• Space Complexity: O(H), where H is the height of the BST. This is due to the stack which stores at most H nodes in the worst case (skewed tree). For a balanced tree, this would be O(log N).