Given a normal binary tree, convert it to Left-child right-sibling (LC-RS) binary tree.

Each node in LC-RS binary tree has two pointers: one to the node’s left child, and one to its next sibling in original binary tree. So starting with the root, each node’s leftmost child in the original tree is made its left child in the LC-RS binary tree, and its nearest sibling to the right in the original tree is made its right child in the binary tree. For example, we have a binary tree below:

1 1 1

/ \ / /

/ \ / 2

2 3 **——>** 2 ———- 3 / \

/ \ / / / 4 \

4 5 6 4 —– 5 6 \ \

/ \ / 5 3

7 8 7 —— 8 /

6

(a) (b) /

7

\

8

(c)

(a) Processing binary tree to LC-RS binary tree, every node is linked and aligned with the left

child, and the next nearest is a sibling.

(b) We can re-write binary tree shown by putting the left child node to one level below its parents

and by putting the sibling next to the left child at the same level.

(c) We can transform this tree to a binary tree by turning each sibling 45° clockwise.

The idea is to traverse the tree in postorder fashion and for every node

- If its left child is empty, then make its right child as left’s and set right to null.
- If left child already exists, then make right child of its left child to point to its right child and set right child to null.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Function to convert a normal binary tree to Left-child // right-sibling (LC-RS) binary tree void convert(Node *root) { // base case: empty tree if (root == nullptr) return; // recursively convert left and right subtree first convert(root->left); convert(root->right); // if left child is empty, then make right child as left's // and set right to null if (root->left == nullptr) { root->left = root->right; root->right = nullptr; } // if left child already exists, then make right child of the // left child to point to right child of current node and // set current right child as null else { root->left->right = root->right; root->right = nullptr; } } |

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

**References:**

https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂