CareerCup

The clue here is every node contains 0 or 2 childrens. So using this condition we can be sure that we can construct a tree using the given preorder.

node* constructTree( char *str) 
{
        static int index =0 ;

        if ( str[index] == '\0' )
               return NULL;
        else
        {

                  node * ptr = new node;
                  ptr->left = ptr->right = NULL;
 
                  if ( str[index] == 'N' )
                  {

                       index++;
                       ptr->data = 'N'
                       ptr->left  = constructTree(str) ;
                       ptr->right = constructTree(str);
                  }
                  else if ( str[index] == 'L' )
                  {
                         index++;
                         ptr->data = 'L'; 
                  }
                  return ptr;
        }
}

can you please explain the question in detail?

and please post some more questions for AMAZON bangalore..which u gave on 5'th feb

how can 1 construct a tree..with only preorder given...we also need the inorder for that

if only preorder is given then there can be many such trees.not a single unique 1..

I think in this particular case we can get a unique tree, but I m not sure.
1. root=NULL;
call MakeTree (&root, root, str, 0)

node* MakeTree (node** root, node* tempRoot, char* str, int* index)
{
if (str[*index])
{
tempRoot = makeNewNode ();/*some function which creates new
node and initialises node to 0*/
if (str [*index] == 'N')
{

if (*index == 0)
{
*root = tempRoot;
}
tempRoot->left = MakeTree (root, tempRoot->left, str, &((*index) ++));
tempRoot->right = MakeTree (root, tempRoot->right, str, &((*index) ++));
}
else
{
return tempRoot;
}
}
}

try this i assume traversal is in an array a.Call wud be Construct(new Node(),0)

int Construct(Node n,int i){
   if(a[i]=='N'){
      n.right=new Node();n.left=new Node();
      return Construct(n.right,Construct(n.left,i+1));
   }
   else
      return i+1;
}

Condition is every node will have 0 children or 2 children... If you encounter L then definitely it will have both child and verify to left

For preorder sequence LLNLNNLLNNLNN

                           L
                     L            L 
                  N     L      L     L
                       N  N   N N   N N 
They are just asking to construct the tree by seeing the sequence. not write the progam i think

#include "stdafx.h"
#include <iostream>
using namespace std;

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

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

int _tmain(int argc, _TCHAR* argv[])
{
	node *root= NULL;

	char a[] = {'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; i<n; i++)
	{
		int temp=0;
		insert(&root, a[i], temp);
	}

	preorder(root);cout << endl;
	cout << endl;

	return 0;
}

void insert(node **root, char d, int &flag)
{
	if(*root == NULL)
	{
		*root = new node;
		(*root)->data = d;
		(*root)->left = (*root)->right = NULL;
		flag = 1;
		return;
	}
	else
	{
		if((*root)->data == 'N')
			return;
		if((*root)->data == 'L')
		{
			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);
}

Can you please tell us the question for the program you have written?

My solution is to use recursion as you traverse the Pre-Order once.
1. First node is the Root as everyone know.
2. Reading the rest of the array.
if the character is N; keep it as left link if available or else right link of it.
if both are filled go to its parent and follow the same.
if the character is L; keep it as left link if available or else right link of it.
if both are filled go to its parent and follow the same.

Replace all instance of pattern NXY in the tree with the tree built as N.left = X and N.right = Y
where X,Y can be L or a previously built NXY.

public static void makeTree(){
		String preOrder = "NNNLLLL";
		Stack<Treenode> stck = new Stack<Treenode>();
		for(int i=0; i<preOrder.length(); i++){
			if(preOrder.charAt(i) == 'N'){
				Treenode tnode1 = new Treenode('N', false);
				stck.push(tnode1);
			}
			else{
				Treenode tnode = new Treenode('L', true);
				boolean flag = false;
				while(true){
						if(!(stck.isEmpty())){
							if(flag){
								tnode = stck.pop();
							}
							else{
								flag = true;
							}
							Treenode stcktop = stck.pop();
							if(stcktop.nodetype){
								if(!(stck.isEmpty())){
									Treenode nnode = stck.pop();
									nnode.left = stcktop;
									nnode.right = tnode;
									nnode.nodetype = true;
									stck.push(nnode);
									if(stck.size()==1)
										break;
								}
								else{
									stck.push(stcktop);
									stck.push(tnode);
									break;
								}
							}
							else{
								stck.push(stcktop);
								stck.push(tnode);
								break;
							}
						}
						else{
							stck.push(tnode);
							break;
						}
					}	
			}
		}
	}

where the constructor for Treenode is

class Treenode{
	Treenode left;
	Treenode right;
	char value;
	boolean nodetype;
	
	public Treenode(char val, boolean nodetype){
		this.value = val;
		this.nodetype = nodetype;
		this.left = null;
		this.right = null;
	}
}

@WgpShashank/anyone :- can u pls tell us the logic of the program.

Hi .. siva.sai .. did u cleared the amazon interview?

Hi .. siva.sai .. did u cleared the amazon interview?

Hi .. siva.sai .. did u cleared the amazon interview?

struct tree* construct_tree(char* A, int *i)
   {
    //Boundary Condition
      if (A == NULL){
         return NULL;
      }
   
      struct 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;
   }

struct tree * constructTree(char *inputArray, int arraySize, int *index)
{
             /* validating input */
	if( input == NULL || *index >= arraySize )
	{
		return NULL;
	}	
	else
	{
		struct tree newNode = (struct tree *) malloc ( sizeof(struct tree));
		newNode->data = inputArray[*index];
		newNode->left = newNode->right = NULL;
		
		*index = *index+1;
		
		if(inputArray[*index] == 'N')
		{
			newNode->left = constructTree(inputArray, arraySize, index);
			newNode->right = constructTree(inputArray, arraySize, index);
		}
		return newNode;
	}
}