O(nlogn) Java solution


  • 1
    Y

    The idea is pretty straight forward: we just recursively check if the subtree is valid BST or not, if it is, we just return the result. When we recursively check from the root, the first result returned would be the largest subtree. Still trying to figure out a O(n) solution.

       public class Solution {
            public int largestBSTSubtree(TreeNode root) {
                if(root == null) {
                    return 0;
                }
                if(helper(root, Long.MIN_VALUE, Long.MAX_VALUE)) {
                    return nodeCount(root);
                }
                int left = largestBSTSubtree(root.left);
                int right = largestBSTSubtree(root.right);
                return Math.max(left, right);
            }
            
            private int nodeCount(TreeNode root) {
                if(root == null) {
                    return 0;
                }
                return nodeCount(root.left) + nodeCount(root.right) + 1;
            }
            
            private boolean helper(TreeNode root, long left, long right) {
                if(root == null) {
                    return true;
                }
                if(root.val <= left || root.val >= right) {
                    return false;
                }
                return helper(root.left, left, root.val) && helper(root.right, root.val, right);
            }
        }

  • 0
    D

    try to recursive from button to up, main the size of each subtree, you can get O(n) solution


  • 0
    Y

    but that would require a parent point right?


  • 0
    H
    This post is deleted!

  • 1

    It's not O(nlogn) but O(n^2). For example for input [1,null,2,null,...,998,null,999,null,0], which is a tree with a thousand nodes, your helper function gets called over a million times.


  • 0

    @StefanPochmann
    the hint in this problem saying it is O(nlog(n)) if reuse method from validateBinaryTree.
    But that method is O(n), so I am wondering how it be O(n
    log(n)) if reuse that one


  • 0

    @三千世界 The whole hint says:

    "You can recursively use algorithm similar to 98. Validate Binary Search Tree at each node of the tree, which will result in O(nlogn) time complexity.".

    That's pretty much what @yfcheng's above solution does. Call validation at each node of the tree, i.e., for every possible subtree. And then combine the results appropriately. If the whole tree is balanced, i.e., its height is O(log n), then this will overall cost O(n log n). Because each node is involved in O(log n) validations. That hint apparently assumes a balanced tree (which I'd say it shouldn't).


  • 0

    @StefanPochmann
    thank you, I see your point. O(nlog(n))) is a average estimate for balanced tree and if un-balanced worst case is O(n^2)


  • 0
    Y

    @StefanPochmann Could you explain a little bit why 98. Validate Binary Search Tree's time complexity is O(logn) for balanced tree? I thought it should be O(n) since it would traversal all the nodes. Thanks!


  • 0

    @yu.xiaoxixi You're the one claiming that it's O(log n), so you should explain it.


  • 0
    Y

    @StefanPochmann ??? I didn't. I think Validate Binary Search Tree's time complexity is O(n) even for balanced tree since it traversed all the n nodes.


  • 0

    @yu.xiaoxixi Well you asked why it's O(log n). That pretty much implies that it is O(log n). And as far as I know, nobody else said anything about it being O(log n). So unless I'm mistaken about that, it's your own claim.


  • 1
    Y

    @StefanPochmann Sorry for the confusion.
    The whole hint says:

    "You can recursively use algorithm similar to 98. Validate Binary Search Tree at each node of the tree, which will result in O(nlogn) time complexity.".

    I thought the hints implies that validate BST is O(logn). Because using validate BST "at each node of the tree" is O(n), so validate BST itself should be O(logn) to get the O(nlogn) conclusion.


  • 0

    @yu.xiaoxixi Ah, ok. Now it's clear what you mean. But no, that doesn't imply that validate BST is O(log n). Note that it's not running "validate BST" on the whole tree all the time. If you run "validate BST" on a leaf, it's O(1). And you can expect like half of the nodes to be leaves. And if you run "validate BST" on a child of the root, that's only half of the tree. For a child of a child of the root, it's only a quarter of the tree. And so on. So as I mentioned earlier, it's O(n log n) overall "Because each node is involved in O(log n) validations" (namely in the validations of the subtrees rooted at the node's O(log n) ancestors).


  • 0
    Y

    @StefanPochmann Oh, I see. It is O(n log n). Thanks much for your explanation!


Log in to reply
 

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