Amazon Interview Question Software Engineer / Developers
Country: India
Why global variable, when you attempt Amazon online test, you don't have access to main function. So when their main function will run it twice, it will fail for second test, and onwards.
"preOrderList" is a list storing preorder traversal of the tree. If the current root node is at 'i', left node is always stored at the 'i+1'th position.
We can pass the variable as reference parameter if global is not desired.
Stack s1;
node nList[N];
for (i=0;i<N;i++){
if (preorderList[i].type=='N' && nList[i].parent==NULL){
nList[i].parent = pop(s1);
s1.push(i);
nList[i].left = i+1;
nList[i+1].parent=i;
}
else if (preorderList[i].type=='S' && nList[i].parent==NULL){
nList[i].parent = pop(s1);
nList[i].parent.right = i;
}
}
Good solution. Just one more case i guess. check this pre-order:
n1
/ \
l1 n2
/ \
n3 n4
/ \ / \
l2 l3 l4 l5
the preorder for this is n1,l1,n2,n3,l2,l3,n4,l4,l5
by your logic when the loop ends, the stack has still n2 and n0. so after the loop ends, should we connect n2 and n0 (i.e. remaining elements in the stack) as parents and children as well
Aren't you assuming that there is a parent pointer for each node ?
if it's not the case, the following soln works:
char pre_order[];
int sz = sizeof(pre_order);
stack<node *> S;
note *root, *parent = 0;
for(int idx = 0; idx < sz; idx++) {
node *t = new node;
if(parent != 0) {
if(parent->left == 0)
parent->left = t;
else
parent->right = t;
} else {
root = t;
}
if(pre_order[idx] == 'N') {
parent = t;
S.push(t);
} else if(!S.empty())
parent = S.pop();
}
}
This is essentially like constructing an expression tree from the prefix expression. The L's are operands and the N's are operators. Parse the string from reverse and push the L's in a stack. For every N, pop two L's, make them the N's children and push it in the stack. Repeat until the string ends.
// getNextvalue is a pointer to a function which reads the next value if present or returns -1 if not present
typedef struct node * link ;
link make_tree(link_to_func getNextvalue )
{ int t;
if((t=getNextvalue())==-1)
return NULL;
link head=new node(t,NULL,NULL);
head->left=make_tree(getNextptr);
head->right=make_tree(getNextptr);
return head;
}
//we cannot get the exact tree we can get one of the possible trees which gives the inorder as the given sequence
Please note, that pre-order is given, not in-order.
And we can get the exact tree, considering the other constraint given. (0 and 2 children)
/*
struct Node
{
char val;
Node* left;
Node* right;
};
*/
// p/P -non-leaf node and L/l - leaf node
Node* createBinaryTree(string str)
{
stack<Node*> stk;
size_t length = str.length();
Node * root = new Node();
if(str.empty())
{
cout<<"Error: invalid Input"<<endl;
return NULL;
}
root->left = NULL;
root->right = NULL;
root->val = str[0];
stk.push(root);
for(int i = 1; i < length; i++)
{
Node * newNode = new Node();
newNode->left = NULL;
newNode->right = NULL;
newNode->val = str[i];
if(stk.empty())
{
cout<<"Error: invalid Input"<<endl;
return NULL;
}
Node* tmpNode = stk.top();
while(!stk.empty())
{
if (tmpNode->left == NULL)
{
tmpNode->left = newNode;
break;
}
if (tmpNode->right == NULL)
{
tmpNode->right = newNode;
stk.pop();
break;
}
tmpNode = stk.top();
}
if(str[i] == 'P' || str[i] == 'p')
stk.push(newNode);
}
return root;
}
1. Calculate number of Leafs (i.e. L) in preorder say it is nL
2. if nL =1, there is only one node i.e root
3. if nL>1 && nL is even , left and right subtree is of height nL/2
4. if nL>1 && nL is odd, one subtree is of height 1 and other is of height (nL-1)/2 (There are two trees possible in this case)
Once we have height of both subtrees we can construct trees.
One can construct multiple trees if we have to satisfy just pre-order traversal.
Example: Pre-Order Traversal Result: A B D E C F G
A
/ \
B C
/ \ / \
D E F G
A
/ \
B D
/ \
E C
/ \
F G
It is also not clear what other nodes are possible than N & L in a binary tree?
To conclude, question is incomplete or the interviewer is expecting you to prove that question leads to multiple answers :).
Thanks,
Laxmi
By N and L, I mean, node names can be only N or L
{ N
/ \
N L
/ \
L L
}
Pre-Order will be NNLLL
Because for a tree with 0 or 2 children, number of leaf = Number of Non-leaf + 1.
we can separate left and right tree with this fact.
I have the following code
Node *BuildTree(char A[ ], int size)
{
if (size == 1){
if (A[0] == 'L') {
Node *root = new Node(A[0]);
root ->left = NULL;
root->right = NULL;
return root;
}else
return NULL;
}
Node *root = new Node(A[0]);
root ->left = NULL;
root->right = NULL;
int N_count = 0;
int L_count = 0;
int i = 1;
while (L_count <=N_count){
if(A[i] == 'N') N_number ++;
else L_Number ++;
i++;
}
root ->left = BuildTree(A+1, i-1);
root->right = BuildTree(A+i+1, size - i- 1);
return root;
}
Here is the working code link: h t t p://codepad.org/qqd48QUT
Logic:
0) The length of the string (or count of nodes) with given restrictions will always be odd
1) For every 'N' visited, call the create function to populate left sub-tree and right sub-tree.
In more detailed manner:
1) Let us assume CreateTree is a function that takes the input string, string length, parent node reference, and an index into the string about current node
2) When the index surpasses the string length, it means we are expecting more nodes as per restrictions but the input given does not have. Which means, invalid input. Bail out
3) Create a node with current index data
4) If current node data is 'L', no more children for this node. just return success
5) If current node data is 'N', it means we have two children for this node.
5.1) Increment the current node index, call the CreateTree function to populate left sub-tree
5.2) Increment the current node index, call the CreateTree function to populate right sub-tree
6) Set the root at this level to this node and return success
import java.util.Stack;
public class PreOrderConstruction {
public static void main(String[] args) {
char[] preOrderList = new char[]{'N','N','L','L','L'};
Stack<Node> stck = new Stack<Node>();
Node inNode = null;
for(int i=preOrderList.length-1; i>=0; i--){
if(preOrderList[i]=='L'){//If leaf node
stck.push(new Node(preOrderList[i]));
}else{
Node left = stck.pop();
Node right = stck.pop();
inNode = new Node(preOrderList[i]);
inNode.setLeftNode(left);
inNode.setRightNode(right);
stck.push(inNode);
}
}
inNode = stck.pop();
}
}
class Node{
Node left = null;
Node right = null;
char data;
public Node(char data){
this.data = data;
}
public void setLeftNode(Node n){
this.left = n;
}
public void setRightNode(Node n){
this.right = n;
}
}
node* GenerateTree(char *input, int stIndex, int endIndex)
{
if(stIndex > endIndex) return null;
if(input[stIndex] == 'L')
{
node *tempnode =(node*)malloc(sizeof(node));
tempnode->data = 'L'; // I have just put here some data
return tempnode;
}
else if (input[stIndex] == 'N' && stIndex +2 <= endIndex)
{
node *tempnode = (node *)malloc(sizeof(node));
tempnode->data = 'N';
tempnode->left = GenerateTree(input,stIndex + 1, endIndex);
tempnode->right = GenerateTree(input, stIndex+ 2, endIndex);
if(tempnode->left == null || tempnode->right == null)
{
return null;
}
else
{
return tempnode;
}
}
else
{
return null; // Invalid format
}
}
node* GenerateTree(char *input, int stIndex, int endIndex)
{
if(stIndex > endIndex) return null;
if(input[stIndex] == 'L')
{
node *tempnode =(node*)malloc(sizeof(node));
tempnode->data = 'L'; // I have just put here some data
return tempnode;
}
else if (input[stIndex] == 'N' && stIndex +2 <= endIndex)
{
node *tempnode = (node *)malloc(sizeof(node));
tempnode->data = 'N';
tempnode->left = GenerateTree(input,stIndex + 1, endIndex);
tempnode->right = GenerateTree(input, stIndex+ 2, endIndex);
if(tempnode->left == null || tempnode->right == null)
{
return null;
}
else
{
return tempnode;
}
}
else
{
return null; // Invalid format
}
}
int count = 0;
treeNode * createNode(char val){
treeNode * node = malloc(sizeof(treeNode));
node->value = val;
node->lChild = NULL;
node->rChild = NULL;
return node;
}
//treeString is the pre-order representation of tree,i.e.-"NNLLL"
treeNode * makeTree(char * treeString, int *count){
treeNode * temp = NULL;
if(*(treeString + *count) != '\0'){
temp = createNode(*(treeString + *count));
if(*(treeString+ *count) == 'N'){
*count += 1;
temp->lChild = makeTree(treeString,count);
*count += 1;
temp->rChild = makeTree(treeString,count);
}
}
return temp;
}
So, the function is called as:
int main(){
char * treeString = "NNLLNNLLL";
treeNode * root = NULL;
root = makeTree(treeString,&count);
}
#include <iostream>
using namespace std;
string str="NNLLL";
int i = 0;
typedef struct node
{
char val;
struct node *left;
struct node *right;
}*tree;
tree root;
void construct_tree(tree current)
{
if(i < (int)str.length() - 1 && current->val=='N')
{
tree temp_l = new node;
temp_l->left=temp_l->right=NULL;
temp_l->val= str[++i];
current->left = temp_l;
construct_tree(temp_l);
tree temp_r = new node;
temp_r->left=temp_r->right=NULL;
temp_r->val = str[++i];
current->right = temp_r;
construct_tree(temp_r);
}
return;
}
void print(tree current)
{
if(current != NULL)
{
cout<<current->val<<" ";
print(current->left);
print(current->right);
}
}
int main()
{
tree tmp = new node;
tmp->left=tmp->right=NULL;
root = tmp;
if(str.length()-1 > 0)
{
tmp->val = str[0];
construct_tree(tmp);
}
print(root);
return 0;
}
public static Node buildTree(Node[] preorder) {
Stack s = new Stack();
Node lastNode = null;
for(int i=0;i<preorder.length;i++) {
Node node = preorder[i];
if(lastNode == null) {
} else if (lastNode.type.equals("N")) {
s.push(lastNode);
lastNode.left = node;
} else {//node type if L
s.pop().right = node;
}
lastNode = node;
}
return preorder[0];
}
public static Node buildTree(Node[] preorder) {
Stack s = new Stack();
Node lastNode = null;
for(int i=0;i<preorder.length;i++) {
Node node = preorder[i];
if(lastNode == null) {
} else if (lastNode.type.equals("N")) {
s.push(lastNode);
lastNode.left = node;
} else {//node type if L
s.pop().right = node;
}
lastNode = node;
}
return preorder[0];
}
node* create_from_preorder(char *s)
{
static int count=0;
node * temp=(node*)malloc(sizeof(node));
temp->left=NULL;
temp->right=NULL;
printf("enter here");
if(s[count]== '1')
{
printf("got 1\n");
temp->data=1;
count++;
temp->left=create_from_preorder(s);
count++;
temp->right=create_from_preorder(s);
}
else if(s[count]== '0')
{
printf("got 0\n");
temp->data =0;
}
else
{
printf("not a valid input");
return NULL;
}
return temp;
}
node* create_from_preorder(char *s)
{
static int count=0;
node * temp=(node*)malloc(sizeof(node));
temp->left=NULL;
temp->right=NULL;
printf("enter here");
if(s[count]== '1')
{
printf("got 1\n");
temp->data=1;
count++;
temp->left=create_from_preorder(s);
count++;
temp->right=create_from_preorder(s);
}
else if(s[count]== '0')
{
printf("got 0\n");
temp->data =0;
}
else
{
printf("not a valid input");
return NULL;
}
return temp;
}
Pair<TreeNode<Character>, Integer> preorderToTree(char[] a, int index) {
if (index < a.length) {
TreeNode<Character> n = new TreeNode<>();
n.value = a[index];
if (a[index] == 'L') { // leaf
return new Pair<>(n, index+1);
}
else {
n.value = 'N';
Pair<TreeNode<Character>, Integer> lp = preorderToTree(a, index+1);
if (lp != null) {
Pair<TreeNode<Character>, Integer> rp = preorderToTree(a, lp.snd);
n.left = lp.fst;
n.right = rp.fst;
return new Pair<>(n, rp.snd);
}
return new Pair<>(n, index+1);
}
}
return null;
}
@Test
public void testPreorderToTree() {
Pair<TreeNode<Character>, Integer> p = preorderToTree(
"NNLLL".toCharArray(), 0);
System.out.println(p.fst.toString());
}
stuct node *constructTree(char *preorder, int *index)
{
// Return null if the array is empty
if (!preorder || *index == n)
return NULL;
// Create a node from the array at that index
struct node *new = NewNode(preorder[*index];
// If the node is a leaf node, terminate the funtion and return a pointer to that node
if (new->data == ‘L’)
return node;
// Move the index pointer ahead by one cell
*index = *index + 1;
// Construct the node's left pointer
new->left = constructTree(preorder, index);
// Move the index pointer ahead by one cell
*index = *index + 1;
// Construct the node's right pointer
new->right = constructTree(preorder, index);
// Return the current node's pointer to its caller funtion
return node;
}
Time Complexity O(n)
- Ran January 24, 2012int MaxVisitedIndex = 0; TreeNode ConstructNodes(preOrderList, int index) { TreeNode n = new TreeNode(); n.data = preOrderList[index].data; if(MaxVisitedIndex < index) MaxVisitedIndex = index; if(preOrderList[index].NodeType == NodeType.Leaf) { n.Left = null; n.right = null; } else { n.Left = ConstructNodes(preOrderList, index + 1); n.Right = ConstructNodes(preOrderList, MaxVisitedIndex + 1); } return n; }