Jobs

Interviews

Discussions

Kth Smallest Element in a BST

Medium

Amazon

6 views

Topics:

TreesRecursion

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. For example:

If root = [3,1,4,null,2] and k = 1, the output should be 1.
If root = [5,3,6,2,4,null,null,1] and k = 3, the output should be 3.

Constraints:

The number of nodes in the tree is n.
1 <= k <= n <= 10^4
0 <= Node.val <= 10^4

Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

Kth Smallest Element in a BST

Medium

Amazon

6 views

Topics:

TreesRecursion

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. For example:

If root = [3,1,4,null,2] and k = 1, the output should be 1.
If root = [5,3,6,2,4,null,null,1] and k = 3, the output should be 3.

Constraints:

The number of nodes in the tree is n.
1 <= k <= n <= 10^4
0 <= Node.val <= 10^4

Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that the nodes in the BST can hold?
What should I return if k is larger than the number of nodes in the BST?
Can the BST be empty, and if so, what should I return?
Are duplicate values allowed in the BST, and if so, how should they be handled when determining the kth smallest element?
Is it guaranteed that k will always be a valid positive integer greater than 0?

Brute Force Solution

Approach

The goal is to find the Kth smallest element in a special tree structure. The brute force strategy involves examining every element in the tree to determine which one is the Kth smallest.

Here's how the algorithm would work step-by-step:

First, gather all the elements from the tree.
Then, arrange all the elements in increasing order from smallest to largest.
Finally, pick the element located at the Kth position in the ordered list; this element is the Kth smallest element in the tree.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def kth_smallest_element_brute_force(root, k):
    all_elements = []

    def inorder_traversal(node):
        if node:
            inorder_traversal(node.left)
            all_elements.append(node.val)
            inorder_traversal(node.right)

    # Collect all elements from the BST using inorder traversal.
    inorder_traversal(root)

    # Sorting ensures elements are ordered smallest to largest.
    all_elements.sort()

    # Return the kth smallest element, adjusting for 0-based indexing.
    return all_elements[k - 1]

Big(O) Analysis

Time Complexity

O(n log n) – The first step involves traversing the entire Binary Search Tree (BST) to gather all n elements. This traversal takes O(n) time. The second step sorts these n elements. Efficient sorting algorithms like merge sort or quicksort have a time complexity of O(n log n). The final step of accessing the element at the Kth position in the sorted list takes O(1) time. Therefore, the dominant operation is sorting, resulting in a total time complexity of O(n log n).

Space Complexity

O(N) – The provided solution first gathers all elements from the Binary Search Tree into a list. This list stores the elements before they are sorted. Therefore, the auxiliary space required is proportional to the number of nodes in the BST, which we denote as N. This results in an auxiliary space usage of O(N).

Optimal Solution

Approach

The best way to find the kth smallest element in a binary search tree is to take advantage of its ordered nature. We can walk through the tree in a special order that lets us count the elements as we go, stopping as soon as we reach the kth one. This avoids looking at parts of the tree that don't matter.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree.
Repeatedly go as far left as possible. As you move left, keep a running count of the nodes you've seen so far.
Once you can't go left anymore, you've found the smallest element you haven't already counted. Check if this is the kth element.
If it's the kth element, you're done! You've found your answer.
If not, go one step to the right. This moves you to an element bigger than the one you just considered.
Now, repeat the process of going as far left as possible from this new position, counting the nodes you visit.
Keep doing this 'left, process, right' pattern until you've found the kth element.

Code Implementation

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def kth_smallest(root, k_value):
    stack = []
    current_node = root
    nodes_visited_count = 0

    while current_node or stack:
        # Traverse to the leftmost node.
        while current_node:
            stack.append(current_node)
            current_node = current_node.left

        current_node = stack.pop()
        # Increment count; it's the next smallest.
        nodes_visited_count += 1

        # Found the kth smallest element.
        if nodes_visited_count == k_value:
            return current_node.value

        # Move to the right subtree.
        current_node = current_node.right

    return None

Big(O) Analysis

Time Complexity

O(n) – The algorithm performs an inorder traversal of the Binary Search Tree (BST). In the worst-case scenario, where the kth smallest element is the last element visited in the inorder traversal, the algorithm will visit each node in the BST exactly once. Therefore, the time complexity is directly proportional to the number of nodes in the BST, denoted as 'n'. Hence, the overall time complexity is O(n).

Space Complexity

O(H) – The algorithm's space complexity is determined by the depth of the recursion stack, where H represents the height of the binary search tree. In the worst case (e.g., a skewed tree), the recursion may go as deep as N, where N is the number of nodes in the tree, resulting in O(N) space. However, in a balanced tree, the height H is logarithmic with respect to N, leading to O(log N) space. Thus, the space complexity is O(H).

Edge Cases

Case	How to Handle
Empty BST (root is null)	Return null or a predefined error value (e.g., -1) if the BST is empty as there is no kth smallest element.
k is less than 1	Throw an IllegalArgumentException or return a special value indicating invalid input, since k must be a positive integer.
k is greater than the number of nodes in the BST	Return null or a predefined error value (e.g., -1) as the kth smallest element does not exist.
BST with all identical values	The in-order traversal will correctly identify the kth smallest element regardless of identical values.
BST with negative and positive values	The in-order traversal algorithm works correctly with both negative and positive values as it only relies on the ordering property of the BST.
BST with very large or very small values that could lead to integer overflow	Use `long` data type where applicable to avoid potential integer overflow issues during calculations related to node values or number of nodes.
Extremely unbalanced BST (skewed tree)	The iterative inorder traversal approach should still work, but for a very skewed tree the space complexity might reach O(n) in the worst case instead of O(h), with h being the height of the tree.
k is equal to 1 (find the minimum value)	The algorithm should correctly return the leftmost node of the BST when k=1.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that the nodes in the BST can hold?
What should I return if k is larger than the number of nodes in the BST?
Can the BST be empty, and if so, what should I return?
Are duplicate values allowed in the BST, and if so, how should they be handled when determining the kth smallest element?
Is it guaranteed that k will always be a valid positive integer greater than 0?

Brute Force Solution

Approach

The goal is to find the Kth smallest element in a special tree structure. The brute force strategy involves examining every element in the tree to determine which one is the Kth smallest.

Here's how the algorithm would work step-by-step:

First, gather all the elements from the tree.
Then, arrange all the elements in increasing order from smallest to largest.
Finally, pick the element located at the Kth position in the ordered list; this element is the Kth smallest element in the tree.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def kth_smallest_element_brute_force(root, k):
    all_elements = []

    def inorder_traversal(node):
        if node:
            inorder_traversal(node.left)
            all_elements.append(node.val)
            inorder_traversal(node.right)

    # Collect all elements from the BST using inorder traversal.
    inorder_traversal(root)

    # Sorting ensures elements are ordered smallest to largest.
    all_elements.sort()

    # Return the kth smallest element, adjusting for 0-based indexing.
    return all_elements[k - 1]

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the very top of the tree.
Repeatedly go as far left as possible. As you move left, keep a running count of the nodes you've seen so far.
Once you can't go left anymore, you've found the smallest element you haven't already counted. Check if this is the kth element.
If it's the kth element, you're done! You've found your answer.
If not, go one step to the right. This moves you to an element bigger than the one you just considered.
Now, repeat the process of going as far left as possible from this new position, counting the nodes you visit.
Keep doing this 'left, process, right' pattern until you've found the kth element.

Code Implementation

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def kth_smallest(root, k_value):
    stack = []
    current_node = root
    nodes_visited_count = 0

    while current_node or stack:
        # Traverse to the leftmost node.
        while current_node:
            stack.append(current_node)
            current_node = current_node.left

        current_node = stack.pop()
        # Increment count; it's the next smallest.
        nodes_visited_count += 1

        # Found the kth smallest element.
        if nodes_visited_count == k_value:
            return current_node.value

        # Move to the right subtree.
        current_node = current_node.right

    return None

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty BST (root is null)	Return null or a predefined error value (e.g., -1) if the BST is empty as there is no kth smallest element.
k is less than 1	Throw an IllegalArgumentException or return a special value indicating invalid input, since k must be a positive integer.
k is greater than the number of nodes in the BST	Return null or a predefined error value (e.g., -1) as the kth smallest element does not exist.
BST with all identical values	The in-order traversal will correctly identify the kth smallest element regardless of identical values.
BST with negative and positive values	The in-order traversal algorithm works correctly with both negative and positive values as it only relies on the ordering property of the BST.
BST with very large or very small values that could lead to integer overflow	Use `long` data type where applicable to avoid potential integer overflow issues during calculations related to node values or number of nodes.
Extremely unbalanced BST (skewed tree)	The iterative inorder traversal approach should still work, but for a very skewed tree the space complexity might reach O(n) in the worst case instead of O(h), with h being the height of the tree.
k is equal to 1 (find the minimum value)	The algorithm should correctly return the leftmost node of the BST when k=1.