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
Node *AddSibling(Node *FirstChild, int data)
{
// 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
Node *AddChild(Node *ParentNode, int data)
{
if (ParentNode == NULL)
return NULL;
// Check if child list is not empty,then we add sibling
if (ParentNode->child)
return AddSibling(ParentNode->child, data);
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);
Node *n1 = AddChild(root, 2);
Node *n2 = AddChild(root, 3);
Node *n3 = AddChild(root, 4);
Node *n4 = AddChild(n1, 5);
Node *n5 = AddChild(n1, 6);
Node *n6 = AddChild(n2, 7);
Node *n7 = AddChild(n2, 8);
Node *n8 = AddChild(n5, 9);
Node *n9 = AddChild(n5, 10);
Node *n10 = AddChild(n5, 11);
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
AddSibling(Node node, int data) {
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)
return (AddSibling(node.child, data));
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);
Node n1 = AddChild(root, 2);
Node n2 = AddChild(root, 3);
Node n3 = AddChild(root, 4);
Node n4 = AddChild(n1, 5);
Node n5 = AddChild(n1, 6);
Node n6 = AddChild(n2, 7);
Node n7 = AddChild(n2, 8);
Node n8 = AddChild(n5, 9);
Node n9 = AddChild(n5, 10);
Node n10 = AddChild(n5, 11);
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
Advantages and Disadvantages of Left Child Right Sibling Representation
Advantages:
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.
Disadvantages:
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