{"id":27142,"date":"2018-01-03T21:46:33","date_gmt":"2018-01-03T16:16:33","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27142"},"modified":"2018-01-03T21:46:33","modified_gmt":"2018-01-03T16:16:33","slug":"c-program-check-binary-tree-bst-not","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-program-check-binary-tree-bst-not\/","title":{"rendered":"C program to check if a binary tree is BST or not"},"content":{"rendered":"

A binary search tree (BST) is a node based binary tree data structure which has the following properties.<\/span>
\n\u2022 The left subtree of a node contains only nodes with keys less than the node\u2019s key.
\n\u2022 The right subtree of a node contains only nodes with keys greater than 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:
\n\u2022 Each node (item in the tree) has a distinct key.<\/p>\n[ad type=\u201dbanner\u201d]\n

\n

Recommended: Please solve it on \u201cPRACTICE<\/u><\/i>\u201d first, before moving on to the solution.<\/a><\/strong><\/h4>\n<\/div>\n

METHOD 1 (Simple but Wrong)<\/strong>
\nFollowing is a simple program. For each node, check if left node of it is smaller than the node and right node of it is greater than the node.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201dint%20isBST(struct%20node*%20node)%20%0A%7B%20%0A%20%20if%20(node%20%3D%3D%20NULL)%20%0A%20%20%20%20return%201%3B%20%0A%20%20%20%20%20%0A%20%20%2F*%20false%20if%20left%20is%20%3E%20than%20node%20*%2F%0A%20%20if%20(node-%3Eleft%20!%3D%20NULL%20%26%26%20node-%3Eleft-%3Edata%20%3E%20node-%3Edata)%20%0A%20%20%20%20return%200%3B%20%0A%20%20%20%20%20%0A%20%20%2F*%20false%20if%20right%20is%20%3C%20than%20node%20*%2F%0A%20%20if%20(node-%3Eright%20!%3D%20NULL%20%26%26%20node-%3Eright-%3Edata%20%3C%20node-%3Edata)%20%0A%20%20%20%20return%200%3B%20%0A%20%20%20%0A%20%20%2F*%20false%20if%2C%20recursively%2C%20the%20left%20or%20right%20is%20not%20a%20BST%20*%2F%0A%20%20if%20(!isBST(node-%3Eleft)%20%7C%7C%20!isBST(node-%3Eright))%20%0A%20%20%20%20return%200%3B%20%0A%20%20%20%20%20%0A%20%20%2F*%20passing%20all%20that%2C%20it\u2019s%20a%20BST%20*%2F%0A%20%20return%201%3B%20%0A%7D\u201d message=\u201dc\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

This approach is wrong as this will return true for below binary tree (and below tree is not a BST because 4 is in left subtree of 3)<\/p>\n[ad type=\u201dbanner\u201d]\nMETHOD 2 (Correct but not efficient)<\/strong>
\nFor each node, check if max value in left subtree is smaller than the node and min value in right subtree greater than the node.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F*%20Returns%20true%20if%20a%20binary%20tree%20is%20a%20binary%20search%20tree%20*%2F%0Aint%20isBST(struct%20node*%20node)%20%0A%7B%20%0A%20%20if%20(node%20%3D%3D%20NULL)%20%0A%20%20%20%20return(true)%3B%20%0A%20%20%20%20%20%0A%20%20%2F*%20false%20if%20the%20max%20of%20the%20left%20is%20%3E%20than%20us%20*%2F%0A%20%20if%20(node-%3Eleft!%3DNULL%20%26%26%20maxValue(node-%3Eleft)%20%3E%20node-%3Edata)%20%0A%20%20%20%20return(false)%3B%20%0A%20%20%20%20%20%0A%20%20%2F*%20false%20if%20the%20min%20of%20the%20right%20is%20%3C%3D%20than%20us%20*%2F%0A%20%20if%20(node-%3Eright!%3DNULL%20%26%26%20minValue(node-%3Eright)%20%3C%20node-%3Edata)%20%0A%20%20%20%20return(false)%3B%20%0A%20%20%20%0A%20%20%2F*%20false%20if%2C%20recursively%2C%20the%20left%20or%20right%20is%20not%20a%20BST%20*%2F%0A%20%20if%20(!isBST(node-%3Eleft)%20%7C%7C%20!isBST(node-%3Eright))%20%0A%20%20%20%20return(false)%3B%20%0A%20%20%20%20%20%0A%20%20%2F*%20passing%20all%20that%2C%20it\u2019s%20a%20BST%20*%2F%0A%20%20return(true)%3B%20%0A%7D%20\u2033 message=\u201dC Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

It is assumed that you have helper functions minValue() and maxValue() that return the min or max int value from a non-empty tree<\/p>\n[ad type=\u201dbanner\u201d]\n

METHOD 3 (Correct and Efficient)<\/strong>
\nMethod 2 above runs slowly since it traverses over some parts of the tree many times. 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) that traverses 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 \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 isBSTUtil(struct node* node, int min, int max) \r\n<\/pre>\n
Implementation:<\/strong><\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%23include%20%3Climits.h%3E%0A%20%0A%2F*%20A%20binary%20tree%20node%20has%20data%2C%20pointer%20to%20left%20child%0A%20%20%20and%20a%20pointer%20to%20right%20child%20*%2F%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node*%20left%3B%0A%20%20%20%20struct%20node*%20right%3B%0A%7D%3B%0A%20%0Aint%20isBSTUtil(struct%20node*%20node%2C%20int%20min%2C%20int%20max)%3B%0A%20%0A%2F*%20Returns%20true%20if%20the%20given%20tree%20is%20a%20binary%20search%20tree%20%0A%20(efficient%20version).%20*%2F%0Aint%20isBST(struct%20node*%20node)%20%0A%7B%20%0A%20%20return(isBSTUtil(node%2C%20INT_MIN%2C%20INT_MAX))%3B%20%0A%7D%20%0A%20%0A%2F*%20Returns%20true%20if%20the%20given%20tree%20is%20a%20BST%20and%20its%20%0A%20%20%20values%20are%20%3E%3D%20min%20and%20%3C%3D%20max.%20*%2F%0Aint%20isBSTUtil(struct%20node*%20node%2C%20int%20min%2C%20int%20max)%20%0A%7B%20%0A%20%20%2F*%20an%20empty%20tree%20is%20BST%20*%2F%0A%20%20if%20(node%3D%3DNULL)%20%0A%20%20%20%20%20return%201%3B%0A%20%20%20%20%20%20%20%0A%20%20%2F*%20false%20if%20this%20node%20violates%20the%20min%2Fmax%20constraint%20*%2F%20%0A%20%20if%20(node-%3Edata%20%3C%20min%20%7C%7C%20node-%3Edata%20%3E%20max)%20%0A%20%20%20%20%20return%200%3B%20%0A%20%0A%20%20%2F*%20otherwise%20check%20the%20subtrees%20recursively%2C%20%0A%20%20%20tightening%20the%20min%20or%20max%20constraint%20*%2F%0A%20%20return%0A%20%20%20%20isBSTUtil(node-%3Eleft%2C%20min%2C%20node-%3Edata-1)%20%26%26%20%20%2F%2F%20Allow%20only%20distinct%20values%0A%20%20%20%20isBSTUtil(node-%3Eright%2C%20node-%3Edata%2B1%2C%20max)%3B%20%20%2F%2F%20Allow%20only%20distinct%20values%0A%7D%20%0A%20%0A%2F*%20Helper%20function%20that%20allocates%20a%20new%20node%20with%20the%0A%20%20%20given%20data%20and%20NULL%20left%20and%20right%20pointers.%20*%2F%0Astruct%20node*%20newNode(int%20data)%0A%7B%0A%20%20struct%20node*%20node%20%3D%20(struct%20node*)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20malloc(sizeof(struct%20node))%3B%0A%20%20node-%3Edata%20%3D%20data%3B%0A%20%20node-%3Eleft%20%3D%20NULL%3B%0A%20%20node-%3Eright%20%3D%20NULL%3B%0A%20%0A%20%20return(node)%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20functions*%2F%0Aint%20main()%0A%7B%0A%20%20struct%20node%20*root%20%3D%20newNode(4)%3B%0A%20%20root-%3Eleft%20%20%20%20%20%20%20%20%3D%20newNode(2)%3B%0A%20%20root-%3Eright%20%20%20%20%20%20%20%3D%20newNode(5)%3B%0A%20%20root-%3Eleft-%3Eleft%20%20%3D%20newNode(1)%3B%0A%20%20root-%3Eleft-%3Eright%20%3D%20newNode(3)%3B%20%0A%20%0A%20%20if(isBST(root))%0A%20%20%20%20printf(%22Is%20BST%22)%3B%0A%20%20else%0A%20%20%20%20printf(%22Not%20a%20BST%22)%3B%0A%20%20%20%20%20%0A%20%20getchar()%3B%0A%20%20return%200%3B%0A%7D%20%20\u2033 message=\u201dC Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Time Complexity: O(n)
\nAuxiliary Space : O(1) if Function Call Stack size is not considered, otherwise O(n)<\/p>\n[ad type=\u201dbanner\u201d]\n
METHOD 4(Using In-Order Traversal)<\/strong>
\nThanks to LJW489 <\/a>for suggesting this method.
\n1) Do In-Order Traversal of the given tree and store the result in a temp array.
\n3) Check if the temp array is sorted in ascending order, if it is, then the tree is BST.<\/p>\n
Time Complexity:<\/strong> O(n)<\/p>\n
We can avoid the use of Auxiliary Array. While doing In-Order traversal, we can keep track of previously visited node. If the value of the currently visited node is less than the previous value, then tree is not BST. Thanks to ygos <\/a>for this space optimization.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201dbool%20isBST(struct%20node*%20root)%0A%7B%0A%20%20%20%20static%20struct%20node%20*prev%20%3D%20NULL%3B%0A%20%20%20%20%20%0A%20%20%20%20%2F%2F%20traverse%20the%20tree%20in%20inorder%20fashion%20and%20keep%20track%20of%20prev%20node%0A%20%20%20%20if%20(root)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(!isBST(root-%3Eleft))%0A%20%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Allows%20only%20distinct%20valued%20nodes%20%0A%20%20%20%20%20%20%20%20if%20(prev%20!%3D%20NULL%20%26%26%20root-%3Edata%20%3C%3D%20prev-%3Edata)%0A%20%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%0A%20%20%20%20%20%20%20%20prev%20%3D%20root%3B%0A%20%0A%20%20%20%20%20%20%20%20return%20isBST(root-%3Eright)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20true%3B%0A%7D\u201d message=\u201dC Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
\u00a0[ad type=\u201dbanner\u201d]<\/div>\n","protected":false},"excerpt":{"rendered":"
C program to check if a binary tree is BST or not – Binary Search Tree – A binary search tree (BST) is a node based binary tree data structure.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80126,69866,1],"tags":[80539,70115,70263,70669,80540,72675,80553,80211,72689,70285,80815,80552,80549,70489,80550,80960],"class_list":["post-27142","post","type-post","status-publish","format-standard","hentry","category-binary-search-tree","category-c-programming","category-coding","tag-binary-search-algorithm-c","tag-binary-search-program-in-data-structure","tag-binary-search-tree","tag-binary-search-tree-applications","tag-binary-search-tree-example-step-by-step","tag-binary-tree-in-data-structure","tag-binary-tree-in-java","tag-binary-tree-program-in-c","tag-binary-tree-search","tag-binary-tree-traversal","tag-bst","tag-bst-definition","tag-code-for-binary-search-tree-in-c","tag-complete-binary-tree","tag-data-structure-binary-search-tree","tag-what-is-binary-tree-in-data-structure"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27142","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=27142"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27142\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27142"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27142"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27142"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}