Creating a tree with Left-Child Right-Sibling Representation

Left-Child Right-Sibling Representation is a different representation of an n-ary tree where instead of holding a reference to each and every child node, a node holds just two references, first a reference to it’s first child, and the other to it’s immediate next sibling. This new transformation not only removes the need of advance knowledge of the number of children a node has, but also limits the number of references to a maximum of two, thereby making it so much easier to code.

```At each node, link children of same parent from left to right.
Parent should be linked with only first child.
```

Examples:

```Left Child Right Sibling tree representation
10
|
2 -> 3 -> 4 -> 5
|    |
6    7 -> 8 -> 9
```

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Prerequisite : Left-Child Right-Sibling Representation of Tree
Below is the implementation.

C++

 `// CPP program to create a tree with left child ` `// right sibling representation. ` `#include ` `using` `namespace` `std; ` ` `  `struct` `Node ` `{ ` `    ``int` `data; ` `    ``struct` `Node *next; ` `    ``struct` `Node *child; ` `}; ` ` `  `// Creating new Node ` `Node* newNode(``int` `data) ` `{ ` `    ``Node *newNode = ``new` `Node; ` `    ``newNode->next = newNode->child = NULL; ` `    ``newNode->data = data; ` `    ``return` `newNode; ` `} ` ` `  `// Adds a sibling to a list with starting with n ` `Node *addSibling(Node *n, ``int` `data) ` `{ ` `    ``if` `(n == NULL) ` `        ``return` `NULL; ` ` `  `    ``while` `(n->next) ` `        ``n = n->next; ` ` `  `    ``return` `(n->next = newNode(data)); ` `} ` ` `  `// Add child Node to a Node ` `Node *addChild(Node * n, ``int` `data) ` `{ ` `    ``if` `(n == NULL) ` `        ``return` `NULL; ` ` `  `    ``// Check if child list is not empty. ` `    ``if` `(n->child) ` `        ``return` `addSibling(n->child, data); ` `    ``else` `        ``return` `(n->child = newNode(data)); ` `} ` ` `  `// Traverses tree in level order ` `void` `traverseTree(Node * root) ` `{ ` `    ``if` `(root == NULL) ` `        ``return``; ` ` `  `    ``while` `(root) ` `    ``{ ` `        ``cout << ``" "` `<< root->data; ` `        ``if` `(root->child) ` `            ``traverseTree(root->child); ` `        ``root = root->next; ` `    ``} ` `} ` ` `  `//Driver code ` ` `  `int` `main() ` `{ ` `    ``/*   Let us create below tree ` `    ``*           10 ` `    ``*     /   /       ` `    ``*    2  3      4   5 ` `    ``*              |   /  | ` `    ``*              6   7  8  9   */` ` `  `    ``// Left child right sibling ` `    ``/*  10 ` `    ``*    | ` `    ``*    2 -> 3 -> 4 -> 5 ` `    ``*              |    | ` `    ``*              6    7 -> 8 -> 9  */` `    ``Node *root = newNode(10); ` `    ``Node *n1  = addChild(root, 2); ` `    ``Node *n2  = addChild(root, 3); ` `    ``Node *n3  = addChild(root, 4); ` `    ``Node *n4  = addChild(n3, 6); ` `    ``Node *n5  = addChild(root, 5); ` `    ``Node *n6  = addChild(n5, 7); ` `    ``Node *n7  = addChild(n5, 8); ` `    ``Node *n8  = addChild(n5, 9); ` `    ``traverseTree(root); ` `    ``return` `0; ` `} `

Java

 `// CPP program to create a tree with left child ` `// right sibling representation.  ` ` `  `class` `GFG { ` `     `  `    ``static` `class` `NodeTemp ` `    ``{ ` `        ``int` `data; ` `        ``NodeTemp next, child; ` `        ``public` `NodeTemp(``int` `data) ` `        ``{ ` `            ``this``.data = data; ` `            ``next = child = ``null``; ` `        ``} ` `    ``} ` `     `  `    ``// Adds a sibling to a list with starting with n ` `    ``static` `public` `NodeTemp addSibling(NodeTemp node, ``int` `data) ` `    ``{ ` `        ``if``(node == ``null``) ` `            ``return` `null``; ` `        ``while``(node.next != ``null``) ` `            ``node = node.next; ` `        ``return``(node.next = ``new` `NodeTemp(data)); ` `    ``} ` `         `  `    ``// Add child Node to a Node ` `    ``static` `public` `NodeTemp addChild(NodeTemp node,``int` `data) ` `    ``{ ` `        ``if``(node == ``null``) ` `            ``return` `null``; ` `     `  `        ``// Check if child is not empty. ` `        ``if``(node.child != ``null``) ` `            ``return``(addSibling(node.child,data)); ` `        ``else` `            ``return``(node.child = ``new` `NodeTemp(data)); ` `    ``} ` ` `  `    ``// Traverses tree in level order ` `    ``static` `public` `void` `traverseTree(NodeTemp root) ` `    ``{ ` `        ``if``(root == ``null``) ` `            ``return``; ` `        ``while``(root != ``null``) ` `        ``{ ` `            ``System.out.print(root.data + ``" "``); ` `            ``if``(root.child != ``null``) ` `                ``traverseTree(root.child); ` `            ``root = root.next; ` `        ``} ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `         `  `        ``/*   Let us create below tree ` `        ``*           10 ` `        ``*     /   /       ` `        ``*    2  3      4   5 ` `        ``*              |   /  | ` `        ``*              6   7  8  9   */` `      `  `        ``// Left child right sibling ` `        ``/*  10 ` `        ``*    | ` `        ``*    2 -> 3 -> 4 -> 5 ` `        ``*              |    | ` `        ``*              6    7 -> 8 -> 9  */` ` `  `        ``NodeTemp root = ``new` `NodeTemp(``10``); ` `        ``NodeTemp n1 = addChild(root,``2``); ` `        ``NodeTemp n2 = addChild(root,``3``); ` `        ``NodeTemp n3 = addChild(root,``4``); ` `        ``NodeTemp n4 = addChild(n3,``6``); ` `        ``NodeTemp n5 = addChild(root,``5``); ` `        ``NodeTemp n6 = addChild(n5,``7``); ` `        ``NodeTemp n7 = addChild(n5,``8``); ` `        ``NodeTemp n8 = addChild(n5,``9``); ` `         `  `        ``traverseTree(root); ` `    ``} ` `} ` ` `  `// This code is contributed by M.V.S.Surya Teja. `

Python3

# Python3 program to create a tree with
# left child right sibling representation.

# Creating new Node
class newNode:
def __init__(self, data):
self.Next = self.child = None
self.data = data

# Adds a sibling to a list with
# starting with n
if (n == None):
return None

while (n.Next):
n = n.Next
n.Next = newNode(data)
return n.Next

# Add child Node to a Node
if (n == None):
return None

# Check if child list is not empty.
if (n.child):
else:
n.child = newNode(data)
return n.child

# Traverses tree in level order
def traverseTree(root):
if (root == None):
return

while (root):
print(root.data, end = ” “)
if (root.child):
traverseTree(root.child)
root = root.Next

# Driver code
if __name__ == ‘__main__’:

# Let us create below tree
# 10
# / /
# 2 3 4 5
# | / |
# 6 7 8 9

# Left child right sibling
# 10
# |
# 2 -> 3 -> 4 -> 5
# | |
# 6 7 -> 8 -> 9
root = newNode(10)
traverseTree(root)

# This code is contributed by pranchalK

C#

 `// C# program to create a tree with left  ` `// child right sibling representation.  ` `using` `System; ` ` `  `class` `GFG ` `{ ` `public` `class` `NodeTemp ` `{ ` `    ``public` `int` `data; ` `    ``public` `NodeTemp next, child; ` `    ``public` `NodeTemp(``int` `data) ` `    ``{ ` `        ``this``.data = data; ` `        ``next = child = ``null``; ` `    ``} ` `} ` ` `  `// Adds a sibling to a list with ` `// starting with n  ` `public` `static` `NodeTemp addSibling(NodeTemp node, ` `                                  ``int` `data) ` `{ ` `    ``if` `(node == ``null``) ` `    ``{ ` `        ``return` `null``; ` `    ``} ` `    ``while` `(node.next != ``null``) ` `    ``{ ` `        ``node = node.next; ` `    ``} ` `    ``return` `(node.next = ``new` `NodeTemp(data)); ` `} ` ` `  `// Add child Node to a Node  ` `public` `static` `NodeTemp addChild(NodeTemp node, ` `                                ``int` `data) ` `{ ` `    ``if` `(node == ``null``) ` `    ``{ ` `        ``return` `null``; ` `    ``} ` ` `  `    ``// Check if child is not empty.  ` `    ``if` `(node.child != ``null``) ` `    ``{ ` `        ``return` `(addSibling(node.child,data)); ` `    ``} ` `    ``else` `    ``{ ` `        ``return` `(node.child = ``new` `NodeTemp(data)); ` `    ``} ` `} ` ` `  `// Traverses tree in level order  ` `public` `static` `void` `traverseTree(NodeTemp root) ` `{ ` `    ``if` `(root == ``null``) ` `    ``{ ` `        ``return``; ` `    ``} ` `    ``while` `(root != ``null``) ` `    ``{ ` `        ``Console.Write(root.data + ``" "``); ` `        ``if` `(root.child != ``null``) ` `        ``{ ` `            ``traverseTree(root.child); ` `        ``} ` `        ``root = root.next; ` `    ``} ` `} ` ` `  `// Driver code  ` `public` `static` `void` `Main(``string``[] args) ` `{ ` ` `  `    ``/* Let us create below tree  ` `    ``*         10  ` `    ``*     / /   ` `    ``* 2 3     4 5  ` `    ``*             | / |   ` `    ``*             6 7 8 9 */` ` `  `    ``// Left child right sibling  ` `    ``/* 10  ` `    ``* |  ` `    ``* 2 -> 3 -> 4 -> 5  ` `    ``*             | |  ` `    ``*             6 7 -> 8 -> 9 */` ` `  `    ``NodeTemp root = ``new` `NodeTemp(10); ` `    ``NodeTemp n1 = addChild(root, 2); ` `    ``NodeTemp n2 = addChild(root, 3); ` `    ``NodeTemp n3 = addChild(root, 4); ` `    ``NodeTemp n4 = addChild(n3, 6); ` `    ``NodeTemp n5 = addChild(root, 5); ` `    ``NodeTemp n6 = addChild(n5, 7); ` `    ``NodeTemp n7 = addChild(n5, 8); ` `    ``NodeTemp n8 = addChild(n5, 9); ` ` `  `    ``traverseTree(root); ` `} ` `} ` ` `  `// This code is contributed by Shrikant13 `

Output:

```10 2 3 4 6 5 7 8 9
```

tags:

Tree n-ary-tree Tree