What if you could modify the BST node's structure?


  • 77
    W

    If we could add a count field in the BST node class, it will take O(n) time when we calculate the count value for the whole tree, but after that, it will take O(logn) time when insert/delete a node or calculate the kth smallest element.

       public class Solution {
            public int kthSmallest(TreeNode root, int k) {
                TreeNodeWithCount rootWithCount = buildTreeWithCount(root);
                return kthSmallest(rootWithCount, k);
            }
            
            private TreeNodeWithCount buildTreeWithCount(TreeNode root) {
                if (root == null) return null;
                TreeNodeWithCount rootWithCount = new TreeNodeWithCount(root.val);
                rootWithCount.left = buildTreeWithCount(root.left);
                rootWithCount.right = buildTreeWithCount(root.right);
                if (rootWithCount.left != null) rootWithCount.count += rootWithCount.left.count;
                if (rootWithCount.right != null) rootWithCount.count += rootWithCount.right.count;
                return rootWithCount;
            }
            
            private int kthSmallest(TreeNodeWithCount rootWithCount, int k) {
                if (k <= 0 || k > rootWithCount.count) return -1;
                if (rootWithCount.left != null) {
                    if (rootWithCount.left.count >= k) return kthSmallest(rootWithCount.left, k);
                    if (rootWithCount.left.count == k-1) return rootWithCount.val;
                    return kthSmallest(rootWithCount.right, k-1-rootWithCount.left.count);
                } else {
                    if (k == 1) return rootWithCount.val;
                    return kthSmallest(rootWithCount.right, k-1);
                }
            }
            
            class TreeNodeWithCount {
                int val;
                int count;
                TreeNodeWithCount left;
                TreeNodeWithCount right;
                TreeNodeWithCount(int x) {val = x; count = 1;};
            }
        }

  • 5

    I don't see any balancing efforts, so this still takes O(n), not O(log n).


  • 0
    J

    excellent idea and it works,once you rebuild the tree with new countnode, it takes O(lgn) to find the desired value. You just need to update the relevant count value after insertion and deletion. it does not take extra time.


  • 0
    R

    complicated solution!!


  • 7
    D

    i think it is simpler to record the node order directly

    class TreeNodeWithCount {
    public:
        int val;
        int count;
        TreeNodeWithCount* left;
        TreeNodeWithCount* right;
        TreeNodeWithCount(int x) {val = x; count = 1;left=NULL;right=NULL;}
    };
    class Solution {
    public:
        TreeNodeWithCount* buildTreeWithCount(TreeNode* root,int& n) {
            if (!root) return NULL;
            TreeNodeWithCount* rootWithCount = new TreeNodeWithCount(root->val);
            rootWithCount->left = buildTreeWithCount(root->left,n);
            rootWithCount->count = n++;
            rootWithCount->right = buildTreeWithCount(root->right,n);
            return rootWithCount;
        }
     
        int kthSmallest(TreeNodeWithCount* rootWithCount, int k) {
            if (rootWithCount->count > k) 
                return kthSmallest(rootWithCount->left, k);
            else if (rootWithCount->count == k) 
                return rootWithCount->val;
            else
                return kthSmallest(rootWithCount->right, k);
        }
     
         
        int kthSmallest(TreeNode* root, int k) {
    		int n = 1;
            TreeNodeWithCount* rootWithCount = buildTreeWithCount(root,n);
            return kthSmallest(rootWithCount, k);
        }
    };

  • 0
    J

    It's not O(log n). O(h) instead. h is the height of the BST.


  • 0
    S

    if nodes are added and deleted, the order will change, right?


  • 0
    D

    what do you mean by "it does not take extra time."
    how to deal with delete and add? U still need O(n) to update count?


  • 8
    W

    Right solution, but not efficient.
    What you stored in TreeNodeWithCount is the order of its value, not the count of its children. So you will not achieve the target which takes O(logn) time when insert/delete a node or calculate the kth smallest element after.
    For example, if a number less than the min value of the BST inserted, you will have to change the order of all the nodes. This will cost O(n) time, not O(logn);


  • 0
    N

    @wfxr
    inserting the number will update every nodes' information but the average time complexity of insert/delete operation of a BST is still O(logn). Also, insert/delete operation itself will still cost the time.


  • 2
    Z

    Hi! My solution also performs O(log(n)) in average for potentially insert/delete/findKth methods. But it is based on counting number of nodes in left branches only and uses hash map instead of new tree structure.

    public class Solution {
        Map<Integer, Integer> map;
        public int kthSmallest(TreeNode root, int k) {
            map = new HashMap<>();
            initMap(root);
            TreeNode node = root;
            int val = map.get(node.val);
            while(val != k-1){
                if(val >= k){
                    node = node.left;
                } else {
                    k-=val+1;
                    node = node.right;
                }
                val = map.get(node.val);
            }
            return node.val;
        }
        private int initMap(TreeNode root){
            int res = 1;
            if(root.left == null) {
                map.put(root.val, 0);
            } else {
                int left=initMap(root.left);
                map.put(root.val, left);
                res+=left;
            }
            if(root.right == null){
                return res;
            }
            return res+initMap(root.right);
        }
    }

  • 0
    F

    @joe-cai Why this is down voted? The given BST may not be balanced at all, so the worst case running time could still be O(n), which is the height of the tree.


  • -1

    Here is my 4 methods (binary search + recursive + iterative + Morris) solution with very detail explanation
    leetcode 230


  • 0

    @monkeykingyan What does that have to do with this topic? Did you just meaninglessly triple-spam into the top-voted topics? And your complexities for your first three solutions are all wrong.


  • 0

    @ManuelP Thank you for your complaint. first, I want to clarify that I don't have other goals to post my solution.
    I will modify my solutions and join the discussion topic. And I am happy that you find problems in my codes and hope I can learn something from you. Best wishes! : )


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.