text: 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
explanation: The provided text extract is a detailed explanation of how to create a tree using the Left-Child Right Sibling representation. It includes an introduction, problem statement, sample example, approach, and implementations in C++ and Java. The text also contains a few questions and their answers, such as "What is an N-Ary Tree?" and "What is the different TreeTraversals Technique?"
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: 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
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The provided text extract is a detailed explanation of how to create a tree using the Left-Child Right Sibling representation. It includes an introduction, problem statement, sample example, approach, and implementations in C++ and Java. The text also contains a few questions and their answers, such as "What is an N-Ary Tree?" and "What is the different TreeTraversals Technique?"
  
  Label: multiple-question-and-answer