1
$\begingroup$

Professor Hastings has constructed a 23-node binary tree in which each node is labeled with a unique letter of the alphabet.

Preorder and postorder traversals of the tree visit the nodes in the following order:

Preorder: B K X E H L Z J W R C Y T S Q A P D F M N U G

Postorder: H J W Z R L E C X S Q T A Y K D M U G N F P B

How can I Draw Professor Hastings' tree and list the nodes in the order visited by an inorder traversal?

$\endgroup$
2
$\begingroup$

The first node of the preorder, which is the same as the last node in the postorder, is the root of the tree, labeled with $B$.

The node after the root in the preorder gives you the left child of the root, in this case $K$. The node before the root in the postorder gives you the right child of the root, which is labeled with $P$.

Now you look into the two subtrees with roots $K$ and $P$. These correspond to substrings in the preorder and postorder. The subtree with root $K$ corresponds to the substring starting at $K$ and ending just before $P$ in the preorder, and to the substring starting at the beginning and ending with $K$ in the postorder. The subtree with root $P$ corresponds to the substring starting with $P$ and running to the end in the preorder, and the substring starting after $K$ and ending with $P$ in the postorder. In this way, we can again find the children of $K$ and the children of $P$, same as we did for the whole tree. For $K$ they are $X$ and $Y$ in that order, and $P$ has children $D$ and $F$.

Just continue in this fashion, splitting the strings into smaller and smaller subtrees until you know the structure of the whole tree.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.