CODEWITHSUNDEEP
javaalgorithmserializationbinary-treetree-traversal
Spindoctor
Spindoctor

Reputation: 471

Handling duplicates when constructing binary trees

I came across the following question in leetcode - https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

I was able to write an algorithm below (find the preorder and post order traversals and save them. Then reconstruct the tree from the traversals) but have reached a more fundamental issue - ie., How does one construct a binary tree with duplicate values. The test case I am failing on is [3,2,4,3] in which the pre-order and post-order are the same.

Any help and advice is appreciated.

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return null;
        ArrayList<Integer> inorder = inOrder(root, new ArrayList<Integer>());
        ArrayList<Integer> preorder = preOrder(root, new ArrayList<Integer>());
        StringBuilder sb = new StringBuilder("");
        for(int val : inorder){
            sb.append(val + " ");
        }
        sb.append("|");
        for(int val : preorder){
            sb.append(val + " ");
        }
        String serialized = sb.toString();
        return serialized;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null)return null;
        String[]result = data.split("\\|");
        String[] inString = result[0].split(" ");
        String[] preString = result[1].split(" ");
        int i = 0;
        int[] inorder = new int[inString.length];
        int[] preorder = new int[preString.length];
        for(i = 0; i < inString.length; i++){
            inorder[i]= Integer.parseInt(inString[i]);
        }
        for(i = 0; i < preString.length; i++){
            preorder[i]= Integer.parseInt(preString[i]);
        }
        return buildTree(preorder, inorder);
    }
    /*
    Inorder Tree Traversal
    */
    private ArrayList<Integer> inOrder(TreeNode root, ArrayList<Integer> inorder){
        if(root == null ){
            return inorder;
        }
        inorder = inOrder(root.left, inorder);
        inorder.add(root.val);
        inorder = inOrder(root.right, inorder);
        
        return inorder;
    }
    /*
    Pre-order Tree Traversal
    */
    private ArrayList<Integer> preOrder(TreeNode root, ArrayList<Integer> preorder){
        if(root == null ){
            return preorder;
        }
        preorder.add(root.val);
        preorder = preOrder(root.left, preorder);
        preorder = preOrder(root.right, preorder);
        
        return preorder;
    }
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeHelper(inorder, 0, inorder.length - 1, preorder, 0, preorder.length-1);
    }
    public TreeNode buildTreeHelper(int[] in, int ins, int ine, int[] pre, int pres, int pree){
        if(pree < pres || ine < ins) return null;
        
        TreeNode root = new TreeNode(pre[pres]);
        int index = 0;
        for(int i = ins; i <= ine; i++){
            if(in[i] == root.val){
                index = i;
                break;
            }
        }
        root.left = buildTreeHelper(in, ins, index - 1,  pre, pres + 1,  pres + index - ins + 1);
        root.right = buildTreeHelper(in, index + 1, ine, pre, pres + (index - ins) + 1, pree);
        
        return root;
    }
}

Thanks

Upvotes: 3

Views: 577

Answers (1)

trincot
trincot

Reputation: 350167

Your serialization -- based on inorder and preorder representations -- is indeed dependent on the uniqueness of the values in the tree. Take for example this serialisation:

 inorder  | preorder
 1 1 2 1 2|1 1 1 2 2

These do not define a single binary tree. For instance, both of the following trees have those traversal orders:

    1                 1
   / \               / \
  1   2             1   1
 / \                   / \
1   2                 2   2

So you'll need to come up with another idea for serialization.

Upvotes: 6

Related Questions