Creating A Binary Tree From A General Tree in data structure

The rules for converting a general tree to a binary tree are given below. Note that a general tree is converted into a binary tree and not a binary search tree

Rule 1: Root of the binary tree = Root of the general tree

Rule 2: Left child of a node = Leftmost child of the node
in the binary tree in the general tree

Rule 3: Right child of a node
in the binary tree = Right sibling of the node in the general tree

Binary Tree
Binary Tree

Now let us build the binary tree

Step 1: Node A is the root of the general tree, so it will also be the root of the binary tree.

Step 2: Left child of node A is the leftmost child of node A in the general tree and right child of node A is the right sibling of the node A in the general tree. Since node A has no right sibling in the general tree, it has no right child in the binary tree

Step 3: Now process node B. Left child of B is E and its right child is C (right sibling in general tree).

binary-tree-steps
Binary-tree-steps

Step 4: Now process node C. Left child of C is F (leftmost child) and its right child is D (right sibling in general tree)

Step 5: Now process node D. Left child of D is I (leftmost child). There will be no right child of D because it has no right sibling in the general tree.

Step 6: Now process node I. There will be no left child of I in the binary tree because I has no left child in the general tree. However, I has a right sibling J, so it will be added as the right child of I.

Step 7: Now process node J. Left child of J is K (leftmost child). There will be no right child of J because it has no right sibling in the general tree

Binary-tree-steps
Binary-tree-steps

Leave a Comment