Share my Binary Search Tree solution, Java, O(nlog(n))


  • 1
    J

    Insert value into binary search tree from the end of array to the start.
    To improve the balance of BST, use O(n) to find the mid of min and max value in the array.
    Total Time Complexity O(nlogn)

    public class Solution {
    class Node {
        int count; // number of values <= this.val
        int val;
        int dup; // duplication of same value
        Node left, right;
        public Node(int val) {
            this.val = val;
        }
    }
    public List<Integer> countSmaller(int[] nums) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        
        for (int i = 0; i < nums.length; i++) {
            min = min < nums[i] ? min : nums[i];
            max = max > nums[i] ? max : nums[i];
        }
        int mid = (max - min) / 2;
        Node root = new Node(mid);
        
        for (int i = nums.length - 1; i >= 0; i--) {
            insert(root, list, nums[i], 0);
        }
        return list;
    }
    public Node insert(Node root, LinkedList<Integer> list, int val, int sum) {
        if (root == null) {
            list.addFirst(sum);
            Node cur = new Node(val);
            cur.dup = 1;
            cur.count = 1;
            return cur;
        }
        
        if (val < root.val) {
            root.left = insert(root.left, list, val, sum);
            root.count += 1;
        } else if (val == root.val) {
            sum += root.count - root.dup;
            list.addFirst(sum);
            root.dup += 1;
            root.count += 1;
        } else {
            sum += root.count;
            root.right = insert(root.right, list, val, sum);
        }
        
        return root;
    }
    

    }


Log in to reply
 

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