Problem Statement

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

Examples

Example 1:

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

Explanation: The 1st smallest value in given BST is 1.
The 1st largest value in given BST is 4.

Example 2:

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

Explanation: The 3rd largest value in the BST is 3.
The 3rd largest value int BST is 3.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

To find the Kth smallest and largest elements in a Binary Search Tree (BST) using a brute force method, a simple approach is to traverse the tree and collect all its node values in a list. or a vector. By sorting this list, the desired elements can be easily retrieved based on their indices. To find the Kth smallest element, access the element at index ‘k - 1’ in the array, and to find the Kth largest element, access the element at index ‘array.length - K’ index. Note that it is preferred to consider the inorder traversal of the BST because it will come out to be sorted already.

Approach:

1. Begin by creating a list or vector to serve as a storage container for the values of the nodes present in the Binary Search Tree (BST).
2. Perform an inorder traversal of the BST utilizing the depth-first search (DFS) technique, during which each node's value should be added to the previously initialized array.
3. To identify the Kth smallest element, retrieve the element located at the index 'k - 1' of the sorted array, keeping in mind that array indexing begins at zero.
4. To determine the Kth largest element, retrieve the element positioned at the index 'array.length - k' within the sorted array.
5. Finally, return a pair of elements: the Kth smallest and the Kth largest, as determined by the aforementioned steps.

Code:

#include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node.
 struct TreeNode {
     int data;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
 };
 
class Solution {
public:
    // Helper function to perform an in-order traversal of the BST
    void inorderTraversal(TreeNode* node, vector<int>& values) {
        if (node) {
            inorderTraversal(node->left, values);
            values.push_back(node->data);
            inorderTraversal(node->right, values);
        }
    }
    
    vector<int> kLargesSmall(TreeNode* root, int k) {
        // Vector to store the node values
        vector<int> values;
        // Perform in-order traversal and collect values
        inorderTraversal(root, values);
        
        // Find the kth smallest and kth largest values
        int kth_smallest = values[k - 1];
        int kth_largest = values[values.size() - k];
        
        return {kth_smallest, kth_largest};
    }
};

// Main method to demonstrate the function
int main() {
    // Constructing the tree: [3, 1, 4, null, 2]
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(1);
    root->left->right = new TreeNode(2);
    root->right = new TreeNode(4);
    
    Solution solution;
    int k = 1;
    vector<int> result = solution.kLargesSmall(root, k);
    
    cout << "[" << result[0] << ", " << result[1] << "]" << endl; // Output: [1, 4]
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N), where N is the number of nodes in the BST
  • Because the code performs an in-order traversal of the BST, which requires O(N) time.
• Space Complexity:O(N), since the code stores all the node values in a list.