CareerCup

We could change the unbalanced tree to balanced by adding some special node. then convert it to array is easy. Also we could convert the array back to a balanced tree. Finally delete these special node in order to create the initial unbalanced tree.

Traverse that tree in in-order and pre-order. you will have two arrays one for in-order traversal and one for pre-order traversal. You can recreate the same tree again from these two arrays. You can also have post-order instead of pre-order. But in-order it must. you cannot recreate from pre-order and post-order traversal.

level order traversal with spcl node at the beginning of each level

For the unbalanced tree, you can't reconstruct the tree from it's inorder, preorder, post order, or level order traversals, because these traversals alone don't have enough information for you to figure out the shape of the tree.There are two methods you can use to reconstruct a tree from its serialized array.

Method 1
Use inorder+preorder lists or inorder+postorder lists. By using inorder along with postorder or preorder traversals will help you to build the tree, because postorder and preorder will tell you the root node and using the root on inorder will tell you the left and right subtrees. If you observe these lists closely you'll see a recursive pattern.

Method 2
Use the preorder or postorder traversals and save null values as keys when you visit a null left or right node. Null nodes will work as a markers to help you reconstruct the tree in the right form. Again postorder's last node is the root, and preorder's first node is he root node; you can go from the leaf nodes and up and reconstruct the tree.

// o -> array
// n -> node
// i -> index
void prepare_reconstruction_array(int *o, node *n, int i)
{
if(!n) return;
o[i] = n->v;
n->l? reconstruct(o, n->l, 2*i+1) : void(0);
n->r? reconstruct(o, n->r, 2*i+2) : void(0);
}

// o -> array
// n -> node
// i -> index
void prepare_reconstruction_array(int *o, node *n, int i)
{
if(!n) return;
o[i] = n->v;
n->l? prepare_reconstruction_array(o, n->l, 2*i+1) : void(0);
n->r? prepare_reconstruction_array(o, n->r, 2*i+2) : void(0);
}


int main()
{
int output[MAX];
for (int i = 0; i< MAX; i++) {
output[i] = -1;
}

prepare_reconstruction_array(o, root, 0);
}

Actual question behind this question is do you know how to serialize and de serialize a binary tree.

There are several mechanism available for the same. Do any traversal(pre\in\post) and represent a null child with a special delimiter(a bit or any special character). Do the reverse to de serialize the tree taken care of delimiter.

1) remove all leaves from binary and put in an arrary one by one till all nodes are removed.
2) add node from reverse of arrary will create a binary tree in same faishion.

Why won't a breadth first traversal work here? Just add the numbers into the array from left to right starting from the root of the tree. When you got to recreate it just add the numbers into a binary tree from starting from the beginning of your array.

Store Binary tree's inorder and preorder traversal in a "single" array of say 2n or 2n+1 elements. work on starting n indices as inorder array and ending n indices as preorder array.

We have 2n elements but array is only one. :) Did i miss something please do tell.

follow the idea of "level order traversal with spcl node at the beginning of each level"

We have "a#bc#" for, where '#' stands for the end of a level
a
a->left = b
a->right= c

We have "a#$c#" for, where '$' stands for missing a child
a
a->left = NULL
a->right= c
We have "a#&#" for where '& stands for missing both children'
a
a->left = NULL
a->right= NULL

Perform a BFS from the root to output the string.

Following the rule should be able to reconstruct the same tree.

The idea is to treat the binary tree as fully complete binary tree with null at absent nodes
find the depth of binary tree
create an array of size(2^d - 1)
initialize the array with -1 or INT_MIN, or boost::optional<T>::none
now data at index i represent a node at level log2(i) at position i - 2^log2(i)

The idea is to treat the binary tree as fully complete binary tree with null at absent nodes
find the depth of binary tree
create an array of size(2^d - 1)
initialize the array with -1 or INT_MIN, or boost::optional<T>::none
now data at index i represent a node at level log2(i) at position i - 2^log2(i)

From the requirement clearly we need

- A forward conversion function to map from a tree to an array
- A backward conversion function to map from the array to original tree

The forward conversion will be the result of one of the traversal: pre/in/post order
While it is possible to use a single array (the pre-order) to reconstruct the input tree, the requirement is that the tree is a binary tree without duplicated value.

In general the binary tree can be constructed using two arrays in-order in combination with pre/post order, we can not combine these 2 arrays to a single array as there is no linear mapping between 2 arrays that allowed an common indicies to combine 2 arrays.

My solution is to create a single array of the structure

struct Node {
	int value;
	bool isLeaf;
};

with isLeaf indicates if a node is a leaf node. We use pre-order traversal to create
the array, the reason is that pre-order traversal will create the parent node before the children. The isLeaft field indicate a leaf node or the point the tree stop growing and we need to come back to build from other branch.