212k views
4 votes
consider the following preorder traversal of a binary tree: assume that integers are leaf nodes, and * nodes each have two children, and - nodes only have one child - the right child. what is the corresponding in-order traversal for this tree?

User Ximbal
by
8.3k points

1 Answer

7 votes
To determine the corresponding in-order traversal for the given preorder traversal of the binary tree, we need to understand the arrangement of the nodes based on the given information.

Let's denote the leaf nodes as integers, * nodes as internal nodes with two children, and - nodes as internal nodes with only a right child.

Given that the preorder traversal of the tree is:
* - 3 4 * 5 - 6 7

We can analyze it as follows:

1. The first node encountered is '*', indicating an internal node with two children. We can assign it as the root of the tree.
2. The second node encountered is '-', indicating an internal node with only a right child.
3. The third node encountered is '3', an integer leaf node.
4. The fourth node encountered is '4', an integer leaf node.
5. The fifth node encountered is '*', indicating an internal node with two children.
6. The sixth node encountered is '5', an integer leaf node.
7. The seventh node encountered is '-', indicating an internal node with only a right child.
8. The eighth node encountered is '6', an integer leaf node.
9. The ninth node encountered is '7', an integer leaf node.

Based on the preorder traversal and the arrangement of nodes, we can construct the binary tree as follows:

```
*
/ \
- 5
/ \
3 -
/ \
6 7
```

To obtain the in-order traversal, we traverse the tree in the order of left subtree, root, right subtree.

The in-order traversal of the given binary tree is:
3 - 5 6 - 7

Therefore, the corresponding in-order traversal for the given preorder traversal is: 3 - 5 6 - 7.
User Reapen
by
8.7k points