Java Modified Binary Search Tree Solution


  • 0
    Y

    I understand that the BST is not balanced. The worst case would be O(N^2). Please feel free to give any suggestion or comments. Any one got any idea on coding style? I don't think this lengthy for loop will be a good idea. However, my method for counting min and max are different. Insert is also different.

    Basically, the TreeNode maintains 3 additional variables, noOfLeft, noOfRight and noOfSelf. noOfLeft means the how many nodes on the left branch. noOfRight has similar meaning. noOfSelf means how many duplicate nodes.

    public int countRangeSum(int[] nums, int lower, int upper) {
        int len;
        if (nums == null || (len = nums.length) <= 0) {
            return 0;
        } else if (lower > upper) {
            return 0;
        }
        
        int result = 0;
        long sum = nums[0];
        if (sum >= lower && sum <= upper) {
            result++;
        }
        TreeNode root = new TreeNode(sum);
        for (int i = 1; i < len; i++) {
            sum += nums[i];
            if (sum >= lower && sum <= upper) {
                result++;
            }
            long max = sum - lower;
            long min = sum - upper;
            
            TreeNode node = null;
            int count = i;
            // Find max
            node = root;
            while (node != null) {
                long value = node.value;
                if (max > value) {
                    node = node.right;
                } else if (max < value) {
                    count -= node.noOfSelf + node.noOfRight;
                    node = node.left;
                } else {
                    count -= node.noOfRight;
                    break;
                }
            }
            
            // Find min
            node = root;
            while (node != null) {
                long value = node.value;
                if (min > value) {
                    count -= node.noOfSelf + node.noOfLeft;
                    node = node.right;
                } else if (min < value) {
                    node = node.left;
                } else {
                    count -= node.noOfLeft;
                    break;
                }
            }
            
            result += count;
            
            // Insert this node.
            node = root;
            while (node != null) {
                long value = node.value;
                if (sum > value) {
                    node.noOfRight++;
                    if (node.right != null) {
                        node = node.right;
                    } else {
                        node.right = new TreeNode(sum);
                        break;
                    }
                } else if (sum < value) {
                    node.noOfLeft++;
                    if (node.left != null) {
                        node = node.left;
                    } else {
                        node.left = new TreeNode(sum);
                        break;
                    }
                } else {
                    node.noOfSelf++;
                    break;
                }
            }
        }
        
        return result;
    }
    
    
    class TreeNode {
        long value;
        TreeNode left;
        TreeNode right;
        int noOfLeft;
        int noOfRight;
        int noOfSelf;
        
        TreeNode(long value) {
            this.value = value;
            this.noOfSelf = 1;
        }
    }

  • 0
    Y

    A little refined version with more explanation on variables.

    public int countRangeSum(int[] nums, int lower, int upper) {
        int len;
        if (nums == null || (len = nums.length) <= 0) {
            return 0;
        } else if (lower > upper) {
            return 0;
        }
        
        int result = 0;
        long sum = 0;
        TreeNode root = new TreeNode(sum);
        for (int i = 0; i < len; i++) {
            sum += nums[i];
            long max = sum - lower;
            long min = sum - upper;
            
            TreeNode node = null;
            // Possible combinations.
            int count = i + 1;
            // Find max
            node = root;
            while (node != null) {
                long value = node.value;
                if (max > value) {
                    node = node.right;
                } else if (max < value) {
                    // Ignore the right parts.
                    count -= node.noOfSelf + node.noOfRight;
                    node = node.left;
                } else {
                    count -= node.noOfRight;
                    break;
                }
            }
            
            // Find min
            node = root;
            while (node != null) {
                long value = node.value;
                if (min > value) {
                    // Ignore the left parts.
                    count -= node.noOfSelf + node.noOfLeft;
                    node = node.right;
                } else if (min < value) {
                    node = node.left;
                } else {
                    count -= node.noOfLeft;
                    break;
                }
            }
            
            result += count;
            
            // Insert this node.
            node = root;
            while (node != null) {
                long value = node.value;
                if (sum > value) {
                    node.noOfRight++;
                    if (node.right != null) {
                        node = node.right;
                    } else {
                        node.right = new TreeNode(sum);
                        break;
                    }
                } else if (sum < value) {
                    node.noOfLeft++;
                    if (node.left != null) {
                        node = node.left;
                    } else {
                        node.left = new TreeNode(sum);
                        break;
                    }
                } else {
                    node.noOfSelf++;
                    break;
                }
            }
        }
        
        return result;
    }
    
    
    class TreeNode {
        long value;
        TreeNode left;
        TreeNode right;
        int noOfLeft;
        int noOfRight;
        int noOfSelf;
        
        TreeNode(long value) {
            this.value = value;
            this.noOfSelf = 1;
        }
    }

  • 0

    Balancing trees immediately makes me think of red-black trees, but then it would be tricky to keep track of those noOf counts when performing tree rotations.


Log in to reply
 

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