{"id":27225,"date":"2018-01-05T21:42:55","date_gmt":"2018-01-05T16:12:55","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27225"},"modified":"2018-10-31T10:05:00","modified_gmt":"2018-10-31T04:35:00","slug":"python-program-check-binary-tree-bst-not","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-program-check-binary-tree-bst-not\/","title":{"rendered":"Check if a binary tree is BST or not"},"content":{"rendered":"

Python program to check if a binary tree is BST:<\/strong><\/span><\/p>\n

A binary search tree<\/a> (BST<\/strong>) is a node based binary tree data structure<\/a> which has the following properties.<\/span>
\n\u2022 The left subtree<\/strong> of a node contains only nodes with keys less than<\/strong> the node\u2019s key.
\n\u2022 The right subtree<\/strong> of a node contains only nodes with keys greater than<\/strong> the node\u2019s key.
\n\u2022 Both the left and right subtrees must also be binary search trees.<\/p>\n

From the above properties it naturally follows that:<\/strong>
\nEach node (item in the tree<\/a>) has a distinct key.<\/strong><\/p>\n

\n

[ad type=\u201dbanner\u201d]<\/h4>\n<\/div>\n

METHOD 1 (Correct and Efficient)<\/strong><\/span><\/h3>\n

A better solution looks at each node only once. The trick is to write a utility helper function isBSTUtil(struct node* node, int min, int max)<\/strong> that traverses<\/a> down the tree keeping track of the narrowing min and max allowed values as it goes, looking at each node only once. The initial values for min and max should be INT_MIN and INT_MAX<\/strong> \u2014 they narrow from there.<\/p>\n

\/* Returns true if the given tree is a binary search tree \r\n (efficient version). *\/ \r\nint isBST(struct node* node) \r\n{ \r\n  return(isBSTUtil(node, INT_MIN, INT_MAX)); \r\n} \r\n\r\n\/* Returns true if the given tree is a BST and its \r\n values are >= min and <= max. *\/ \r\nint is BST Util(struct node* node, int min, int max)<\/pre>\n
Implementation of Python Program:<\/strong><\/span><\/h3>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20program%20to%20check%20if%20a%20binary%20tree%20is%20bst%20or%20not%0A%20%0AINT_MAX%20%3D%204294967296%0AINT_MIN%20%3D%20-4294967296%0A%20%0A%23%20A%20binary%20tree%20node%0Aclass%20Node%3A%0A%20%0A%20%20%20%20%23%20Constructor%20to%20create%20a%20new%20node%0A%20%20%20%20def%20__init__(self%2C%20data)%3A%0A%20%20%20%20%20%20%20%20self.data%20%3D%20data%20%0A%20%20%20%20%20%20%20%20self.left%20%3D%20None%0A%20%20%20%20%20%20%20%20self.right%20%3D%20None%0A%20%0A%20%0A%23%20Returns%20true%20if%20the%20given%20tree%20is%20a%20binary%20search%20tree%0A%23%20(efficient%20version)%0Adef%20isBST(node)%3A%0A%20%20%20%20return%20(isBSTUtil(node%2C%20INT_MIN%2C%20INT_MAX))%0A%20%0A%23%20Retusn%20true%20if%20the%20given%20tree%20is%20a%20BST%20and%20its%20values%0A%23%20%3E%3D%20min%20and%20%3C%3D%20max%0Adef%20isBSTUtil(node%2C%20mini%2C%20maxi)%3A%0A%20%20%20%20%20%0A%20%20%20%20%23%20An%20empty%20tree%20is%20BST%0A%20%20%20%20if%20node%20is%20None%3A%0A%20%20%20%20%20%20%20%20return%20True%0A%20%0A%20%20%20%20%23%20False%20if%20this%20node%20violates%20min%2Fmax%20constraint%0A%20%20%20%20if%20node.data%20%3C%20mini%20or%20node.data%20%3E%20maxi%3A%0A%20%20%20%20%20%20%20%20return%20False%0A%20%0A%20%20%20%20%23%20Otherwise%20check%20the%20subtrees%20recursively%0A%20%20%20%20%23%20tightening%20the%20min%20or%20max%20constraint%0A%20%20%20%20return%20(isBSTUtil(node.left%2C%20mini%2C%20node.data%20-1)%20and%0A%20%20%20%20%20%20%20%20%20%20isBSTUtil(node.right%2C%20node.data%2B1%2C%20maxi))%0A%20%0A%23%20Driver%20program%20to%20test%20above%20function%0Aroot%20%3D%20Node(4)%0Aroot.left%20%3D%20Node(2)%0Aroot.right%20%3D%20Node(5)%0Aroot.left.left%20%3D%20Node(1)%0Aroot.left.right%20%3D%20Node(3)%0A%20%0Aif%20(isBST(root))%3A%0A%20%20%20%20print%20%22Is%20BST%22%0Aelse%3A%0A%20%20%20%20print%20%22Not%20a%20BST%22%0A%20%0A%23%20This%20code%20is%20contributed%20by%20Nikhil%20Kumar%20Singh(nickzuck_007)\u201d message=\u201dPython Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output:<\/strong><\/span><\/h3>\n
Is BST<\/pre>\n
Time Complexity:<\/strong> <\/span>O(n)\u00a0<\/strong>
\nAuxiliary Space :<\/strong><\/span> O(1)<\/strong> if Function Call Stack size is not considered, otherwise O(n)<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
Python program to check if a binary tree is BST or not – Data Structure – A binary search tree is a node based binary tree data structure.<\/p>\n","protected":false},"author":1,"featured_media":28088,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80126,1,4148],"tags":[81149,81152,81143,81142,81145,81146,81148,81147,81150,81141,81144,81151],"class_list":["post-27225","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-binary-search-tree","category-coding","category-python","tag-check-if-binary-tree-is-balanced","tag-check-if-binary-tree-is-balanced-python","tag-check-if-binary-tree-is-bst-c","tag-check-if-binary-tree-is-bst-java","tag-check-if-binary-tree-is-bst-python","tag-check-whether-the-linked-list-is-palindrome","tag-geeksforgeeks-binary-search-tree","tag-how-to-check-if-a-tree-is-balanced-or-not-in-java","tag-python-check-if-tree-is-balanced","tag-searches-related-to-python-program-to-check-if-a-binary-tree-is-bst-or-not","tag-valid-binary-search-tree","tag-what-is-balanced-binary-tree"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27225","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27225"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27225\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/28088"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27225"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27225"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27225"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}