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:

Given a Normal 3-ary (non-binary) tree
Given a Normal 3-ary (non-binary) tree

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

    Insert Edge connecting the siblings
    Insert Edge connecting the siblings
  2. 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.
  3. Rotate the resulting tree by 45degress to differentiate between its left and right subtree.

    Binary Tree
    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

Subscribe to our weekly newsletter

Join our community of 1000+ developers and stay updated with the fast moving world of computer science

We promise, we won't spam
Even we hate spam as much as you hate them

LEAVE A REPLY

Please enter your comment!
Please enter your name here