We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I solved it in the similar way, although your solution can be simplified: it's not necessary to store all the elements of the tree in a list, you can just remember one previous value and compare it with the current one in the traversal function: if current is less than previous or equal then it's not BST
In a BST, if you printed out the data during an in order traversal you would end up with 1,2,3,4,5,6... If the printout went like 1,2,4,3... then its not a BST.
So as you traverse, compare the current node's data to the saved previous one (int num). If the current node.data > num, then num = node.data. if node.data is ever <= num, then its not a BST.
@tvolkov You're wrong. You have to verify that all nodes in the left sub tree are lower than the current node and all nodes in the right sub tree are greater than the current node. You need to know all the sub tree in order to determine this. Checking just the current node with it's parent or child nodes could easily yield incorrect results.
Trees: Is This a Binary Search Tree?
You are viewing a single comment's thread. Return to all comments →
I solved it in the similar way, although your solution can be simplified: it's not necessary to store all the elements of the tree in a list, you can just remember one previous value and compare it with the current one in the traversal function: if current is less than previous or equal then it's not BST
how?
In a BST, if you printed out the data during an in order traversal you would end up with 1,2,3,4,5,6... If the printout went like 1,2,4,3... then its not a BST.
So as you traverse, compare the current node's data to the saved previous one (int num). If the current node.data > num, then num = node.data. if node.data is ever <= num, then its not a BST.
@tvolkov You're wrong. You have to verify that all nodes in the left sub tree are lower than the current node and all nodes in the right sub tree are greater than the current node. You need to know all the sub tree in order to determine this. Checking just the current node with it's parent or child nodes could easily yield incorrect results.