Python program to find largest binary search tree in a Binary Tree.














































Python program to find largest binary search tree in a Binary Tree.



Description:
To find the largest BST in BT we need to write a function to find the largest subtree which is also a Binary Search Tree (BST).
A Tree is BST if following is true for every node x.
1. The largest value in left subtree (of x) is smaller than value of x.
2. The smallest value in right subtree (of x) is greater than value of x.

Example : 
Here the maximum size  BST subtree is :


Program :

# Python program to find largest BST in a Binary Tree. minVal= -2147483648 maxVal = 2147483647 # Helper function that allocates a new node with the given data and None left and right pointers. class newNode: def __init__(self, data): self.data = data self.left = None self.right = None # Returns Information about subtree which includes size of largest subtree which is a BST def largestBSTBT(root): # Base cases : When tree is empty or it has # one child. if (root == None): return 0, minVal, maxVal, 0, True if (root.left == None and root.right == None) : return 1, root.data, root.data, 1, True # Recur for left subtree and right subtrees l = largestBSTBT(root.left) r = largestBSTBT(root.right) # Create a return variable and initialize its size. ret = [0, 0, 0, 0, 0] ret[0] = (1 + l[0] + r[0]) # If whole tree rooted under current root is BST. if (l[4] and r[4] and l[1] < root.data and r[2] > root.data) : ret[2] = min(l[2], min(r[2], root.data)) ret[1] = max(r[1], max(l[1], root.data)) # Update answer for tree rooted under # current 'root' ret[3] = ret[0] ret[4] = True return ret # If whole tree is not BST, return maximum # of left and right subtrees ret[3] = max(l[3], r[3]) ret[4] = False return ret # Driver Code if __name__ == '__main__': """Let us construct the following Tree 20 / \ 25 30 / 10 """ root = newNode(20) root.left = newNode(25) root.right = newNode(30) root.left.left = newNode(10) print("Size of the largest BST is",largestBSTBT(root)[3])
Output:

Size of the largest BST is 2 >>>

More Articles of Khushboo Singh:

Name Views Likes
Python program to insert an element in binary tree. 820 20
Tokenize text using NLTK in Python. 1198 12
Python Remove multiple elements from list while Iterating. 731 22
Python How to Check if an item exists in list ? 4267 14
Python How to remove multiple elements from list ? 736 26
Python program to check if two trees are mirror of each other without using recursion. 659 19
Python program to find maximum in Binary tree. 928 19
Python Check if all elements are same using Set 709 15
Python program to find diameter of a binary tree. 1081 20
Python program to print root to leaf paths without using recursion. 839 20
Python program to find root of the tree where children id sum for every node is given. 668 23
Introduction of Python NLTK library 1354 25
Categorizing and Tagging Sentences using NLTK in Python . 999 19
Python program to find height of a tree without using recursion. 661 16
Python program to find sum of all nodes of the given perfect binary tree. 655 19
Python program to find minimum in binary tree. 820 23
Python Check if element exist in list using list.count() function. 690 13
Python program to convert a given binary tree to doubly linked list. 882 20
Python program to find distance between two nodes of a binary tree. 1521 20
NLTK stop Words 1134 13
Python program to find largest binary search tree in a Binary Tree. 934 20
Python program to find inorder successor in binary search tree with recursion. 1201 18
Python program to convert a binary tree into doubly linked list in spiral fashion. 794 15
Python List check if element are same using all() 666 12
Python program to check if two trees are identical using recursion. 705 30
Python Find the occurrence count of an element in the tuple using count() 964 23
Python Convert two lists to a dictionary 722 19
Python program to construct a complete binary tree from given array. 1426 14
Python program to find diameter of binary tree in O(n). 870 17
Introduction to the AVL tree. 739 15
Python program to check if two trees are identical without using recursion 659 17
Python Convert a list of tuples to dictionary. 1076 24
Python program to convert a binary tree to a circular doubly link list. 644 21
Python Check if element exist in list based on own logic. 736 23
Python program to merge two binary trees by doing node sum using recursion 999 27
Python program to check whether a given binary tree is perfect or not. 674 17
Python Check if all elements are same using list.count(). 1083 28
Python program to find an element into binary tree 627 12
Python program to find lowest common ancestor in a binary tree 1209 24

Comments