Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Advantages and Disadvantages of Left Child Right Sibling Representation
3.
Frequently Asked Questions
3.1.
What is N-Ary Tree?
3.2.
What is the different TreeTraversals Technique?
3.3.
What is Breadth-First Search?
4.
Conclusion 
Last Updated: Mar 27, 2024
Medium

Create a tree with Left-Child Right Sibling

Author 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
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

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

Frequently Asked Questions

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

What is Breadth-First Search?

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!

Previous article
Populate Inorder Successor for all node
Next article
Clockwise Triangular Traversal of a Binary Tree
Live masterclass