Finding the largest subtree in BST

Question

Given the binary tree, I want to find the largest subtree that is the BST in it.

Naive approach:

I have a naive approach when I visit every node of a tree and pass that node to the isBST function. I will also track the number of nodes in the subtree if it is BST.

Is there a better approach than this?

Answer 1

I posted the complete solution and explanation on my blog:

http://www.leetcode.com/2010/11/largest-binary-search-tree-bst-in.html

The idea is to go around the depth and pass the minimum and maximum values from bottom to top instead of top to bottom. In other words, we test the deeper nodes before we verify that the above nodes satisfy the BST requirements.

The main reason for this is when one of the nodes does not satisfy the BST properties, all subtrees above (including this node) must also not satisfy the BST requirements.

Compared to the top-down approach, the bottom-up approach is such an amazing choice, because the results for the total number of nodes can be transmitted along the tree. This saves us from recounting again and again. The total number of nodes for a subtree is simply the total number of nodes on its left and right subtrees plus one.

This algorithm works in O (N) time complexity and O (1) space, which is as efficient as it can be. (where N is the total number of nodes in the binary tree).

Below is the C ++ code. The hard part of the implementation is taking care of how the min and max values ​​are passed from bottom to top. Please note that I did not initialize the minimum and maximum values, as they are initialized at the bottom of the tree.

// Find the largest BST subtree in a binary tree. // If the subtree is a BST, return total number of nodes. // If the subtree is not a BST, -1 is returned. int findLargestBSTSubtree(BinaryTree *p, int &min, int &max, int &maxNodes, BinaryTree *& largestBST) { if (!p) return 0; bool isBST = true; int leftNodes = findLargestBSTSubtree(p->left, min, max, maxNodes, largestBST); int currMin = (leftNodes == 0) ? p->data : min; if (leftNodes == -1 || (leftNodes != 0 && p->data <= max)) isBST = false; int rightNodes = findLargestBSTSubtree(p->right, min, max, maxNodes, largestBST); int currMax = (rightNodes == 0) ? p->data : max; if (rightNodes == -1 || (rightNodes != 0 && p->data >= min)) isBST = false; if (isBST) { min = currMin; max = currMax; int totalNodes = leftNodes + rightNodes + 1; if (totalNodes > maxNodes) { maxNodes = totalNodes; largestBST = p; } return totalNodes; } else { return -1; // This subtree is not a BST } } BinaryTree* findLargestBSTSubtree(BinaryTree *root) { BinaryTree *largestBST = NULL; int min, max; int maxNodes = INT_MIN; // INT_MIN is defined in <climits> findLargestBSTSubtree(root, min, max, maxNodes, largestBST); return largestBST; } 

Answer 2

I assume that the problem you are trying to solve is to find the largest (with many nodes) BST in BT. In this case, you need to go through all the nodes of the tree, checking if it is a BST, and as soon as you find it, you will need to check if it has more nodes than the largest one found so far.

 class TreeNode { public int value; public TreeNode left; public TreeNode right; } void LargestBST(TreeNode bt, IDictionary<TreeNode, bool> isBST, IDictionary<TreeNode, int> nodeCount, ref TreeNode largestBST) { if (bt == null) return; if (IsBST(bt, isBST) && (largestBST == null || NodeCount(bt, nodeCount) > NodeCount(largestBST, nodeCount)) largestBST = bt; else { LargestBST(bt.left, isBST, nodeCount, ref largestBST); LargestBST(bt.Right, isBST, nodeCount, ref largestBST); } } bool IsBST(TreeNode node, IDictionary<TreeNode, bool> isBST) { if (node == null) return true; bool result; if (!isBST.TryGetValue(node, out result)) { TreeNode maxLeft = Max(node.Left); TreeNode minRight = Min(node.Right); result = (maxLeft == null || maxLeft.value <= node.value) && (minRight == null || minRight.value >= node.value) && IsBST(node.left, isBST) && IsBST(node.Right, isBST); isBST.Add(node, result); } return result; } TreeNode Max(TreeNode node) { if (node == null) return null; while (node.right != null) node = node.right; return node; } TreeNode Min(TreeNode node) { if (node == null) return null; while (node.left != null) node = node.left; return node; } int NodeCount(TreeNode node, IDictionary<TreeNode, int> nodeCount) { if (node == null) return 0; int result; if (!nodeCount.TryGetValue(node, out result)) { result = 1 + NodeCount(node.left, nodeCount) + NodeCount(node.right, nodeCount); nodeCount.Add(node, result); } return result; } 

Answer 3

A tree is a BST if traversing it in order gives you its elements in sorted order. You can use this code here if you want to implement an example: http://placementsindia.blogspot.com/2007/12/c-program-to-check-whether-binary-tree.html

Runtime O (N), where N = number of nodes.

Given the BST tree, if the root two subtrees of both BST are wrong (and to the one who deleted your answer that suggested this solution: you should not have deleted your answer, I personally was not going to lower you and there is so much to learn from the bad, but seemingly a good solution, since there is a good one). Counterexample:

  3 / \ 2 4 / \ 1 5 

Now, to get the largest subtree, which is BST, consider this tree:

  3 / \ 2 4 / \ 1 5 

Boundary move 1 2 5 3 4. I think you can solve your original problem by finding a continuous ordered continuous subsequence in a workaround. You just need to be careful not to select sequences that do not describe BST. For example, for:

  10 / \ 2 14 / \ | 1 5 20 

Walking in order 1 2 5 10 20 14. Don’t choose 20. I think this can be done if you fire the elements until their selection ceases to make sense. For example, when you reach 14, reject 20. I am not sure if this can be effectively done. I will edit my post if I find the exact way.

Answer 4

I would think that you can avoid checking if each node is a BST root, working from top to bottom, and not from bottom to top. If the subtree is a BST, it will be larger than any subtree in itself, so you do not need to check inside the subtree if it passed the isBST test. Then you just have isBST, return the size of the valid tree and save it along with a pointer to the root of the subtree if you need to find it again, and not just find out how big is the largest.

UPDATE:

Some of the code posted here to verify that something is a BST will fail in some cases, as they only check the parent element of node.

Take for example:

  10 / \ 4 99 / 2 

This is an invalid BST (2 does not correspond to position 10), but if you do not send the minimum and maximum values ​​down the tree, you will incorrectly check it as valid. This pseudo code takes this into account.

 main { Verify(root, MIN_VALUE, MAX_VALUE) } boolean Verify(node , min, max) { if(node == null) return true; if(node.value > min && node.value < max && Verify(node.leftchild, min, node.value) && Verify(node.rightchild,node.value,max) { return true; } else { return false; } } 

Answer 5

 int getMinMaxValue(Node* root, bool isMin) { if (!root) { // Not real limits... return (isMin ? INT_MAX : INT_MIN); } int leftVal = getMinMaxValue(root->left, isMin); int rightVal = getMinMaxValue(root->right, isMin); if (isMin) { return min(root->value, min(leftVal, rightVal)); } else { return max(root->value, max(leftVal, rightVal)); } } bool isBST(Node* root) { if (!root) { return true; } Node* left = root->left; Node* right = root->right; if (left) { if (getMinMaxValue(left, false) > root->value) { return false; } } if (right) { if (getMinMaxValue(right, true) < root->value) { return false; } } return isBST(left) && isBST(right); } 

Then just go down from the root of the node, checking if the subtree is BST, and take the largest one.

Answer 6

To check if a node is the root of a BST, we must recursively check each left and right child elements. If you start with root, you will have to return all the children before you can decide whether the root from the binary tree is BST or not. Therefore, it makes no sense to call "isBST" for each node. Here is my approach

• Start with root
• Find max left and right
• If not max left and right return "NOT BST"
• if BST is on the left, check more than so far. If so, save it and return "NOT BST"
• if BST is on the right, check more than so far. If so, save it and return "NOT BST"
• If there is BST on the left and on the right, there is a new BST with the current root as ROOT and with the number of nodes on the left + right + 1

A couple of problems when doing this work is to save max so far, for which I used the variable ref MaxNumNodes. maxbst withh has the root of the largest BST found when the function returned.

 public int MaxBST(Node root, int min, int max, ref Node maxbst, ref int MaxNumNodes) { if (root == null) return 0; //Not a BST if (root.data < min || root.data > max) return -1; //Find Max BST on left int left = MaxBST(root.left, min, root.data, ref maxbst, ref MaxNumNodes); //Find Max BST on right int right = MaxBST(root.right, root.data + 1, max, ref maxbst, ref MaxNumNodes); //Case1: -1 from both branches . No BST in both branches if (left == -1 && right == -1) return -1; //Case2:No BST in left branch , so choose right //See if the BST on right is bigger than seen so far if (left == -1) { if (right> MaxNumNodes) { MaxNumNodes = right; maxbst = root.right; } return -1; } //Case3:No BST in right branch , so choose left //See if the BST on left is bigger than seen so far if (right == -1) { if (left > MaxNumNodes) { MaxNumNodes = left; maxbst = root.left; } return -1; } //Case4:Both are BST , new max is left BST + right BST maxbst = root; return left + right + 1; } 

Answer 7

This is not the best approach, but you can traverse the binary tree and store it in an array, and then find the longest continuous increasing sequence that will give you a BST with the maximum number of nodes. The complexity would be O(n) for crawling and O(n) for searching, so it would still be O(n) .

Answer 8

One possible solution might be the following:

 int maxNodes = INT.MIN; Node* lb = NULL; int largesBST(Node* root) { largesBST(root, INT.MIN, INT.MAX); } int largesBST(Node* p, int MIN, int MAX) { if(!p) { return 0; } if(p->data > MIN || p->data < MAX) { return -1; } int lc = largestBST(p->left, p->data, MAX); if(lc == -1) { return -1; } int rc = largestBST(p->right, MIN, p->data); if(rc == -1) { return -1; } // At this point, cur node is BST int curNodes = lc + rc + 1; if(curNodes > maxNodes) { maxNodes = curNodes; lb = p; } } 

Answer 9

To solve the above problem:

• you can traverse a tree in a tree
• Store it in an array and find the “largest sorted subset”.