Home Data Structures Convert any m-ary tree (General Tree) to a Binary Tree

# Convert any m-ary tree (General Tree) to a Binary Tree

We are given any m-ary tree, our goal is to convert that m-ary tree into a Binary Tree by following below steps:

1. Insert an edge connecting all the sibling of the given n-ary tree.

2. Delete all the parent edges from the parent to its children except the one to its leftmost child.

3. Rotate the resulting tree by 45degress to differentiate between its left and right subtree.

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

#### 1 COMMENT

1. This is vague. For example, why didn’t you remove V4 to V8 edge?
P.s: My last comment is incomplete. Please ignore that!