Ref :- "Serialize and De-serialize a Binary Tree" (http://www.geeksforgeeks.org/
Given solution :- The solution given for "How to store a general Binary Tree?" is to store BOTH Inorder and Preorder traversals.
This approach is
1) time consumming :- as you have to do two traversal
2) Space consuming :- as this solution requires space twice the size of Binary Tree. (As mentioned in article)
My approach :- I have better approach which requires only 1 traversal and memory only equal to tree
A tree can be specified as an array of Tree node objects. And another array that will represent the parent child relation.
e.g.
Thus we need to store all nodes in in-order traversal and an additional string that gives mapping. e.g. in above case 1,4,3,1,-1,6,4,6,7
We can build this string while we are doing in-order traversal. Thus NO second traversal
De-Serialization is also very easy. We just need to de-serialize nodes in same sequence. And then based on the mapping string just adjust the pointers.
Java Code :- Only serialization part
package treerelated;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
public class TreeNode {
public int value;
public TreeNode left,right;
public TreeNode(int value) {
super();
this.value = value;
}
public int findFullNodes(){
int total = 0;
if(left!=null)
total += left.findFullNodes();
if(right !=null)
total += left.findFullNodes();
if(left!=null && right !=null)
total +=1;
return total;
}
@Override
public String toString() {
return ""+value;
}
public static ArrayList<TreeNode> nodeList;
public static Map<Integer,Integer> parentChildRelationMap;
public static int currCount ;
public static void inOrderTraversal(TreeNode root){
nodeList = new ArrayList<TreeNode>();
parentChildRelationMap = new HashMap<Integer, Integer>();
currCount = -1;
inOrderTraversal_internal(root);
System.out.println("Printing Array");
for(int i=0;i<nodeList.size();i++){
System.out.print(nodeList.get(i)+" ");
}
System.out.println("\nparentChildRelationMap=");
for(Integer i :parentChildRelationMap.keySet()){
System.out.println(i +" has parent "+parentChildRelationMap.get(i));
}
}
public static int inOrderTraversal_internal(TreeNode root){
if(root==null) return currCount;
else {
int countBefore = currCount;
int returnedCount = inOrderTraversal_internal(root.left);
System.out.println(root.value);
nodeList.add(root);
currCount++;
if(countBefore!=returnedCount){
// It means some child nodes were added
// Child node was added on returnedCount and parent is added on currCount
parentChildRelationMap.put(returnedCount,currCount);
}
countBefore = currCount; // So countBefore-1 represents the position of parent node of rightside tree
returnedCount= inOrderTraversal_internal(root.right);
if(countBefore!=returnedCount){
// It means some child nodes were added
// Child node was added on returnedCount and parent is added on countBefore-1
parentChildRelationMap.put(returnedCount,countBefore);
}
// return countBefore-1 to indicate where this node was added
return countBefore;
}
}
}
package treerelated;
public class TreeOperations {
public static void main(String[] args) {
TreeNode t1 = new TreeNode(10);
t1.left = new TreeNode(20);
t1.right = new TreeNode(30);
t1.left.left = new TreeNode(40);
t1.left.right = new TreeNode(50);
t1.right.left = new TreeNode(60);
t1.right.right = new TreeNode(70);
t1.left.right.left = new TreeNode(80);
t1.right.right.right = new TreeNode(90);
TreeNode.inOrderTraversal(t1);
}
}
Output :-
40
20
80
50
10
60
30
70
90
Printing Array
40 20 80 50 10 60 30 70 90
parentChildRelationMap=
0 has parent 1
1 has parent 4
2 has parent 3
3 has parent 1
5 has parent 6
6 has parent 4
7 has parent 6
8 has parent 7
