CareerCup

I can give idea to solve this problem
store the in-oder and post-order traversal output of binary tree in file
now with these two out we can reconstruct the same tree.

I can give idea to solve this problem
store the in-oder and post-order traversal output of binary tree in file
now with these two output we can reconstruct the same tree.

use adjacency list of nodes in the tree
list size is n, number of nodes in tree

Storing inorder and postorder will destroy the structure of tree.

There was once problem asked in code jam 2009 on decision trees.
In that problem one decision tree was presented to user in form of file .
I think that would be better way to write a binary tree in file.

supppose tree is

2
1 3

And second tree is
1
2
3

having same preorder traversal.
So how you are going to reconstruct the tree.

we should save pointer to disk otherwise there is noway to solve problems sethuraj asked

You can represent the tree as a(b(c,d),d(e,f)). This can be achieved by doing a Euler Tour.

To construct back, Just use a stack. Continue Pushing values (a,b,...) and popping back when you get a ')'

pre-order and in-order will allow to construct the binary tree with the same structure

in-order + preorder
or
in-order + postorder

How about?
1. Write BFS preorder, write the parent's offset to each node's section and the fact that it's left/right child. This can be done quite easily with recursion. This has to be done to preserve the tree structure.

2. When reading, read each node in order, construct the node, stick it into a hashtable (key=offset, value=pointer of node).

3. When reading a child node, look up the hashtable with the parent's offset, get the node * of the parent, construct and node, and relink it with the parent.