Question
Draw the binary tree for which the traversal sequences are given as follows:
(i) Post order: DHKECFMNLGBA
In order: DCHEKAFBMLNG
(ii) Pre order: ABCDEFGHJK
In order: B-D-C-E-A-G-H-K-F
Answer :
Word Count : 728
_________ ________ _____ _________ ___ ___ _______ _________ __________ ________ _______ ________.
________ _________ _________ _____ ______.
___ _______ ______ _________ ______ _____ __________ ___ ________ _______ _______ ___.
________ _____ _____ ________ __________ ____.
_________ _____ ___ _____ _______ __________ ________.
___ ______ ___ _______ __________ _________.
______ ______ ______ _______ __________ __________ _______ _____ _____ _____.
_____ _______ _____ ____ _______ _____ _________ ______ _____ ____ ____.
____ ___ _____ ____ _____ _______ _________ ______ ______ __________.
_____ _________ ____ _________ _________ ___ _____ ___ __________.
________ _______ ______ _____ ____ _____.
_____ ______ _________ ___ _______.
_________ ___ ____ _____ ________.
____ ____ __________ __________ ______ __________ __________.
______ __________ _______ ___ ______ ____ _______ ___ __________ _____.
______ ___ __________ ____ ___ _____ _____ ______ ___.
__________ ___ _________ _____ ________ _________ ________ ______ _______ _____.
______ ________ ______ _____ _______ _____ _____ ________.
_____ ____ _________ _______ ________ ___ _____ __________.
________ _____ __________ __________ _____ ___ _________ __________.
__________ ______ ________ _________ _______ ___ _____.
___ _______ ___ _____ ____ ______ _________ _______.
________ ________ ______ _______ _______ ____.
_____ ____ _____ _____ ____ _____ _____.
____ ________ ________ _____ _____ ___ _____ _________ _____.
_____ _______ ____ ________ ________ ______ _______ _____.
___ _____ ________ ______ __________ ________.
__________ _________ ___ ______ _______.
___ _______ _______ ___ __________ __________ __________ _____ __________.
_____ ___ ______ _________ ______ _________ ___ ___ ________.
________ ________ __________ _________ _______ _______ _____.
_____ _____ ________ __________ __________ __________ _____.
_______ __________ _______ ________ ___.
__________ ________ ________ _______ ___ ____ ___ _________.
_____ _______ ____ _____ __________.
___ _________ ____ ________ ____ ___ ______ ______ ____ ______.
______ _______ ________ _________ _______ ________ _______ _____ ___ ______ _____ ________.
___ ____ ____ ____ _________ __________.
_______ _________ _________ ___ _______.
______ _________ __________ ______ _____ ____ _____ __________ _______ _________ ________ __________.
___ ___ _________ ________ _______ ________ _______ _____.
____ ________ ________ ________ _________ ___ ___ ______ ____ __________ ___ _______.
_______ ____ __________ ___ ____ _________.
_______ ___ ____ ________ ________ _______ _______ _______ __________.
______ _____ ________ ___ _________ ______.
_______ _________ ____ ____ ____.
____ _____ _____ ________ ___ _________ _________ _________ ___.
______ ____ ____ ____ _____ ______ ________ __________ ________.
________ _____ ______ _______ ________.
_________ ____ _____ ________ _______.
_______ _______ __________ __________ ______.
______ ______ _______ __________ ________ ________ _________.
____ ________ _______ ________ _____ ____ ________ ________.
__________ ________ ____ ____ ___ _________ ____ ___ ___ ________.
______ ______ ___ _____ _________ ___ __________ ____ _______ __________ ________.
___ __________ ______ _________ _____ ___ _____ _____ _________ ___ ____.
________ _____ _______ ____ ____ _____.
_______ ________ _______ ____ _______ __________ _________ __________ ________ __________ __________ _____.
_______ _______ ___ ______ _______ ______ _________ _________ ______ ________ ____.
____ ________ _________ ______ ____.
_________ ___ _____ ___ __________ __________ ____ __________.
_____ ___ ____ ________ ____ __________ _______ _____ ___ ________ ____ ____.
________ ______ ______ _____ ______ __________ ______ ______ _____ ____ _____.
___ __________ ___ _______ _________ ___ _________.
__________ _____ _________.
Skip in 10
To construct a binary tree from given traversal sequences, we use the properties of each traversal method. Post-order traversal visits nodes in the order Left → Right → Root, in-order traversal visits nodes Left → Root → Right, and pre-order traversal visits nodes Root → Left → Right. Using these rules, we can reconstruct the tree step by step. --- (i) Post-order: DHKECFMNLGBA, In-order: DCHEKAFBMLNG 1. Identify the root: In post-order, the last element is always the root of the tree. Here, post-order ends with `A`. So `A` is the root. 2. Divide the in-order sequence: In in-order, elements left of the root are in the left subtree, and elements right of the root are in the right subtree. In-order: `D C H E K A F B M L N G` * Left subtree in-order: `D C H E K` * Right subtree in-order: `F B M L N G` 3. Left subtree reconstruction: Post-order for left subtree (from original post-order, removing the root `A`): `D H K E C F M N L G B` → the left subtree nodes are `D H K E C` (first 5 elements). * Root of left subtree is last element in this post-order segment: `C`
______ ________ ________ _______ __________ ___ _____ _____._________ ________ _____ _________ ___ ___ _______ _________ __________ ________ _______ ________.
________ _________ _________ _____ ______.
___ _______ ______ _________ ______ _____ __________ ___ ________ _______ _______ ___.
________ _____ _____ ________ __________ ____.
_________ _____ ___ _____ _______ __________ ________.
___ ______ ___ _______ __________ _________.
______ ______ ______ _______ __________ __________ _______ _____ _____ _____.
_____ _______ _____ ____ _______ _____ _________ ______ _____ ____ ____.
____ ___ _____ ____ _____ _______ _________ ______ ______ __________.
_____ _________ ____ _________ _________ ___ _____ ___ __________.
________ _______ ______ _____ ____ _____.
_____ ______ _________ ___ _______.
_________ ___ ____ _____ ________.
____ ____ __________ __________ ______ __________ __________.
______ __________ _______ ___ ______ ____ _______ ___ __________ _____.
______ ___ __________ ____ ___ _____ _____ ______ ___.
__________ ___ _________ _____ ________ _________ ________ ______ _______ _____.
______ ________ ______ _____ _______ _____ _____ ________.
_____ ____ _________ _______ ________ ___ _____ __________.
________ _____ __________ __________ _____ ___ _________ __________.
__________ ______ ________ _________ _______ ___ _____.
___ _______ ___ _____ ____ ______ _________ _______.
________ ________ ______ _______ _______ ____.
_____ ____ _____ _____ ____ _____ _____.
____ ________ ________ _____ _____ ___ _____ _________ _____.
_____ _______ ____ ________ ________ ______ _______ _____.
___ _____ ________ ______ __________ ________.
__________ _________ ___ ______ _______.
___ _______ _______ ___ __________ __________ __________ _____ __________.
_____ ___ ______ _________ ______ _________ ___ ___ ________.
________ ________ __________ _________ _______ _______ _____.
_____ _____ ________ __________ __________ __________ _____.
_______ __________ _______ ________ ___.
__________ ________ ________ _______ ___ ____ ___ _________.
_____ _______ ____ _____ __________.
___ _________ ____ ________ ____ ___ ______ ______ ____ ______.
______ _______ ________ _________ _______ ________ _______ _____ ___ ______ _____ ________.
___ ____ ____ ____ _________ __________.
_______ _________ _________ ___ _______.
______ _________ __________ ______ _____ ____ _____ __________ _______ _________ ________ __________.
___ ___ _________ ________ _______ ________ _______ _____.
____ ________ ________ ________ _________ ___ ___ ______ ____ __________ ___ _______.
_______ ____ __________ ___ ____ _________.
_______ ___ ____ ________ ________ _______ _______ _______ __________.
______ _____ ________ ___ _________ ______.
_______ _________ ____ ____ ____.
____ _____ _____ ________ ___ _________ _________ _________ ___.
______ ____ ____ ____ _____ ______ ________ __________ ________.
________ _____ ______ _______ ________.
_________ ____ _____ ________ _______.
_______ _______ __________ __________ ______.
______ ______ _______ __________ ________ ________ _________.
____ ________ _______ ________ _____ ____ ________ ________.
__________ ________ ____ ____ ___ _________ ____ ___ ___ ________.
______ ______ ___ _____ _________ ___ __________ ____ _______ __________ ________.
___ __________ ______ _________ _____ ___ _____ _____ _________ ___ ____.
________ _____ _______ ____ ____ _____.
_______ ________ _______ ____ _______ __________ _________ __________ ________ __________ __________ _____.
_______ _______ ___ ______ _______ ______ _________ _________ ______ ________ ____.
____ ________ _________ ______ ____.
_________ ___ _____ ___ __________ __________ ____ __________.
_____ ___ ____ ________ ____ __________ _______ _____ ___ ________ ____ ____.
________ ______ ______ _____ ______ __________ ______ ______ _____ ____ _____.
___ __________ ___ _______ _________ ___ _________.
__________ _____ _________.
IGNOU ACADEMY
Your IGNOU journey, made easier.
- Solved Assignments
- Study Notes
- Guess Papers
- Question Papers
Continue Reading — It's Free
Sign in with Google to unlock more of this answer.
✓ Free access
✓ Unlock up to 60% of the answer
✓ No payment required
✓ Unlock up to 60% of the answer
✓ No payment required
Quick Google sign-in. No separate registration form.