CareerCup

//let preorder traversal of a tree be in a array t
  for(i = t.length; i>-1; i--){
     
     if(t(i) == L){
         stack.push(t[i]);
     }else{
         leftChild = s.pop(); // will return null if stack is empty
         rightChild = s.pop(); // will return null if stack is empty
         node = new Node(leftChild, rightChild);
         stack.push(node);
     }
     
  }

  root = stack.pop(); // get the root from the stack;

from what the OP posted, there is no way to reconstruct a tree from the preorder sequence because there is no one-to-one relationship. for example

N and N both have the preorder sequence N,N,L,L,
/ \ /
N L N
/ / \
L L L
if the number of children of each node is given, it is another story

We have to provide a tree which gives the given preorder traversal. What is the problem if there are multiple trees, your solution tree should give the preorder traversal same as mentioned. Since their can be multiple approaches, hence multiple tree solutions. Initially 'CodeGeek' one solution which is correct according to his approach and he can create a tree which gives the same order as given in the ques. Then how this question arises that it will not work for right sided tree ??

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.

You can find the WORKING code here : cslabprograms.blogspot.com/2011/02/nl-tree.html

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.

You can find a working program here:
cslabprograms.blogspot.com/2011/02/nl-tree.html

Very much straight forward.. you should be given either a (singly or doulbly) linked list of pre-order traversal i.e. (Root)N->N->N->N->N->N->L->L->N->N->N->N->L
You need to trick the pointers for following 2 cases
1. N->L->L : this is the node with 2 childs..so N->left= 1st L and N->right= 2nd L
2. N->L->N : node has 1 child...so N->left/right = L ... if BST the check if(N>L) then N->left = L otherwise its a right child
Note: By assuming BST to be desired tree, check for values to decide if left or right child..in case of just BT can be set to either of them.

Since the nodes are marked with leafs / nodes its possible to build a tree with this

chiragjain1989,

The above code will fail for below tree model: only right sided tree is there

30

40

50

@CodeGeek..i think it will not in the below tree

A
/ \
B C
/\ / \
D E F G

pre-order traversal will be A->B->D->E->C->F->G..

how will u reconstruct tree for the above one..

A
 \
  B

and 
  A
 /
B

both are two different trees but with same post-order, even with the N L notation.
what about such case ?

so it is true that it is not possible to generate tree from just one traversal given.

We can reconstruct tree from preorder, if the tree is BST and every node in the left sub-tree less than pivot, every node in the right sub-tree greater than pivot

Yes thats true. But in question it was not mentioned that tree is BST.

hi... from pre-order traversal v can construct a unique tree if N and L info given, provided the condition mentioned "every node can have 0 or at most 2 nodes" is actually "every node can have 0 or 2 nodes", i.e. a node is not allowed to have a single child, coz that will create confusion as to whr it will go, left or right... otherwise the first N next to an N in the list will go to left, which solves the problem.

@mail2maulish .. does a node allowed to have just 1 child ?

do we have to write executable code during phone interview

{
//let preorder traversal of a tree be in a array t
for(i = t.length; i>-1; i--){

if(t(i) == L){
stack.push(t[i]);
}else{
leftChild = s.pop(); // will return null if stack is empty
rightChild = s.pop(); // will return null if stack is empty
node = new Node(leftChild, rightChild);
stack.push(node);
}

}

root = stack.pop(); // get the root from the stack;
}

@sudhir: Your code will not work.

A pre order traversal will loose the structure of the tree.If it shudnt a node should have both child or none.If this is de case then foll code shud work
i assume the traversal is in an array

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

Initial call wud be Construct(new Node(),0)

Guys, I think the question is ambiguous.
suppose we have two trees:
N N
/ \ /
N N N
/ \ / \
L L L N
\
L
The pre-order traversal of both trees is: N N L N L

@sudhir,@verma.tech Can you please provide asap......I tried it but not succeed

Reply asap.

It is not possible to rebuild the tree from this.
e.g. NNNLLL can be
N
N L
N L
L

or


N
N
N L
L L

It is given that the node will have 0 or 2 children. Let N be represented by 1 and L be represented by 0 , so the code is

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;

char str[100];
int l ;
typedef struct node
{
        int num;
        struct node* left;
        struct node* right;
}node;

node * func ( int index , node * t)
{
        if(index >= l )
                return t;
        if(str[index] == 'L')
        {
                node * temp;
                temp = (node*)malloc(sizeof(node));
                temp->num = 0;
                temp->left = NULL;
                temp->right = NULL;
                t = temp;

                return temp;
        }
        else
        {
                t = (node*)malloc(sizeof(node));
                t->num = 1;
                t->left = func(index + 1, t->left);
                t->right = func(index + 1 , t->right);
        }
        return t;
}
void printtree( node * t)
{
        if(t)
        {
                printf("%d\n",t->num);
                printtree(t->left);
                printtree(t->right);
        }
}
int main()
{
        node * t;
        scanf("%s",str);
        l = strlen(str);
        t = func(0,t);
        printtree(t);
        return 0;
}

I just have a pseudocode of sort that would probably work.

static preIndex = 0
BuildTree(PreOrder[])
{
Node *tNode = newNode(PreOrder[preIndex++]);
if(tNode->val = "L") then return tNode;
tNode->left = BuildTree(preOrder[])
tNode->right = BuildTree(preOrder[])
return tNode
}

root = BuildTree(PreOrder[]) is the call to be made.

<pre lang="" line="1" title="CodeMonkey97684" class="run-this">node *formTree(string& str)
{
int n=str.length();

Stack<node*> mystack;
node *root=NULL;

for(int i=0;i<n;i++){
node *temp=new node;
temp->left=temp->right=NULL;

if(str[i]=='N'){
temp->data='N';

}
else if(str[i]=='L')
temp->data='L';
//cout<<"\nNode constructed. Value is "<<temp->data;

//connect it to the tree
if(!root) root=temp;
else {
while(mystack.isNotEmpty()){
node *tos=mystack.peek();
if(tos->left==NULL){
tos->left=temp;
break;
}
else if(tos->right==NULL){
tos->right=temp;
break;
}
else mystack.pop();
} //end of while

}
if(str[i]=='N') mystack.push(temp);

} //end of for-loop

//if(mystack.isNotEmpty()) cout<<"\nSome error";
return root;
}


</pre><pre title="CodeMonkey97684" input="yes">
</pre>

My solution : using a stack to reconstruct the tree( assumption: there is NO node which have only one child , in that case, tree's shape is not deterministic )
input is a integer array, positive number means “Node”, negative number means “Leaf”
1 if current cell is N, push tp stack
2 if current cell is L, make it to top’s left child (if no left child yet), otherwise make it as right child
3 if top have two children already, then pop, and make it as new top’s left or right child( left have priority than right, because go through left-right preorddr traversal ), then check the new top, if it have two children alreay, keep popping

// positive number means “Node”, negative number means “Leaf”
NodePosition     BuildTree(int *input, int len)
{
	stack<NodePosition> stk;
	NodePosition temp, root;

	for( int i = 0 ; i < len; i++)
	{
		// current node is “Node”
		if (input[i] > 0 )
		{
			temp = (NodePosition)malloc(sizeof(TreeNode));
			temp->Element = input[i];
			temp->Left = temp->Right = NULL;
			stk.push(temp);
			if (i == 0)
				root = temp;
		}
		else
		// current node is “Leaf”
		{
			temp = (NodePosition)malloc(sizeof(TreeNode));
			temp->Element = input[i];
			temp->Left = temp->Right = NULL;

			// save as top’s left child
			if (stk.top()->Left == NULL)
				stk.top()->Left = temp;
			else if(stk.top()->Right == NULL )
			// save as top’s right child and pop back
			{
				stk.top()->Right = temp;

				// keep popping until top’s right is NULL 
				while(stk.top()->Left && stk.top()->Right)
				{
					temp = stk.top();
					stk.pop();
					if (stk.empty())
						break;
					if (stk.top()->Left == NULL)
						stk.top()->Left = temp;
					else
						stk.top()->Right = temp;
				}
			}
		}
	}
	return root;
}

String s = "nnnlllnll";
        LinkedList<String> string = new LinkedList<String>();
        for (int i = 0; i < s.length(); i++) {
            string.add(s.charAt(i) + "");
        }

private static Node conTree(LinkedList<String> string) {
        if (string.isEmpty()) return null;
        String data = string.pop();
        Node node;
        if (data.equals("n")) {
            node = new Node(data);
            node.setLeft(conTree(string));
            node.setRight(conTree(string));
        } else {
            node = new Node(data);
        }
        return node;
    }

Steps:
Iterate the array recursively
at each call create node and update its key
if it is leaf node, return the newly created node
if not leaf node, call function to update left and right child nodes.
We need a pointer to keep track of location in array.

#include <stdio.h>
#include <stdlib.h>
//Definition of Node
struct node
{
	int key;
	struct node* left;
	struct node* right;
	};
typedef struct node Node;

//Recursive function
Node* preorderTree(int* array,int* nodearray,int* i, int size)
{
        int prev=*i;        
        Node* newnode=(Node*)malloc(sizeof(Node)) ;
        newnode->key=*(array+*i);
       
		*i=*i+1;
        if(*(nodearray+prev)==0)
            {             
                newnode->left=NULL;
                newnode->right=NULL;
                return newnode;
            }
        else if(*i<size)
        {            
            newnode->left=preorderTree(array,nodearray,i,size);
			newnode->right=preorderTree(array,nodearray,i,size);            
            return newnode;
        }        
              
}

//Test Code
int main()
{
	int array[5]={15,5,25,20,35};
    int nodearray[5]={1,0,1,0,0};
    int a=0;
	int arraysize=5;
    Node* result=NULL;

    result=preorderTree(array,nodearray,&a,arraysize);
    	
}