CareerCup

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.

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

Karthik, Can you tell me solution for this?

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

For example,

+
- *
3 5 7 8

would be stored as

+-35*78

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

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.

Just for clarification...

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

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.

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

Also, the sequence above is preoder, not inorder.

preorder*

How about

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

Jack!!! Can you tell?

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.

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.

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

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.

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

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.

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.

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.

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

to the abov soln by Hui.
i was thinkin the same thing, but
without your index.
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

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

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

More over,
i would make some changes, instead of breadth first search
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.

Can we use "Prufer Codes"?

Can we do it using parenthesis

sth like this, pre-order

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

Can do like this

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

use XML

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

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

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

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

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)
2) Read from the file:
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!

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

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

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))

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

For example,

+
- *
1 2 3 4

would be stored as

+-12*34

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

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

How about this

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.

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

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),)),))
void read_tree(const char * string)
{
	int str_length = strlen(string);
	if(str_length == 0) { return; } // empty tree
	Node * parent_node = create_node(string[0]); // root
	if(string[1] == '(') {
		read_tree_helper(parent_node, string, 2);
	}
}

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);
			}
		}
	}
}

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?

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 addNode(TREE **root, int data);
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);
static char[] answerInorder;
static char[] answerPreorder;

int main() {
TREE *root = NULL;
TREE *reRoot = NULL;
addNode(&root,5);
addNode(&root,6);
addNode(&root,3);
addNode(&root,7);
addNode(&root,2);
addNode(&root,9);
addNode(&root,8);
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[0];
(*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;
}

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.

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.

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[0] };
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; }
}

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.

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.

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.

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