We are given any m-ary tree, our goal is to convert that m-ary tree into a Binary Tree by following below steps:
- Insert an edge connecting all the sibling of the given n-ary tree.
Insert Edge connecting the siblings - Delete all the parent edges from the parent to its children except the one to its leftmost child.
Delete all edges from a parent to its child except the leftmost one. - Rotate the resulting tree by 45degress to differentiate between its left and right subtree.
3-ary tree converted into a Binary Tree
The Time Complexity of converting an m-ary tree to Binary tree is O(N + E), N is the number of nodes in the tree and E is the number of the edges in the intermediate tree created after step 1.
Preorder, Inorder & Postorder of the resultant tree are
Preorder: V1, V2, V5, V6, V3, V4, V7, V9, V10, V11, V8
Inorder: V5, V6, V2, V3, V9, V10, V11, V8, V4, V1
Postorder: V6, V5, V11, V10, V9, V8, V7, V4, V3,V2, V1
This is vague. For example, why didn’t you remove V4 to V8 edge?
P.s: My last comment is incomplete. Please ignore that!