DAY 65 - Kth Smallest Element in a BST

Hi Guys! Nayan this side and welcome to 65'th day of 100DaysOfCode Challenge. I guess we are 2/3rd done in this journey as of next article. It has been the most consistent I have ever been and I am really loving coding and programming at the moment.

Let's get to today's question. We are going to solve another Binary Search Tree Question.

Question: Kth Smallest Element in a BST

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

Intuition:

• I have already talked about Binary Search Trees in one of my previous articles but To give a one line definition again. A Binary Search tree is a binary tree which contains all elements less than the root in it's left subtree and all elements greater in it's right subtree. Every subtree should also be a BST.

• So from the properties, we can safely observe that the values which are smaller will lie on the left side and greater on the right side. Which means we will first need to traverse our left subtree for answer.

• One more property of a BST is that If we do the inorder traversal of a Binary Tree it will give us all it's elements in a sorted increasing order manner.

• Using this property we just need to find out that kth element in the order traversal and we have got our answer.

Algorithm and Code:

Algorithm

The algorithm follows a recursive approach to traverse the binary tree and find the kth smallest element. Let's dive into the key components of the code:

1. helper Function:
   The helper function is a recursive function that traverses the binary tree in an inorder fashion, effectively visiting nodes in ascending order. Here's how it works:

   • If the root node is NULL, the function returns without any action.
   • The function first traverses the left subtree by calling helper(root->left, k, result).
   • The value of k is decremented, effectively tracking the number of nodes visited so far.
   • When k reaches 0, the result is updated with the current node's value, and the function returns.
   • The function then traverses the right subtree by calling helper(root->right, k, result).

2. kthSmallest Function:
   The kthSmallest function initializes a variable result to store the kth smallest element's value. It calls the helper function to traverse the binary tree and update result when k becomes 0.

Complexity Analysis

• Time: O(N)
• Space: O(N)

Explanation:

• The time complexity of the algorithm is determined by the height of the binary tree. In the worst case, when the tree is unbalanced, the time complexity is O(N), where N is the number of nodes in the tree.
• The space complexity is O(H), where H is the height of the binary tree, due to the recursive stack used for traversing.

Code:

void helper(TreeNode* root, int& k, int& result) {
        if (root == NULL)
            return;

        helper(root->left, k, result);
        k--;

        if (k == 0) {
            result = root->val;
            return;
        }

        helper(root->right, k, result);
    }

    int kthSmallest(TreeNode* root, int k) {
        int result = -1; // Initialize result to a default value
        helper(root, k, result);
        return result;
    }

Thanks for reading!. Feel free to leave back constructive criticism.