Kth Smallest Element in a BST | LeetCode

To find the Kth smallest element in a BST, we can perform an inorder traversal of the tree. In an inorder traversal, the nodes are visited in non-decreasing order. By keeping track of the count of visited nodes, we can identify the Kth smallest element.

Problem Statement

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Example 1:

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

Implementation

/**p
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution {

    /**
     * @param TreeNode $root
     * @param Integer $k
     * @return Integer
     */
    function kthSmallest($root, $k) {
        $stack =[];
        $curr = $root;
         while(!empty($stack) || $curr!== null) {
            while($curr!== null){
                array_push($stack, $curr);
                $curr = $curr->left;
            }
            $curr = array_pop($stack);
            $k--;
            if($k==0) return $curr->val;
            $curr = $curr->right;
         }
        return -1;
    }
}

Explanation

1. Start with an empty stack and set the current node $curr to the root node (20).
2. Traverse to the left subtree of the current node until reaching the leftmost node (4).
   Push encountered nodes onto the stack: 20 -> 8 -> 4.
3. At node 4, encounter a null left child, stop traversing left, and pop the node.
4. Decrement k to k = 2.
5. Move to the right subtree of node 4 (no right child).
   Stack: 20 -> 8
6. Now pop 8 from stack and decrement k to k = 1
7. Traverse to the left subtree of the right child of node 8 (node 12).
   Push node 12 onto the stack and traverse to the left subtree of node 12.
   Stack: 20 -> 12
8. Push node 10 onto the stack.
   Stack: 20->12->10
9. At node 10, encounter a null left child, stop traversing left, and pop the node.
   Decrement k to k = 0.
10. Since k is now 0, return the value of node 10.

Time and Space Complexity

Time Complexity:

• In the worst-case scenario, the algorithm traverses the entire tree once, performing an inorder traversal.
• Since each node is visited once, the time complexity of the algorithm is O(n), where n is the number of nodes in the tree.

Space Complexity:

• The space complexity is determined by the additional space used by the stack during the traversal.
• In the worst-case scenario, the stack can hold all nodes of the tree if the tree is skewed.
• Therefore, the space complexity of the algorithm is O(n) in the worst case, where n is the number of nodes in the tree.
• However, in the average case, the space complexity is O(log n), where n is the number of nodes in the tree.

Conclusion

In this article, we’ve explored the concept of binary search trees and examined a PHP implementation for finding the Kth Smallest Element in BST.

Happy Coding:)