3 replies to this topic

[kakariki]

Hey,

I am having trouble with a question on a sample exam in a programming class I am in.

Describe (in a sentence or two) all binary trees whose nodes appear in exactly the same sequence in both (i) preorder and inorder, (ii) preorder and postorder, (iii) inorder and postorder.

That's the question. I know how to traverse the tree in preorder, inorder, and postorder. Aswell as level order. But, I am unsure how to determine what BSTs would traverse the same in the way listed.

Thanks.

[gregwarner]

I. Preorder and inorder both process the root before the right subtree, so trees that appear the same would be trees whose nodes only have right subtrees.
II. Preorder and postorder each process the root at a different time in relation to both subtrees, so trees that appear the same would be trees with one node and no subtrees.
III. Inorder and postorder both process the left subtree before the root, so trees that appear the same would be trees whose nodes only have left subtrees.

[kakariki]

Great! Thanks a lot gregwarner, that's a really big help!!!

[fayyazlodhi]

Following would be interesting related problems along with code for traversal of BST

http://forum.codecal...if-bst-not.html
http://forum.codecal...cestor-bst.html