## Amazon Interview Question for Software Engineer / Developers

• 0

Comment hidden because of low score. Click to expand.
2
of 2 vote

An ordered (pre/post/in) works only for a complete binary tree. For the question, perhaps what they want is to store each element (say at i index) in an array and it's child at 2i and 2i+1 position. If it does not have a left/right child, leave the corresponding index empty.

From this array, it is easy to reconstruct any binary tree.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

seems the best one. I have another solution, which is harder to understand, but takes up less space. But I myself prefer your approach.

Comment hidden because of low score. Click to expand.
1
of 1 vote

I believe storing the pre-order and in-order sequence is the optimal solution: it takes roughly 2*n bytes to store, where n is the number of nodes in the tree, and it removes the complication in dealing with unbalanced or incomplete trees. Here's an example:

Say we're given the following sequences (completely arbitrary):

Pre-order: abdecf
In-order: dbeafc

To reconstruct the tree, we'd read these two lines into two arrays. In a recursive function, we examine the first element of the pre-order array, which is obviously the root node of the current tree we're building. We locate its position in the in-order array, in this case, array index 3. As a result, we can divide the in-order array into two parts: the left branch (dbe) and the right branch (fc). Knowing that, we also know the "length" of those two branches, which we can use to extract bde and cf from the pre-order array. To finish it off, we set the left branch to be the result of calling the function recursively on pre-order bde, in-order dbe and the right branch to be the result of calling the function recursively on pre-order cf, in-order fc.

Try it out -- it works. :D

Comment hidden because of low score. Click to expand.
0

Here's the actual code for the method I described above -- short and simple:

public TreeNode makeTree (List preorder, List inorder) {
// the first Object in preorder will be the root
if (preorder.isEmpty())
return null;
int rootIndex = inorder.indexOf(preorder.get(0));
if (rootIndex == 0 && inorder.isEmpty())
return new TreeNode(inorder.get(0));
else {
return new TreeNode(inorder.get(rootIndex),
makeTree(preorder.subList(1, rootIndex+1),
inorder.subList(0, rootIndex)),
makeTree(preorder.subList(rootIndex+1, preorder.size()),
inorder.subList(rootIndex+1, inorder.size())));
}
}

Comment hidden because of low score. Click to expand.
0

Is there a way we can indent the code in career cup ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Karthik, Can you tell me solution for this?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Do an inorder traversal and write as you read...

For example,

+
- *
3 5 7 8

would be stored as

+-35*78

Comment hidden because of low score. Click to expand.
0

To make this work for unbalanced/incomplete trees, NULL must be a allowed value.

+
- 7
3 +
5

+-3NN+5NNN7NN

or use parenthesis
+(-(3,+(5,)),7)

Comment hidden because of low score. Click to expand.
0

@Jack
If its an in order traversal shouldn't it follow the order left child,root and then right child.According to the traversal is the above order +-35*78 correct? Please clarify

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0
of 0 vote

inorder? How it is going to work for nodes with number alone?

Comment hidden because of low score. Click to expand.
0
of 0 vote

If the node's data is an object, I would use a hashing function. If the node contains data of a primitive type, then use ascii characters since an ascii is 1 byte.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Just for clarification...

By node's data as an object, I mean if the data type is abstract.

Comment hidden because of low score. Click to expand.
0
of 0 vote

When the data type is abstract, using a hashing function allows you to store a hash table into the file where the hash maps to a value. This way, the value is stored once if it has duplicates.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Also, if the integer is within range for ascii, then store characters. If not, then store data based on precision.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Also, the sequence above is preoder, not inorder.

Comment hidden because of low score. Click to expand.
0
of 0 vote

preorder*

Comment hidden because of low score. Click to expand.
0
of 0 vote

NOTE: Binary tree. not BST.
7
/ 5 14
/
10
/ 1 2

Jack!!! Can you tell?

Comment hidden because of low score. Click to expand.
0
of 0 vote

What I did was:

Do a preorder traversal.

Take string along with you, and as you go left add a 1 to it and right add a 0 to it. Then at each node you'll have node and associated string, write it to file.

Then you can read this file back in and know where the nodes go and since we are doing preorder traversal, you can be sure the parent will come before the child when reading in the file .

Recruiter said this is the first time he saw this answer in two days of interviewing... so wondering if there was something better, but i can't see one.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I was assuming the BT is complete. If the BT isn't complete, then preorder without metadata will fail. It would have been good to clarify this w/ the interviewer. I would also ask the interviewer what type of data the binary tree is used for, since certain optimizations are possible?

In that case, I would try writing name/value pairs by using a preorder traversal and converting primitive types into strings.

For example...

*
- +
72 33 48
5 91

Contents of property file:
*: - +
-: 72
72: 5
+: 33 48
48: 91

Writing out ascii chars becomes inefficient for integers but makes it easier to debug your code. If storage space is not a concern, this may suffice. Nevertheless, you can optimize a string of decimal digits by using hex digits.

Comment hidden because of low score. Click to expand.
0

this still has an issue:
consider the following two versions of the trees:
Tree 1 | Tree 2
------- | ------
* | *
- + | - +
72 33 48 | 72 33 48
5 91 | 5 91

So, as you can see, Node with 72 and 48 can have their children in a different manner, but on the file they will be written similiarly. So u cant really differentiate in the ordering. Therefore I would suggest that one should use a delimiter to write the two children of each node. something like this:

Parent : LC ; RC
------ -- --
* : - ; +
- : 72 ; <Blank>
72 : 5 ; <Blank>
+ : 33 ; 48
48 : ; 91

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hmm, so jack are you saying my answer was wrong then, if it was not nec. a complete tree?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Kartik,

No, it seems logically correct. You have metadata for each node using 0,1. I meant to say that a raw preorder traversal would be ambiguous when read back. Curiously, how would you separate the metadata from the data in your implementation? For instance, how would you read back a string such as 430113243? Let me know if I misunderstood your algorithm.

Comment hidden because of low score. Click to expand.
0
of 0 vote

My traversal above isn't preorder. It's actually breadth-first on 2 queues.

Comment hidden because of low score. Click to expand.
0

what we need is the less-commonly known level-order traversal.

Comment hidden because of low score. Click to expand.
0
of 0 vote

So jack, you are right in interpreting my implementation.

At the end of the store (data" "path) you would have a file something like so:

A NULL
B 0
C 01
D 1
E 11

So you read the file back line by line and you parse it into two fields, content of node (I should probably note that the interviewer said there were only chars as data in this tree) and then a 0's and 1's string which says where the node is located. Then you automatically set the first node to root. Then go though each string with the corresponding data and rebuild the tree. So it's O(n) rebuilding time as you have the nodes in traversed order so you garuntee not hitting something twice.

Comment hidden because of low score. Click to expand.
0
of 0 vote

So jack, you are right in interpreting my implementation.

At the end of the store (data" "path) you would have a file something like so:

A NULL
B 0
C 01
D 1
E 11

So you read the file back line by line and you parse it into two fields, content of node (I should probably note that the interviewer said there were only chars as data in this tree) and then a 0's and 1's string which says where the node is located. Then you automatically set the first node to root. Then go though each string with the corresponding data and rebuild the tree. So it's O(n) rebuilding time as you have the nodes in traversed order so you garuntee not hitting something twice.

Comment hidden because of low score. Click to expand.
0
of 0 vote

So jack, you are right in interpreting my implementation.

At the end of the store (data" "path) you would have a file something like so:

A NULL
B 0
C 01
D 1
E 11

So you read the file back line by line and you parse it into two fields, content of node (I should probably note that the interviewer said there were only chars as data in this tree) and then a 0's and 1's string which says where the node is located. Then you automatically set the first node to root. Then go though each string with the corresponding data and rebuild the tree. So it's O(n) rebuilding time as you have the nodes in traversed order so you garuntee not hitting something twice.

Comment hidden because of low score. Click to expand.
0
of 0 vote

1) BFS and write nodes on different levels to different lines of the file
2) Marking with index which parent they belong to

Comment hidden because of low score. Click to expand.
0
of 0 vote

to the abov soln by Hui.
i was thinkin the same thing, but
since it is a binary tree, it is almost gauranteed that reading 2-elements would lead you to 1 parent.
however, i would at this point ask the interviewer(s) whether a single child would always reside to its parent's left side(left child).
also i would also ask whether i am allowed to write on different lines

Comment hidden because of low score. Click to expand.
0
of 0 vote

HotDog, there is no gurantee that it is a FULL binary tree, so I think writing Index is un-avoidable. How do u think?

Comment hidden because of low score. Click to expand.
0
of 0 vote

i am just wondering,
could we ignore the fact that it is a full bt or not a full bt?
because i am thinkin that we could look at the patterns.

we are only reading each line as each level.
we are only reading each elem in each line as a child

ex.

a tree:
[a][ b, c ] //root level
[b][ d, ] //next level
[c][ , g ] //same level as b

I believe we need to define the bound of an obj.
but the basic idea is reading as it comes and
a space represents a null child.
(*and hui, you are right, we need to identify null child.)

let's say we use | to define the bound of an obj(delimiter)
|a|
|b||c|
|d|| || |e|
else, i guess we would use a special byte value

this only happens if the interviewer(s) allow(s) us to output each level as a new line.

if we are only allowed to use 1 single string line
i guess i would use 2 bits for identifiers
10 - left
01 - right
11 - next level

but i believe the way i answer this question is too naive.

wut do you guys think?

With LamboMumbleHumbleDumbo,
HotDogMumboJumboKudo

Comment hidden because of low score. Click to expand.
0
of 0 vote

More over,
i would use preOrder (root,left,right)
appened to the end of the file as we go.
again, we only need to find a good delimiter to seperate a left child and a right child and a delimiter for null child(and maybe a delimiter for next level, this won't b necessary, we only need to keep countin as we buildin the level, 2^h is the max # nodes u could hv)

or creatively
you could build a relation table between each child and its parent.
and recursively iterate thru and built the tree.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we use "Prufer Codes"?

Comment hidden because of low score. Click to expand.
0

For Prufer codes to be used, the nodes need to be labelled uniquely and as integers. So Prufer codes wont work for many cases

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we do it using parenthesis

sth like this, pre-order

5(3(7,8),6(9,2)))

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can do like this

store node->data, direction, level
Preorder(node->left,0,level++);
Preorder(node->right,1, level++);

Comment hidden because of low score. Click to expand.
0
of 0 vote

use XML

Comment hidden because of low score. Click to expand.
0

wont work if you need to differentiate if a single leaf node is a left child or right child !

Comment hidden because of low score. Click to expand.
0

why not - you could use <left>val</left> or <node branch="left">val</node>

Comment hidden because of low score. Click to expand.
0
of 0 vote

Let the tree be
a
b c
d e f
Do a inorder traversal with a little modification.Modification is to add 0 for empty nodes.

function String inorder(struct node* root,String vOutput) {
if(root == null)
return(vOutput +'0');

if (root->left == null && root->right ==null)
return (vOutput + root->data);

inorder(root->left,vOutput);
return(vOutput + root->data);
inorder(root->right,vOutput);

}

So the output of the program is going to be 'db0aecf'

Find the middle of the array.Elemant is the root.The left array is the left subtree and
right array is the right sub tree.

Using the middle element discussed above recursively print the elements

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think most of you are in the right track.. my solution is inspired by all the above ideas, but in my opinion, simple, and slightly better..

I agree preorder is the best since it adds parents before children. So we output numbers as we go in preorder but everytime we go "up", we insert U (or some other character), and everytime we skip left child, we insert R.. since up characters are same as the number of parents, and right characters as much as nodes, we shall have 3n characters storage in the worst case. And while re-creating the tree, we shall be actually instructing the algorithm how to go, so the next character read will always be the one added..

suppose tree is:
a
b c
d e - f
g - h i j -

Output: abdgUUehUiUUUcRfj

Since this may involve a number of U just to get to the next available spot, we can probably just put one, denoting go to next place a node can be inserted after this node.

I know, it gets complicated, but you'll get an unambiguous, small, and fast storage format

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi Ann, Your solution will work only for your case, try it working for the case where the root has no right tree or even a tree with greater number of levels with few nodes missing

Comment hidden because of low score. Click to expand.
0
of 0 vote

write inorder and preorder/postorder
these two order traversals uniquely represent the tree.

Comment hidden because of low score. Click to expand.
0
of 0 vote

It is clear by now that some of the above solutions do not work when we have left or right child missing! Testing things with this simple tree will fail many of the above solutions!

1
/ \
2
/ \
3

While reconstruction, there is an ambiguity to be resolved - Where to place 3?

My Algorithm:
------------

1) Traverse it a BFS way:
12).3)
1 Read the first symbol, Create a node for the same.
2 If symbol is null, then it is a null tree else proceed to step 3.
3 Read the next symbol from file. Set Local Var L = true;
4 If symbol is '.', then left child is null, so do not enqueue anything.
Set L = false;
5 Until Symbol is ')', do steps 6-8.
6 Retrieve the symbol, create a node and enqueue it.
7 If L is false, Queue Structure will have Direction set to 'R' else 'L'.
8 Also store the CurrentNode Value as the parent value in Queue structure.
9 L = true; Go to 5
10 Dequeue the element.
11 Search the parent value uptil now from the created tree!
12 If Direction = 'L' set the searched node left pointer to current node.
13 If Direction = 'R' set the searched node right pointer to current node.
14 Set CurrentNode = Dequeued element.

I know searching tree everytime is O(logN). Hence, algorithm deserves some good improvement tips!

Comment hidden because of low score. Click to expand.
0
of 0 vote

With inorder and preorder sequence or in-order and post-order sequence the binary tree can be reconstructed perfectly.

Comment hidden because of low score. Click to expand.
0
of 0 vote

do inorder traversal and do preorder traversal write both into the file. using these two only we can rebuild the tree.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Think from a compiler aspect.
When you parse an expression, the BNF grammar for an expression is:
Expression:= Expression OP Expression

in real code, it's like:
(Expression)OP(Expression)

then we get more expression:
((Expression)OP(Expression))OP(Epxression)

Each time we see '(', we create a new node.

Using the same idea, we don't need to use the queue or BFS.

e.g.

``````a
b  c
d    e f``````

can be represented as:

a(b(d,),c(e,f))

Comment hidden because of low score. Click to expand.
0
of 0 vote

Do an inorder traversal and write as you read...

For example,

+
- *
1 2 3 4

would be stored as

+-12*34

Comment hidden because of low score. Click to expand.
0
of 0 vote

How about just doing a preorder traversal, but also write out the NULL pointer. It should perfectly reconstruct the tree.

Comment hidden because of low score. Click to expand.
0
of 0 vote

why did the array idea get dismissed easily ?
Thought with a modified BFS it should work pretty well
Array Tree[NUMVertices]

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. label every node, level by level, with numbers

1
/ \
2 3
/ /
4 5
\
6

2. for every, record the left child, right child. O(n) space:

2 4 5 N N N
3 N N N 6 N

1 2 3 4 5 6

Then you can reconstruct the tree. I'm just simulating how the real binary tree works.

Comment hidden because of low score. Click to expand.
0
of 0 vote

define
tree:= <branch> | <leaf>
branch:= 1, node_value, <tree_left>, <tree_right>
leaf:= 0, leaf_value

As observed earlier in the posts, NULL should be allowed as leaf value

Comment hidden because of low score. Click to expand.
0
of 0 vote

Using parentheses:
A(B(D,E),C(F(,G(H(K,L),)),))

For small trees which nodes can be presented as ansichar (1byte) (below), for bigger trees should use hashmap for nodes and extend string reading algorithm

1.

``````typedef struct node Node;

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

typedef struct tree Tree;

struct tree {
Node * root;
}``````

2.

``````void print_tree(Node * node)
{
printf(node->data);
if(node->left || node->right) {
printf("(");
if(node->left) {
print_tree(node->left);
}
printf(",");
if(node->right) {
print_tree(node->right);
}
printf(")");
}
}

// print to file
print_tree(tree->root); // A(B(D,E),C(F(,G(H(K,L),)),))``````

3.

``````// A(B(D,E),C(F(,G(H(K,L),)),))
{
int str_length = strlen(string);
if(str_length == 0) { return; } // empty tree
Node * parent_node = create_node(string); // root
if(string == '(') {
}
}

void read_tree_helper(Node * parent_node, const char * string, unsigned int index, int str_length)
{
if(index >= str_length) { return; }

if(string[index] != ',') {
parent_node->left = create_node(string[index + 1]);
if((string[index + 2] == ',') && (string[index + 3] != ')')) {
parent_node->right = create_node(string[index + 3]);
if(string[index + 4] == '(') {
read_tree_helper(parent_node->right, string, index + 5, str_length);
}
} else {
if(string[index + 2] == '(') {
read_tree_helper(parent_node->left, string, index + 3, str_length);
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0

The above read_tree_helper breaks after we traverse upto A(B(D,E)

Comment hidden because of low score. Click to expand.
0
of 0 vote

I was thinking of a solution mixing a file storing the tree details and an xml structure storing node record details.

stuct node
{
int d1; int d2; String d3;
node* left; node*right;
}
For Tree each with data node....

1
2 3
4 NULL NULL 5

Create a treeStuct.txt file as

1
2,3
4,-1,-1,6

and an XML as

<node id = 1>
<d1>10</d1>
<d2>4</d2>
<d3>Node1StringData</d3>
</node>
<node id = 2>
<d1>10</d1>
<d2>4</d2>
<d3>Node2StringData</d3>
</node>
<node id = 3>
<d1>10</d1>
<d2>4</d2>
<d3>Node3StringData</d3>
</node>

This works and can be reused by changing XML schema to support differnt node types...

Does this work?

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Save inorder and preorder of a tree.
2. Reconstruct it using:
a. Navigate through each character of preorder array
a.1. Check the preorder character with each node of newly tree that is
getting constructed.
a.1.1. If current preorder character comes before current node
character in inorder array, node = node -> left
a.1.2. If current preorder character comes after current node
character in inorder array, node = node -> right
a.1.3. Continue until you get null. If null, attach the new
preorder character to the left/right depending on where
reached.

Here is the source code:
# include <stdio.h>
# include <stdlib.h>

typedef enum location {LEFT=-1, CENTRE=0, RIGHT=1} relPos;
typedef enum boolean {TRUE=1,FALSE=0} boolVar;

typedef struct tree {
int data;
char reData;
struct tree *left;
struct tree *right;
} TREE;

void printInOrder(TREE *root,boolVar printInt);
void printPreOrder(TREE *root,boolVar printInt);
void printPostOrder(TREE *root,boolVar printInt);
void constructTree(TREE **root,char *inorder, char*preorder);
relPos myNavigator(char *inorder,char rootNode, char currentNode);

int main() {
TREE *root = NULL;
TREE *reRoot = NULL;
printf("\nIn-order : ");
printInOrder(root,TRUE);
printf("\nPre-order : ");
printPreOrder(root,TRUE);
printf("\nPost-order : ");
printPostOrder(root,TRUE);
char inorder[] = "2356789";
char preorder[] = "5326798";
constructTree(&reRoot,inorder,preorder);
printf("\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
printf("\nIn-order : ");
printInOrder(reRoot,FALSE);
printf("\nPre-order : ");
printPreOrder(reRoot,FALSE);
printf("\nPost-order : ");
printPostOrder(reRoot,FALSE);
getch();
return 1;

}

void addNode(TREE **parentNode, int data) {
TREE *newNode = NULL;
newNode = malloc(sizeof(TREE));
newNode -> data = data;
newNode -> left = NULL;
newNode -> right = NULL;
if(*parentNode == NULL) {
*parentNode = newNode;
return;
}
TREE *node = *parentNode;
TREE **leftN = NULL;
TREE **rightN = NULL;
while(node) {
leftN = &(node -> left);
rightN = &(node -> right);
if(node -> data > data) {
if(*leftN)
node = *leftN;
else {
*leftN = newNode;
break;
}
} else {
if(*rightN)
node = *rightN;
else {
*rightN = newNode;
break;
}
}
}
}

void printInOrder(TREE *node,boolVar printInt) {
if(!node)
return;
printInOrder(node -> left,printInt);
if(printInt)
printf("%d ",node -> data);
else
printf("%c ",node -> reData);
printInOrder(node -> right,printInt);
}

void printPreOrder(TREE *node,boolVar printInt) {
if(!node)
return;
if(printInt)
printf("%d ",node -> data);
else
printf("%c ",node -> reData);
printPreOrder(node -> left,printInt);
printPreOrder(node -> right,printInt);
}

void printPostOrder(TREE *node,boolVar printInt) {
if(!node)
return;
printPostOrder(node -> left,printInt);
printPostOrder(node -> right,printInt);
if(printInt)
printf("%d ",node -> data);
else
printf("%c ",node -> reData);
}

void constructTree(TREE **reRoot, char *inorder, char*preorder) {
TREE *newNode,*tempNode,**childNode = NULL;
*reRoot = (TREE *)malloc(sizeof(TREE));
(*reRoot) -> reData = preorder;
(*reRoot) -> left = NULL;
(*reRoot) -> right = NULL;
int index = 0;
for(index = 1;preorder[index] != '\0';index++) {
newNode = (TREE *)malloc(sizeof(TREE));
newNode -> reData = preorder[index];
newNode -> left = NULL;
newNode -> right = NULL;
tempNode = *reRoot;
while(1) {
if(myNavigator(inorder,tempNode -> reData,preorder[index]) == LEFT) {
childNode = &(tempNode -> left);
if(*childNode == NULL) {
*childNode = newNode;
break;
}
}
else {
childNode = &(tempNode -> right);
if(*childNode == NULL) {
*childNode = newNode;
break;
}
}
tempNode = *childNode;
}
}
}

relPos myNavigator(char *inorder,char rootNode, char currentNode) {
int index = 0;
for(index = 0;inorder[index] != '\0';index++) {
if(inorder[index] == rootNode)
return RIGHT;
if(inorder[index] == currentNode)
return LEFT;
}
return CENTRE;
}

Comment hidden because of low score. Click to expand.
0

The www.careercup.com is interesting resource, tnks, webmaster. But look at this <a href= http://carolinecs.150m.com/state_water_heater_censible.html > state water heater censible </a>

Comment hidden because of low score. Click to expand.
0

The www.careercup.com is cool site, good job, admin. And see this <a href= http://howdoqj6.netfirms.com/buy_liquor_online.html > buy liquor online </a>

Comment hidden because of low score. Click to expand.
0

The www.careercup.com is excellent site, thanks, webmaster.
<a href= http://board.spawn.com/forums/member.php?u=59753 > Buy viagra </a> <a href= http://stardustathome.ssl.berkeley.edu/forum/profile.php?mode=viewprofile&u=4014 > Buy Cialis </a> <a href= http://www.tetongravity.com/forums/member.php?u=19806 > Buy Levitra </a>

Comment hidden because of low score. Click to expand.
0
of 0 vote

if file size is not an issue, then why not just use object serialization. for example jave object serialization. Obviously this doesn't scale for very large trees but it is one way to persist the tree.

Comment hidden because of low score. Click to expand.
0
of 0 vote

clearly, if the tree is full tree, then we can serialization easily, just like heap structure. So, we can try to make the tree "virtual full". That is, all leaves of the tree has exactly two children, if there is only one node, add a virtual nodes on the leaf. Then, write the value of the node or \0(virtual node) into file level by level. When read data from file, contruct the binary tree level by level.

Comment hidden because of low score. Click to expand.
0

just store INOREDER traversal along with its PREORDRER traversal!
with these two u can reconstruct the tree

Comment hidden because of low score. Click to expand.
0
of 0 vote

A C# solution with pre-order and in-order traversals to rebuild the tree:

class RebuildBinaryTree
{
static void Main(string[] args)
{
List<int> preOrder = new List<int>() { 1, 2, 3, 4, 5, 6, 7 };
List<int> inOrder = new List<int>() { 3, 2, 4, 1, 6, 5, 7 };
Node node = BuildTree(preOrder, inOrder);

preOrder = new List<int>() { 1,2,3,8,9,10,11,12,4,13,14,5,6,15,16,7,17,18,19 };
inOrder = new List<int>() { 8,9,3,11,10,12,2,4,13,14,1,16,15,6,5,17,7,19,18 };
node = BuildTree(preOrder, inOrder);
}

public static Node BuildTree(List<int> preOrder, List<int> inOrder)
{
if (preOrder == null || preOrder.Count == 0)
{
return null;
}

Node node = new Node() { Data = preOrder };
int index = inOrder.FindIndex(a => a == node.Data);
node.Left = BuildTree(preOrder.GetRange(1, index), inOrder.GetRange(0, index));
node.Right = BuildTree(preOrder.GetRange(index + 1, preOrder.Count - index - 1), inOrder.GetRange(index + 1, inOrder.Count - index - 1));

return node;
}
}

public class Node
{
public int Data { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. calculate PreOrder and InOrder
PreOrder: 1234567
InOrder: 2431675
first element is root node so root node is 1. now find the root node in InOrder and break the string.
InOrder 243 - 675 ( 3 - 3 size)
PreOrder 234 - 567 ( divide the same )
now consider left part it means this is going to left child under root node. consider first element of 234 which is 2 and find the same node in Inorder and divide again so now
InOrder: 43
PreOrder 34 ( as of now you determine 1-(root) 2 ( left )
again perfrom the same and you will able to reconstruct the tree.

Comment hidden because of low score. Click to expand.
0
of 0 vote

use an array. parent is at position 2i and left child is at 2i-1 and right child at 2i+1. If the left/right child doesn't exist, then assign the array slot a number that will not appear in the tree.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Why not use JSON or XML or any sort of standard serialization?

And if that's not an option, you can do a simple encoding like each node encoded as: [content]{[child1],[child2]}, with special caution taken to properly escape characters. No need to get clever with traversals, algorithms, etc. It's O(n) runtime, O(log(n)) space, and is far more practical. Throw a round of compression on top if you're worried about file size.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

With a pre-order and an In-Order sequence, can easily rebuild the tree.

Comment hidden because of low score. Click to expand.
0

Can you please tell how to create the tree.

By using inorder and preorder tree traversal can be re-created. I was trying to write a recursive as well as non recursive algorithm for it but I am stuck on it.

The prototype is

btreenode* create_binary_tree(char *inorder, char *preorder, int length)

where length is the length of the string when contents of binary tree are written in sequential fashion.

btreenode is as follows

typedef struct btreenode{
struct btreenore *left;
char data;
struct btreenode *right;
}

Can you help me with the solution. I know that this can be done using divide and conquer by assigning the first element of the preorder to be root. then looking for root node content in inorder string. All elements left of root are in the left sub tree and all elements after root are in right subtree. You then recursively go on to build the tree. But unforutnately I was unable to get a working solution for it.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.