Question

Draw a (single) binary tree T, such that: • Each internal node of T stores a single character • A preorder traversal of T yields EXAMFUN • An inorder traversal of T yields MAFXUEN

Short answer

Root is 'E'. Left subtree contains nodes X, A, M, F, U. Right subtree is 'N'.

Step-by-step solution

- Understand the traversal definitions

Recognize that a preorder traversal visits nodes in the order: Root, Left, Right. An inorder traversal visits nodes in the order: Left, Root, Right.

- Identify the root from preorder

In the given preorder traversal EXAMFUN, the first character 'E' is the root of the binary tree.

- Locate the root in inorder sequence

Find 'E' in the inorder sequence MAFXUEN. This helps in separating left and right subtrees. The left subtree is 'MAFXU' and the right subtree is 'N'.

- Construct the left subtree

For the left subtree 'MAFXU', the root will be the next character in the preorder sequence after the initial root, which is 'X'. The left and right inorder sequences are 'MAF' and 'U' respectively.

- Construct right subtree for the left part

For inorder 'MAF', the next character in preorder 'A' becomes the new root of this subtree. This subdivides 'MAF' into 'M' (left) and 'F' (right) with roots assigned accordingly.

- Construct the remaining right subtree

Continue with right inorder 'U', utilizing the next preorder character 'U'. The rightmost subtree attaches to 'X'.

- Construct the remaining tree structure

Using similar steps repeat for the single remaining right subtree ('N').

- Finalize tree structure

Combine all parts making sure to consistently follow preorder and inorder sequences.

Key concepts

preorder traversal

In a binary tree, a preorder traversal follows the sequence: visit the root first, then traverse the left subtree, and finally, the right subtree. This method ensures that we access nodes in the precise hierarchical pathway.
For example, in the given preorder traversal 'EXAMFUN', we identify the structure starting from the root 'E', followed by nodes in the left subtree and then the right subtree.
This process helps in setting the foundation of our binary tree, beginning with the root and ensuring each subsequent node follows this path accurately.

inorder traversal

An inorder traversal of a binary tree visits nodes following the sequence: left subtree first, root second, and right subtree last. This pattern results in nodes being visited in a sorted order, if the binary tree is a binary search tree.
Given the inorder traversal 'MAFXUEN', identifying the position of the root 'E' helps in dividing the tree into left ('MAFXU') and right ('N') subtrees. This separation is crucial for constructing the respective subtrees accurately.
When combined with the preorder traversal, this method allows for a methodical reconstruction of the binary tree by appropriately segmenting and assigning nodes in their rightful positions.

subtree identification

Identifying subtrees is a key step in constructing a binary tree from its traversals. Once the root node is placed, the remaining sequence needs to be divided into subtrees based on the inorder and preorder definitions.
For instance, after identifying 'E' as the root in both traversals, the inorder sequence splits into 'MAFXU' (left subtree) and 'N' (right subtree). The preorder sequence further guides the subdivision within these subtrees ('X', 'A', 'M', 'F', 'U' for 'MAFXU').
This methodical breakdown into smaller segments helps in reconstructing each part of the tree step by step, ensuring the structure remains true to the original given traversals.