Buttercola: Leetcode: Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Hint:

Try to utilize the property of a BST.
What if you could modify the BST node's structure?
The optimal runtime complexity is O(height of BST).

A similar post can be found at : http://buttercola.blogspot.com/2014/10/facebook-print-n-th-node-in-binary-tree.html

Code (Java):

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int counter = 0;
    private boolean found = false;
    private int val = Integer.MIN_VALUE;
    public int kthSmallest(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
         
        kthSmallestHelper(root, k);
         
        return val;
    }
     
    private void kthSmallestHelper(TreeNode root, int k) {
        if (root == null) {
            return;
        }
         
        if (!found) {
            kthSmallestHelper(root.left, k);
        }
         
        counter++;
        if (counter == k) {
            found = true;
            val = root.val;
        }
         
        if (!found) {
            kthSmallestHelper(root.right, k);
        }
    }
}

An O(h) solution:
If the BST node's structure can be modified. We let each node maintain the number of nodes of its left subtree. Therefore, for each node, we can compare k with the number of its subtree.

Code (Java):

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
         
        int leftNodes = getNumberNodes(root.left);
        if(k == leftNodes + 1) {
            return root.val;
        } else if (k > leftNodes + 1) {
            return kthSmallest(root.right, k - leftNodes - 1);
        } else {
            return kthSmallest(root.left, k);
        }
    }
     
    private int getNumberNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
         
        return getNumberNodes(root.left) + getNumberNodes(root.right) + 1;
    }
}

Update on 4/29/19:

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
 
public class Solution {
    /**
     * @param root: the given BST
     * @param k: the given k
     * @return: the kth smallest element in BST
     */
    public int kthSmallest(TreeNode root, int k) {
        // write your code here
        BSTNode bstRoot = buildBST(root);
 
        BSTNode p = bstRoot;
 
        while (p != null) {
            int numLeft = p.left == null ? 0 : p.left.numNodes;
            int numRight = p.right == null ? 0 : p.right.numNodes;
 
            if (k == numLeft + 1) {
                return p.val;
            }
 
            if (k <= numLeft) {
                p = p.left;
            } else {
                p = p.right;
                k = k- numLeft - 1;
            }
        }
         
        return -1;
    }
 
    private BSTNode buildBST(TreeNode root) {
        if (root == null) {
            return null;
        }
 
        BSTNode left = buildBST(root.left);
        BSTNode right = buildBST(root.right);
 
        int numNodes = (left == null ? 0 : left.numNodes) + 
                       (right == null ? 0 : right.numNodes) + 
                       1;
 
        BSTNode bstRoot = new BSTNode(root.val, numNodes);
 
        bstRoot.left = left;
        bstRoot.right = right;
 
        return bstRoot;
    }
}
 
class BSTNode {
    int val;
    int numNodes;
    BSTNode left, right;
 
    public BSTNode(int val, int numNodes) {
        this.val = val;
        this.numNodes = numNodes;
        left = right = null;
    }
}

Buttercola

Thursday, August 20, 2015

Leetcode: Kth Smallest Element in a BST

No comments:

Post a Comment