1.
Introduction
1.1.
What is an N-Ary Tree?
1.2.
Left-Child Right Sibling Representation
1.3.
Problem Statement
1.4.
Sample Example
2.
Approach
2.1.
Implementation in C++
2.2.
Implementation in Java
2.3.
3.
3.1.
What is N-Ary Tree?
3.2.
What is the different TreeTraversals Technique?
3.3.
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Create a tree with Left-Child Right Sibling

Sarthak
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

## Introduction

Today, we will discuss our topic on how to create a tree from Left-Child Right Sibling. It is actually a different representation of N Ary-Tree. This comes as one of the Interview's favorite Questionnaires. We will have some insights about N-Ary Tree before jumping to the creation of Tree. Do you want to crack this interview question and wanna become a Ninja? Just follow this.

### What is an N-Ary Tree?

It is similar to Binary Tree, but a node can have a maximum of n children. It is slightly different from Binary Tree. The children of any node have their children, themselves being N-Ary Tree with one "level" of depth less than their parents.

Fig: Binary Tree

To represent the N-Ary Tree, We have to use an array of n(=3 in the figure) pointers to store children. This representation is a memory-consuming approach, as we don't know the number of children a node can have. Hence, We come up with optimized approach for storing nodes, i.e., Left-Child Right Sibling Approach.

### Left-Child Right Sibling Representation

In this type of representation, a node holds two links, first a link to its first child and the other link to its immediate next sibling. In this representation, a link between two nodes can be a parent-child relationship or sibling-sibling relationship.

Fig: Left-Child Right Sibling

### Problem Statement

You are given a binary tree with n nodes. Now, You have to create a new tree in the form having nodes as left child right siblings.

### Sample Example

Input:

``In the input, we are given a Binary Tree as shown in the above fig: Binary Tree.``

Output:

``````The Depth First Traversals of the tree is as follows
1 2 5 6 9 10 11 3 7 8 4``````

The output shows Depth First Traversals which depicts the Left-Child Right Sibling of the Tree.Here, you can see how the formation of left-child right sibling takes place above.

## Approach

• The process of converting from an N-Ary tree to a Left-Child Right Sibling binary tree is called the Knuth transform.
• Here, We have to create two things for a node only, left child and right sibling.
• First, We create a root node.
• Now, we create children of the root node and then children of their nodes.
• If the parent given to us is NULL, then we return NULL.
• If we have some child of the parent node, then we attach it to the end of all siblings; else, we link it as a child node.

### Implementation in C++

``````// Cpp Program for creating a tree with left child right sibling representation.
#include <iostream>
using namespace std;
// Structure of the Node
struct Node
{
int data;
struct Node *next;
struct Node *child;
};
// Creating a new Node
Node *newNode(int data)
{
Node *newNode = new Node;
newNode->next = newNode->child = NULL;
newNode->data = data;
return newNode;
}
// Adds a sibling of a common Parent Node
{
// If root Node Is NULL return NULL
if (FirstChild == NULL)
return NULL;
// Traversing the linked List while we reach to the last node we traverse.
while (FirstChild->next)
FirstChild = FirstChild->next;
return (FirstChild->next = newNode(data));
}
// Add child Node to a Parent Node
{
if (ParentNode == NULL)
return NULL;
// Check if child list is not empty,then we add sibling
if (ParentNode->child)
else
return (ParentNode->child = newNode(data));
}
// Traversing of Tree in depth-first 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()
{
Node *root = newNode(1);
cout<<”The Depth First Traversals of tree is as follows”<<endl;
TraverseTree(root);
return 0;
}``````

Output:

``````The Depth First Traversals of tree is as follows
1 2 5 6 9 10 11 3 7 8 4``````

### Implementation in Java

``````class Ninja {
static class Node {
int data;
Node next, child;
public
Node(int data) {
this.data = data;
next = child = null;
}
}
// Adding a sibling to a list with starting with n
static public Node
if (node == null)
return null;
while (node.next != null)
node = node.next;
return (node.next = new Node(data));
}
// Adding child Node to a Node
static public Node AddChild(Node node, int data) {
if (node == null)
return null;
// Check if child is not empty.
if (node.child != null)
else
return (node.child = new Node(data));
}
// Traverses tree in level order
static public void TraverseTree(Node temp) {
if (temp == null)
return;
while (temp != null) {
System.out.print(temp.data + " ");
if (temp.child != null)
TraverseTree(temp.child);
temp = temp.next;
}
}
// Driver code
public static void main(String args[]) {
Node root = new Node(1);
System.out.print("The Depth First Traversals of tree is as follows\n");
TraverseTree(root);
}
}``````

Output:

``````The Depth First Traversals of tree is as follows
1 2 5 6 9 10 11 3 7 8 4``````

1. The Left Child Right Sibling representation is more space-efficient than a traditional multiway tree. The memory requirement for this representation is less, as we have to store only references, one is of child node and the other is of siblings.

2. It is easier to code and implement as it builds upon the binary tree data structure.

Operations such as searching, insertion and deletion take a long time because, in order to find the right element or position, we would have to traverse through all the siblings of the node to be searched, inserted, and deleted.

Check out this problem - Diameter Of Binary Tree

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

#### What is N-Ary Tree?

The N-ary Tree is a tree that has n number of children at a particular node; hence it is named N-ary. The difference between N-Ary Tree and Binary Tree is the shape. Also, It takes less space as compared to the Binary tree.

#### What is the different TreeTraversals Technique?

Some of the common tree traversing algorithms are as follows:-

• Preorder Traversal
• Inorder Traversal
• PostOrder Traversal

Breadth-First Search is a vertex-based algorithm. It is used for finding the shortest path in a graph. It is also known as Leval Order Traversal and can be Implemented using Queue Data Structure.

## Conclusion

In this article, we learned how to make a Tree in Left-Child Right Sibling Representation,

We also understand its approach and then learned its Implementation in different Languages.

We hope you learned how to utilize space properly using this approach.

Suggested problems are Construct a Binary Tree From Preorder and Postorder,Construct a Binary Tree From its Linked-List Representation, and many more.

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingDBMSSystem DesignWeb Development, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. You must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Live masterclass