CareerCup

If we assume that tree nodes either have 0 or 2 nodes, then the tree constructed should be unique. Build the tree in recursion just like a preorder traverse.

public class Main {
   private String _str;

   class Node {
      public int index;
      public Node left, right;
   }

   public Main(String str) {
      _str = str;
   }

   private Node buildTreePreorder(int curIndex) {
      Node cur = new Node();
      cur.index = curIndex;
      if (_str.charAt(curIndex)=="N") {
         cur.left = buildTreePreorder(cur.index + 1);
         cur.right = buildTreePreorder(cur.left.index + 1);
      }
      return cur;
   }

   public static void main(String[] args) {
      Main main = new Main("NNNLLLL"); // test string
      Node root = main.buildTreePreorder(0);
   }
}

is it possible?
A
B
CD
and
A
BD
C
preorder and marks are all the same:
(A,N)(B,N)(C,L)(D,L)

what if introducing left and right extra characters (denoting null) for leaf nodes?

Node* formtree(char *preorder, int &num)
{
   if(preorder[num]=='\0') return NULL;
   Node *t=new Node();
   if(preorder[num++]=='L')
   {
      t->left=t->right=NULL;
   }
   else
   {
      t->left=formtree(preorder,num);
      t->right=formtree(preorder,num);
   }
   return t;
}

its the other way to ask the same question in which given the preorder of tree & construct the tree with preorder..isn't it you may wants to look @ this & can modify if need to achieve answer

http dot shashank7s dot blogspot dot com/2011/03/special-type-of-tree-is-given-where-all dot html

correct me if anything wrong