Construction of Binary Tree from Given Traversals
Given Traversals
- Inorder:
[10, 4, 18, 22, 9] - PostOrder:
[10, 18, 9, 22, 41]
In-order + Post-Order Traversal
In the inorder traversal, the process follows Left-Vertex-Right. To understand this better, let’s look at an example:
- The first element in the inorder sequence is considered part of the left subtree.
- The next element is considered the root (vertex).
- The remaining elements are assumed to be part of the right subtree.
- The remaining subtree is further broken down in a similar manner, recursively applying the process.
Example 1:
Example 2:
Inorder Traversal: 4 2 5 1 6 3
Example 3:
Inorder Traversal: 4 2 1 7 5 8 3 6
Post-order Traversal
In the PostOrder Traversal, the process follows Left-Right-Vertex. We apply the PostOrder traversal language to construct the tree.
In-order + Post-order
Inorder: {DBEAFC} Postorder:{ABDECF}
References
Information
- Date: 2024.10.16
- Time: 14:10
- Continued to Data Structures & Algorithm Lecture 22