Constructing a binary tree from inorder and postorder traversals

In summary, the conversation involves constructing a tree using given traversals (preorder and inorder) and verifying the correctness of the tree. The first tree has a root of E, with left child X and right child N. X has left child A and right child U, while A has left child M and right child F. The second tree has a root of D, with left child B and right child E. B has left child A and right child C, while E has left child F and right child G. The correctness of the first tree is confirmed, but there is uncertainty about the correctness of the second tree.
  • #1
Shackman
22
2

Homework Statement


Construct the tree from the following traversals
Preorder: EXAMFUN
Inorder: MAFXUEN

The Attempt at a Solution


E
/ \
X N
/ \
A U
/ \
M F

Correct?

Very difficult to see sorry, but E is root with left child X right child N. X has left child A right child U. A has left child M right child F.
 
Last edited:
Physics news on Phys.org
  • #2
I am now almost positive the first tree is correct, but what about
Preorder: DBACEGF
Inorder: ABCDEFG

I have: Root is D has left child B right child E. B has left child A right child C. E has left child null right child F. F has left child G right child null.
 
Last edited:
  • #3
This looks correct based on the given preorder and inorder traversals. However, without the full picture it is impossible to say for certain if this is the correct tree. Additionally, the postorder traversal is not provided, so it is difficult to verify the tree's construction. It would be helpful to have more information or a visual representation to ensure accuracy.
 

1. How do you construct a binary tree from inorder and postorder traversals?

To construct a binary tree from inorder and postorder traversals, you first need to understand the concept of inorder and postorder traversals. Inorder traversal is when the left subtree is visited first, then the root, and finally the right subtree. Postorder traversal is when the left subtree is visited first, then the right subtree, and finally the root. To construct the binary tree, you need to start with the last element in the postorder traversal as the root. Then, you can find the index of that element in the inorder traversal. The elements to the left of the index in the inorder traversal will be the left subtree, and the elements to the right will be the right subtree. You can then recursively construct the left and right subtrees using the same process.

2. What is the time complexity for constructing a binary tree from inorder and postorder traversals?

The time complexity for constructing a binary tree from inorder and postorder traversals is O(n), where n is the number of nodes in the tree. This is because we need to visit each node once to construct the tree.

3. Can a binary tree be constructed from only inorder or postorder traversal?

Yes, a binary tree can be constructed from only inorder or postorder traversal. However, the resulting tree may not be unique. This is because inorder and postorder traversals do not provide enough information to determine the exact structure of the tree. Additional information, such as preorder traversal, is needed to construct a unique binary tree.

4. What is the difference between inorder and postorder traversal?

Inorder traversal visits the left subtree first, then the root, and finally the right subtree. This results in the elements being visited in ascending order. Postorder traversal visits the left subtree first, then the right subtree, and finally the root. This results in the elements being visited in descending order.

5. Can a binary tree have duplicate elements when constructed from inorder and postorder traversals?

Yes, a binary tree can have duplicate elements when constructed from inorder and postorder traversals. This is because there may be duplicate elements in the traversals, and the structure of the tree is determined by the order of the elements rather than the values of the elements. However, in most cases, duplicate elements are avoided in inorder and postorder traversals to make the resulting tree unique.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
3
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
9K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
5K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
1K
Back
Top