Serialize BST Tree

Question

Im trying to serialize a BST so that it can be read in by another program. The out put has the node followed by all their children and their childrens children etc. Followed by closing brackets if there is are no additional children.

My methods output

(4 (2 (1 ) ) ( 3 ) ) (6  (5 )) (7 ))




public String serializePrefix(){
        StringBuilder str = new StringBuilder();
        serializePrefix (root, str, " ");
        return str.toString();
    }


    private void serializePrefix (Node t, StringBuilder str, String sep){
        int ID = 1;
        if (t == null)
            str.append(")");
        else{


                str.append("(" + t.data.toString() );
                str.append(sep);
                serializePrefix (t.left, str, sep);
                serializePrefix (t.right, str, sep);

        }

        ID++;

    }

I need the out put to be

(4 (2 (1 ) (3 ) ) (6 (5 ) (7 ) ) ))

This would create the tree

         4
       /  \
      2    6
    /  \  / \
   1   3  5  7 

Answer 1

Your first problem case is when you find a leaf: all your closing brackets ()) are doubled, because you try to advance toward the left and right links, but you find nulls, which trigger the ending bracket in your code.

private void serializePrefix (Node t, StringBuilder str, String sep){
    int ID = 1;
    if (t == null)
        //ERROR: if empty node found, apply close bracket
        str.append(")");
    else{
        str.append("(" + t.data.toString() );
        str.append(sep);

        //this is the problem part, for example for node number 1:
        serializePrefix (t.left, str, sep); //this writes ")" first time
        serializePrefix (t.right, str, sep); //this writes ")" second time

    }

    ID++;

}

The second issue is, that on the last branch, your brackets would not get closed properly, because when your algorithm "steps back" to the root, it does not close the opened brackets as it steps back one by one...

Fix proposal:

private void serializePrefix (Node t, StringBuilder str, String sep){
    int ID = 1;
    if (t == null)
        // do nothing!
        // str.append(")");
    else{
        str.append("(" + t.data.toString() );
        str.append(sep);

        //this is the problem part, for example for node number 1:
        serializePrefix (t.left, str, sep); //this writes ")" first time
        serializePrefix (t.right, str, sep); //this writes ")" second time

        //close opened bracket
        str.append(")");
    }

    ID++;

}

(by the way, it is a general advice to try to close what you open in the visible distance from where you opened it... This helps a lot with controlling leaks around resources like DB connections and the likes.)