DEV Community

codingpineapple
codingpineapple

Posted on

230. Kth Smallest Element in a BST (javascript solution)

Description:

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

Solution:

Time Complexity : O(n)
Space Complexity: O(n)

// Use DFS to add values to an array
// Return the kth index of that array
var kthSmallest = function(root, k) {
    const values = []

    // DFS function
    function dfs(root, values) {
        if(root.left) dfs(root.left, values)
        values.push(root.val)
        if(root.right) dfs(root.right, values)
    }

    // Run dfs and populate array of values
    dfs(root, values)

    return values[k-1]
};
Enter fullscreen mode Exit fullscreen mode

Top comments (0)