1 votes 1 votes give an o(n) algorithm to check whether the given binary tree is bst or not DS data-structures binary-search-tree time-complexity + – Kaluti asked Mar 31, 2018 recategorized Jul 6, 2022 by Lakshman Bhaiya Kaluti 507 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply pankaj_vir commented Mar 31, 2018 reply Follow Share https://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/ we know that inorder traversal gives the sorted order in ascending order, just do the traversal and check it is in sorted order or not. 0 votes 0 votes Devshree Dubey commented Mar 31, 2018 reply Follow Share It's tat bit simple. For a tree to be a BST,the only pre-condition which holds is that the values in left are less than that of the root,whereas the values on the right hand side are greater than the root.The recursive algorithm should work in this case. 1 votes 1 votes Kaluti commented Mar 31, 2018 reply Follow Share but it will give wrong result for some binary tree because it will check only at current node only 0 votes 0 votes abhishekmehta4u commented Apr 1, 2018 reply Follow Share Kaluti is right 1 votes 1 votes Please log in or register to add a comment.
2 votes 2 votes INORDER of binary search tree will be always sorted . if you have a binary tree then perfome inorder traversal if it is sorted then tree is binary search tree otherwise it is not a binary search tree. inorder traversal will take O(n) time . abhishekmehta4u answered Apr 1, 2018 abhishekmehta4u comment Share Follow See all 3 Comments See all 3 3 Comments reply pankaj_vir commented Apr 1, 2018 reply Follow Share It should be in ascending order. 0 votes 0 votes Devshree Dubey commented Apr 1, 2018 reply Follow Share @pankaj_vir,It is but obvious when the inroder traversal is applied the result will be in increasing order. However, for the case of list comprising of elements should be in descending order in tree itself. 0 votes 0 votes pankaj_vir commented Apr 2, 2018 reply Follow Share @Devshree Dubey, that's true 0 votes 0 votes Please log in or register to add a comment.