Write a program to check whether a given tree is a binary search tree.
We all know that a binary search tree follows the rule : for any given node with value N, all the values in the left of that node is lesser than N and all the values in the right of that node will be greater than or equal to N. For example,
This is a tricky question. We may try to immediately run through all the nodes checking only the immediate left and right nodes and coming to a conclusion that it is a binary search tree. But this program may not work for this scenario.
The simplest solution to this problem is to do an inorder traversal through the entire tree and find whether it is sorted or not. Typically we can do that by pushing into any array. Even better is to calculate the minimum value at each step. Program is as follows. Please leave some comments if something is confusing. I will get back immediately.
We all know that a binary search tree follows the rule : for any given node with value N, all the values in the left of that node is lesser than N and all the values in the right of that node will be greater than or equal to N. For example,
This is a tricky question. We may try to immediately run through all the nodes checking only the immediate left and right nodes and coming to a conclusion that it is a binary search tree. But this program may not work for this scenario.
The simplest solution to this problem is to do an inorder traversal through the entire tree and find whether it is sorted or not. Typically we can do that by pushing into any array. Even better is to calculate the minimum value at each step. Program is as follows. Please leave some comments if something is confusing. I will get back immediately.
Cheers!
Braga
2 comments:
Could you please elaborate on the same Braggesh. Tx.
@Joel Nishan Lobo : This involves in the way a tree is traversed. See here for traversal techniques : http://www.technicalypto.com/2010/02/traversals-in-binary-search-tree.html
Post a Comment