A Special Binary Tree is given, Where all leaf are marked with L and others are marked with N. every node can have 0 or at most 2 nodes.

Problems: Given a preorder traversal of tree as a string 'NNLLNLL' Non-leaf nodes are labelled N and Leaf ndoes are labelled L. Each node has either 0 or 2 children. Construct the tree given the preorder traversal string.

Explanation & Approaches

As we should see how pre-order traversal is arranged. Pre-order traversal means first put root node, then pre order traversal of left subtree and then pre order traversal of right subtree. As shown in below figure:

In normal scenario, it’s not possible to detect where left subtree ends and right subtree starts using only pre-order traversal. But here, we are given a special property. Since every node has either 2 children or no child, we can surely say that if a node exists then its sibling also exists. So every time we are computing a subtree, we need to compute its sibling subtree as well.

Secondly, whenever we get ‘L’ in the input string, that is a leaf so we can stop for a particular subtree at that point. So after this ‘L’ node (left child of its parent ‘L’), it’s sibling starts. If ‘L’ node is right child of its parent, then we need to go up in the hierarchy to find next subtree to compute.

Keeping above invariant in mind, we can easily determine, when a subtree ends and next start. It means that we can give any start node to our method and it can easily complete the subtree it generates w/o going outside its nodes.

We just need to take care, that we are passing correct start nodes to different subtrees.

Data Structure Used: Array & Binary Tree

Algorithm:
1.Check if Array is NULL or Not if yes return NULL //base Condition
2.if Array is Not Null then create node one by one element start from 0th index to n-1 index in
array .
3. Check if array value at ith index is L id yes then simply return that Node.
4 else increment i then call for left subtree
5 again increment i=i+1 call for right subtree

#include
using namespace std;

struct node
{
node *left;
char data;
node *right;

};


void insert(node **root, char d, int&);
void preorder(node *root);


int main()
{
node *root= NULL;


char a[] ={'N','N','N','L','L','L','L'};
//11 Test Cases Below How Much You More Wants
//{'N'};
//{'N','L','L'};
//{'N','N','L','L','N','L','L'};
//{'N','N','N','L','L','L','L'};
//{'N','L','N','L','N','L','L'};
//{'N','N','N','L','L','N','L','L'};
//{'N','L','N','N','L','L','N','L','L'};
//{'N','N','N','L','L','N','L','L','N','L','L'};
//{'N','N','L','L','N','N','L','L','N','L','L'};
//{'N','N','N','L','L','N','L','L','N','N','L','L','N','L','L'};
//{'L', 'N', 'L', 'L', 'L', 'N', 'N', 'N', 'L', 'N', 'L', 'L', 'N', 'N', 'L', 'N', 'N',};
int n = sizeof(a) / sizeof(char);

for(int i=0; idata = d;
(*root)->left = (*root)->right = NULL;
flag = 1;
return;
}
else
{
if((*root)->data == 'L')
return;
if((*root)->data == 'N')
{
insert(&(*root)->left, d, flag);
if(flag == 0)
insert(&(*root)->right, d, flag);
}
}
}

void preorder(node *root)
{
if(root == NULL)
return;


cout << root->data << " "; preorder(root->left);
preorder(root->right);
}


Time Complexity O(n)
Space Complexity O(1) if Stack Space is Not Considered else O(n)
Run Here https://ideone.com/O4m6n

Above Code Can be Made More Clear & Optimize by removing
tree* construct_tree(char* A, int *i)
{
//Boundary Condition
if (A == NULL)
{
return NULL;
}

tree *node = newnode(A[*i]);
//On reaching leaf node, return
if (A[*i] == 'L'){
return node;
}

//Populate left sub tree
*i = *i + 1;
node->left = construct_tree(A, i);

//Populate right sub tree
*i = *i + 1;
node->right = construct_tree(A, i);

return node;
}

Run Here https://ideone.com/gYTWC

Java Program Using Parent Node



import java.io.Console;

public class Node{
public Node parent;
public Node left;
public Node right;
public char label;

public Node(Node parent,Node left, Node rigth, char label){
this.parent = parent;
this.left = left;
this.right = right;
this.label = label;
}

public static void main(String[] args){
Console console = System.console();
String preorder = console.readLine("Enter the preorder traversal string:");
Node root = null;
Node current = null;

for(int i = 0; i if(preorder.charAt(i)=='N'){
if(root==null){
root = new Node(null,null,null,'N');
current = root;
} else {
if(current.left==null){
Node temp = new Node(current,null,null,'N');
current.left = temp;
current = temp;
} else if(current.right==null){
Node temp = new Node(current,null,null,'N');
current.right=temp;
current = temp;
}
}
} else {
if(root==null){
root = new Node(null,null,null,'L');
current = root;
break;
} else {
if(current.left==null){
Node temp = new Node(current,null, null, 'L');
current.left = temp;
} else if(current.right==null){
Node temp = new Node(current, null,null,'L');
current.right=temp;
while(current!=null && current.right!=null){
current = current.parent;
}
}
}
}
}
System.out.println("==== Preorder traversal of tree constructed ======");
inorderTraversal(root);
System.out.println();
System.out.println("==================================================");
}

public static void inorderTraversal(Node root){
if(root!=null){
System.out.print(root.label);
inorderTraversal(root.left);
inorderTraversal(root.right);
}
}
}

Time Complexity O(N)
Space Complexity O(1)
Run Here http://ideone.com/T4fhM