Homework SourseSuppose that you are given two sequences of elements corresp
Suppose that you are given two sequences of elements corresponding to the inordersequence and the preorder sequence.Prove that it is possible to reconstruct a uniquebinary tree
Solution
14. Algorithm
lets take an example preorder: ABCDEFGHIJKLM
inorder: CEDFBAHJIKGML
preorder first element , root =A
In inorder elements left to A, left subtree = CEDFB
In inorder elements right to A ,right subtree = HJIKGML
A
next element in preorder = B
In inorder elements left to B, left subtree = CEDF
In inorder elements right to B ,right subtree = null
A
/
B
next element in preorder = C
In inorder elements left to C, left subtree = null
In inorder elements right to C ,right subtree = EDF
A
/
B
/
C
next element in preorder = D
In inorder elements left to D, left subtree = E
In inorder elements right to D ,right subtree = F
A
/
B
/
C
\\
D
/ \\
E F
Right subtree of A = HJIKGML
next element in preorder = G
In inorder elements left to G, left subtree = HJIK
In inorder elements right to D ,right subtree = ML
A
/ \\
B G
/
C
\\
D
/ \\
E F
next element in preorder =H
In inorder elements left to H, left subtree = null
In inorder elements right to H ,right subtree = JIK
A
/ \\
B G
/ /
C H
\\
D
/ \\
E F
next element in preorder =I
In inorder elements left to I, left subtree = J
In inorder elements right to I ,right subtree = K
A
/ \\
B G
/ /
C H
\\ \\
D I
/ \\ / \\
E F J K
next element in preorder =L
In inorder elements left to L, left subtree = M
In inorder elements right to L ,right subtree = null
A
/ \\
B G
/ / \\
C H L
\\ \\ /
D I M
/ \\ / \\
E F J K
