Java program to build NL Tree from preorder traversal

There exists a special kind of tree which has the node value 'N' if it is an internal node
and 'L' if it is a leaf node. An internal node can have either 0 or 2 children, not 1. Build the tree from preorder traversal.

The algorithm works based on the concept that number of leaf nodes=number of internal nodes+1.
(This is true only if internal node can have either 0 or 2 children, not 1).

Count from the beginning of the preorder array and when number of internal nodes==number of leaf node, that means, it is the end of the left subtree.
Now recursively call the routine with the sub array containing the left subtree and with the
sub array containing the right subtree.
Finally join the left subtree and the right subtree with the root.


public TreeNode buildNLTree(char[] preorder)
{
int length_p=preorder.length;
if(length_p<1 )
{
//Wrong input
return null;
}

if(length_p==1)
{ //Stop condition for the recursion;
TreeNode node=new TreeNode();
node.left=null;
node.right=null;
node.data=preorder[0];
return node;
}

int n_count=0,l_count=0;
int pos_right_sub_tree=0;

for(int i=0;i<length_p;i++)
{
if(preorder[i]=='N')
n_count++;
else
l_count++;

if(n_count==l_count)
{
pos_right_sub_tree=i+1;
break;
}
}

char[] newpreorder_left=new char[pos_right_sub_tree-1];
char[] newpreorder_right=new char[length_p-pos_right_sub_tree];

System.arraycopy(preorder, 1, newpreorder_left, 0, pos_right_sub_tree-1);
System.arraycopy(preorder, pos_right_sub_tree, newpreorder_right, 0, length_p-pos_right_sub_tree);

TreeNode treeroot=new TreeNode();
treeroot.data=preorder[0];

TreeNode leftsubtree=buildNLTree(newpreorder_left);
TreeNode rightsubtree=buildNLTree(newpreorder_right);

treeroot.left=leftsubtree;
treeroot.right=rightsubtree;

return treeroot;
}