- Forum
- General C++ Programming
- Binary Search tree
Binary Search tree
While it is true that the inorder traversal of a binary search tree produces a sorted output, is the converse also true, i.e., if the inorder traversal of a binary tree is sorted, then is it necessarily a binary search tree?
@hamsterman
Thanks for the prompt reply :).
However, pardon me for being so skeptic , how can you be absolutely certain about it?
Thanks for the prompt reply :).
However, pardon me for being so skeptic , how can you be absolutely certain about it?
Take the output string, for example ABCDEF.
The question is "was the tree that generated this output a bst?". A binary tree is a bst if
1. both of its children are bsts
2. the greatest element of the left child is smaller than the root element and the lowest element of the right child is greater than the root element
(either or both could be empty too).
The example output was produced by concatenation: output of left child + root element + output of right child
Any element could be the root one. Lets randomly pick D. Now left child produced ABC and right child produced EF. C goes before D and E goes after D, so the second property of a bst is fulfilled. Now you need to know if ABC and EF were both generated by bsts. The problem is recursive, until you reach a tree of one node, which is definitely a bst.
Sorry if it's a mess. I'm not used to writing proofs.
The question is "was the tree that generated this output a bst?". A binary tree is a bst if
1. both of its children are bsts
2. the greatest element of the left child is smaller than the root element and the lowest element of the right child is greater than the root element
(either or both could be empty too).
The example output was produced by concatenation: output of left child + root element + output of right child
Any element could be the root one. Lets randomly pick D. Now left child produced ABC and right child produced EF. C goes before D and E goes after D, so the second property of a bst is fulfilled. Now you need to know if ABC and EF were both generated by bsts. The problem is recursive, until you reach a tree of one node, which is definitely a bst.
Sorry if it's a mess. I'm not used to writing proofs.
Topic archived. No new replies allowed.