Kth Smallest and Largest element in BST

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 its 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.

Approach

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).
Perform a 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.
After completing the traversal, proceed to sort the list in ascending order, ensuring that the values are ordered from the smallest to the largest.
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.
To determine the Kth largest element, retrieve the element positioned at the index 'array.length - k' within the sorted array.
Finally, return a pair of elements: the Kth smallest and the Kth largest, as determined by the aforementioned steps.

Dry Run

Solution

#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);
        
        // Sort the values
        sort(values.begin(), values.end());
        
        // 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;
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

// Definition for a binary tree node.
public class TreeNode {
     int data;
     TreeNode left;
     TreeNode right;
     TreeNode(int val) { data = val; left = null; right = null; }
}

class Solution {
    // Helper function to perform an in-order traversal of the BST
    private void inorderTraversal(TreeNode node, List<Integer> values) {
        if (node != null) {
            inorderTraversal(node.left, values);
            values.add(node.data);
            inorderTraversal(node.right, values);
        }
    }

    public List<Integer> kLargesSmall(TreeNode root, int k) {
        // List to store the node values
        List<Integer> values = new ArrayList<>();
        // Perform in-order traversal and collect values
        inorderTraversal(root, values);
        
        // Sort the values
        Collections.sort(values);
        
        // Find the kth smallest and kth largest values
        int kth_smallest = values.get(k - 1);
        int kth_largest = values.get(values.size() - k);
        
        List<Integer> result = new ArrayList<>();
        result.add(kth_smallest);
        result.add(kth_largest);
        
        return result;
    }

    // Main method to demonstrate the function
    public static void main(String[] args) {
        // 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 = new Solution();
        int k = 1;
        List<Integer> result = solution.kLargesSmall(root, k);
        
        System.out.println(result); // Output: [1, 4]
    }
}
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.data = val
        self.left = left
        self.right = right

class Solution:
    def kLargesSmall(self, root, k):
        # Helper function to perform an in-order traversal of the BST
        def inorder_traversal(node, values):
            if node:
                inorder_traversal(node.left, values)
                values.append(node.data)
                inorder_traversal(node.right, values)
        
        # List to store the node values
        values = []
        # Perform in-order traversal and collect values
        inorder_traversal(root, values)
        
        # Sort the values
        values.sort()
        
        # Find the kth smallest and kth largest values
        kth_smallest = values[k - 1]
        kth_largest = values[-k]
        
        return [kth_smallest, kth_largest]

# Example usage:
# Constructing the tree: [3,1,4,null,2]
root = TreeNode(3)
root.left = TreeNode(1)
root.left.right = TreeNode(2)
root.right = TreeNode(4)

solution = Solution()
k = 1
print(solution.kLargesSmall(root, k))  # Output: [1, 4]
// Definition for a binary tree node.
 class TreeNode {
      constructor(val = 0, left = null, right = null) {
          this.data = val;
          this.left = left;
          this.right = right;
  }
 }

class Solution {
    // Helper function to perform an in-order traversal of the BST
    inorderTraversal(node, values) {
        if (node) {
            this.inorderTraversal(node.left, values);
            values.push(node.data);
            this.inorderTraversal(node.right, values);
        }
    }

    kLargesSmall(root, k) {
        // Array to store the node values
        let values = [];
        // Perform in-order traversal and collect values
        this.inorderTraversal(root, values);
        
        // Sort the values
        values.sort((a, b) => a - b);
        
        // Find the kth smallest and kth largest values
        let kth_smallest = values[k - 1];
        let kth_largest = values[values.length - k];
        
        return [kth_smallest, kth_largest];
    }
}

// Main method to demonstrate the function
function main() {
    // Constructing the tree: [3, 1, 4, null, 2]
    let root = new TreeNode(3);
    root.left = new TreeNode(1);
    root.left.right = new TreeNode(2);
    root.right = new TreeNode(4);
    
    let solution = new Solution();
    let k = 1;
    let result = solution.kLargesSmall(root, k);
    
    console.log(result); // Output: [1, 4]
}

main();

Complexity Analysis

Time Complexity O(N log N), since the code performs an in-order traversal of the BST (O(N)) and then sorts the values (O(N log N)).

Space Complexity O(N), since the code stores all the node values in a list, where N is the number of nodes in the BST.

Intuition

When aiming to identify the Kth smallest and largest elements within a Binary Search Tree (BST), one strategy strategy involves leveraging the inorder traversal technique. This method, which adheres to the Left Node Right sequence, inherently orders the tree's elements in ascending order. The unique structure of a BST, where the left child node holds a value smaller than its parent node and the right child node holds a value greater than the parent, guarantees that an inorder traversal will produce a sorted sequence. This characteristic significantly helps the task of extracting the Kth smallest and largest elements, making the process both efficient and straightforward.

Methodology

Begin by initializing an array that will be used to store the values of the nodes within the BST.
Execute an inorder traversal of the BST, during which each node's value is sequentially added to the array.
Utilize a counter to monitor the progress of the traversal, particularly focusing on the Kth position, thereby eliminating the necessity for an additional data structure.
To determine the Kth smallest element, observe the counter, and upon reaching the value of K, record the current node's value as the Kth smallest.
For identifying the Kth largest element, conduct a reverse inorder traversal, starting from the root node. As each node is visited, increment a counter to track the number of visited nodes. The traversal should follow the order: right subtree first, then the current node, and finally the left subtree.
Ultimately, return the values corresponding to the Kth smallest and Kth largest elements as derived from the aforementioned steps.

Dry Run

Solution

#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:
    // Function to find the kth smallest element
    int kthSmallest(TreeNode* root, int k) {
        this->k = k;
        this->result = -1;
        inorder(root);
        return result;
    }

    // Function to find the kth largest element
    int kthLargest(TreeNode* root, int k) {
        this->k = k;
        this->result = -1;
        reverse_inorder(root);
        return result;
    }

    // Function to return kth smallest and kth largest elements
    vector<int> kLargesSmall(TreeNode* root, int k) {
        return {kthSmallest(root, k), kthLargest(root, k)};
    }

private:
    int k;
    int result;

    // Helper function for inorder traversal
    void inorder(TreeNode* node) {
        if (node != nullptr) {
            inorder(node->left);
            if (--k == 0) {
                result = node->data;
                return;
            }
            inorder(node->right);
        }
    }

    // Helper function for reverse inorder traversal
    void reverse_inorder(TreeNode* node) {
        if (node != nullptr) {
            reverse_inorder(node->right);
            if (--k == 0) {
                result = node->data;
                return;
            }
            reverse_inorder(node->left);
        }
    }
};

// Main method to demonstrate the function
int main() {
    // Constructing the tree: [3, 1, 4, nullptr, 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);
    
    // Output the result
    cout << "[" << result[0] << ", " << result[1] << "]" << endl; // Output: [1, 4]
    
    return 0;
}
import java.util.ArrayList;
import java.util.List;

// Definition for a binary tree node.
 public class TreeNode {
     int data;
     TreeNode left;
     TreeNode right;
     TreeNode(int val) { data = val; left = null; right = null; }
 }

class Solution {
    private int k;
    private int result;

    // Function to find the kth smallest element
    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        this.result = -1;
        inorder(root);
        return result;
    }

    // Helper function for inorder traversal
    private void inorder(TreeNode node) {
        if (node != null) {
            inorder(node.left);
            if (--k == 0) {
                result = node.data;
                return;
            }
            inorder(node.right);
        }
    }

    // Function to find the kth largest element
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        this.result = -1;
        reverseInorder(root);
        return result;
    }

    // Helper function for reverse inorder traversal
    private void reverseInorder(TreeNode node) {
        if (node != null) {
            reverseInorder(node.right);
            if (--k == 0) {
                result = node.data;
                return;
            }
            reverseInorder(node.left);
        }
    }

    // Function to return kth smallest and kth largest elements
    public List<Integer> kLargesSmall(TreeNode root, int k) {
        List<Integer> result = new ArrayList<>();
        result.add(kthSmallest(root, k));
        result.add(kthLargest(root, k));
        return result;
    }

    // Main method to demonstrate the function
    public static void main(String[] args) {
        // 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 = new Solution();
        int k = 1;
        List<Integer> result = solution.kLargesSmall(root, k);

        // Output the result
        System.out.println(result); // Output: [1, 4]
    }
}
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.data = val
        self.left = left
        self.right = right

class Solution:
    # Function to find the kth smallest element
    def kthSmallest(self, root, k):
        self.k = k
        self.result = None
        self.inorder(root)
        return self.result

    # Helper function for inorder traversal
    def inorder(self, node):
        if node is not None:
            self.inorder(node.left)
            self.k -= 1
            if self.k == 0:
                self.result = node.data
                return
            self.inorder(node.right)

    # Function to find the kth largest element
    def kthLargest(self, root, k):
        self.k = k
        self.result = None
        self.reverse_inorder(root)
        return self.result

    # Helper function for reverse inorder traversal
    def reverse_inorder(self, node):
        if node is not None:
            self.reverse_inorder(node.right)
            self.k -= 1
            if self.k == 0:
                self.result = node.data
                return
            self.reverse_inorder(node.left)

    # Function to return kth smallest and kth largest elements
    def kLargesSmall(self, root, k):
        return [self.kthSmallest(root, k), self.kthLargest(root, k)]

# Example usage
if __name__ == "__main__":
    # Constructing the tree: [3, 1, 4, None, 2]
    root = TreeNode(3)
    root.left = TreeNode(1)
    root.left.right = TreeNode(2)
    root.right = TreeNode(4)
    
    solution = Solution()
    k = 1
    result = solution.kLargesSmall(root, k)
    
    print(result)  # Output: [1, 4]
// Definition for a binary tree node.
  class TreeNode {
       constructor(val = 0, left = null, right = null) {
           this.data = val;
           this.left = left;
           this.right = right;
       }
  }
 
class Solution {
    constructor() {
        this.k = 0;
        this.result = null;
    }

    // Function to find the kth smallest element
    kthSmallest(root, k) {
        this.k = k;
        this.result = null;
        this.inorder(root);
        return this.result;
    }

    // Helper function for inorder traversal
    inorder(node) {
        if (node !== null) {
            this.inorder(node.left);
            this.k -= 1;
            if (this.k === 0) {
                this.result = node.data;
                return;
            }
            this.inorder(node.right);
        }
    }

    // Function to find the kth largest element
    kthLargest(root, k) {
        this.k = k;
        this.result = null;
        this.reverseInorder(root);
        return this.result;
    }

    // Helper function for reverse inorder traversal
    reverseInorder(node) {
        if (node !== null) {
            this.reverseInorder(node.right);
            this.k -= 1;
            if (this.k === 0) {
                this.result = node.data;
                return;
            }
            this.reverseInorder(node.left);
        }
    }

    // Function to return kth smallest and kth largest elements
    kLargesSmall(root, k) {
        return [this.kthSmallest(root, k), this.kthLargest(root, k)];
    }
}

// Main function to demonstrate the function
function main() {
    // Constructing the tree: [3, 1, 4, null, 2]
    let root = new TreeNode(3);
    root.left = new TreeNode(1);
    root.left.right = new TreeNode(2);
    root.right = new TreeNode(4);

    let solution = new Solution();
    let k = 1;
    let result = solution.kLargesSmall(root, k);

    // Output the result
    console.log(result); // Output: [1, 4]
}

main();

Complexity Analysis

Time Complexity O(N), where N is the number of nodes in the binary tree. The reason is that in the worst-case scenario, the inorder and reverse inorder traversals visit each node exactly once.

Space Complexity O(H), where H is the height of the binary tree.

Problem List

Kth Smallest and Largest element in BST

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Intuition

Methodology

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code