O(n) - Simple Pre-Preorder Iterative Solution


  • 0

    The logic of this code is simple. Use Pre-Order DFS traversal. At each node check, if left and child obey BST rules. If yes, then increment the current tree size by 1, for each child and push the nodes onto the stack. If a node is found which violates BST rules, then check if the current size of BST tree is greater than last BST tree size. If yes, then save the max size. And reset the current tree size to 0 to measure the size of the next subtree.

    private int findSizeOfBST(Node root) {
                if (root == null) {
                    return 0;
                }
                Stack<Node> stack = new Stack<>();
                stack.push(root);
                int maxSize = 0;
                int currentTreeSize = 0;
                /*
                 * Check if node' left and right are BST nodes, if yes then increment currentTreeSize by 1. If it violates BST, then check if we have found the largest size of BST tree
                 * or not by saving the sub-tree size in maxSize and then reset the currentTreeSize to 0 so that it can start counting the size of next subtree.
                 */
                while (!stack.isEmpty()) {
                    Node node = stack.pop();
    
                    if (node.right != null) {
                        stack.push(node.right);
                        if (node.right.data > node.data) {
                            currentTreeSize++;
                        } else {
                            maxSize = Math.max(currentTreeSize, maxSize);
                            currentTreeSize = 0;
                        }
                    }
    
                    if (node.left != null) {
                        stack.push(node.left);
                        if (node.left.data <= node.data) {
                            currentTreeSize++;
                        } else {
                            maxSize = Math.max(currentTreeSize, maxSize);
                            currentTreeSize = 0;
                        }
                    }
                }
                // We add 1 to account for parent node count
                return 1 + Math.max(currentTreeSize, maxSize);
            }
    

  • 0
    V

    I dont think this works. The result for the example [10,5,15,1,8,null,7] would return 5, when the answer should be 3


Log in to reply
 

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