Serialize and deserialize a binary tree

Time: O(n)

Space: O(n)

Intuition

Serialize via pre-order DFS: record node values and "#" for null nodes. Deserialize by consuming tokens in the same pre-order: the first non-null token is the root, recurse for left then right subtree.

Algorithm

1Serialize: preorder DFS, append val or "#", comma-separated.
2Deserialize: split by comma, use an index pointer (or queue of tokens). Consume first token: if "#" return null. Else create node, recurse left, then right.

Example Walkthrough

Input: Tree: 1â†’(2, 3â†’(4,5))

1.Serialize: "1,2,#,#,3,4,#,#,5,#,#".
2.Deserialize: read 1â†’root, read 2â†’left, read #â†’left.left=null, read #â†’left.right=null, ...

Output: Reconstructed tree = original tree

Common Pitfalls

•Use pre-order (not in-order) for serialization â€” in-order requires extra information to determine root.

Serialize and deserialize a binary tree.java

Java

// Approach: BFS serialization with null markers. Tokens are node values or '#' for null.
// Deserialize by replaying BFS queue with the token stream.
// Time: O(n) Space: O(n)
class Tree {
    int data;
    Tree left, right;

    Tree(int d) {
        data = d;
        left = right = null;
    }
}

class Tree {
    // Function to serialize a tree and return a list containing nodes of tree.
    public ArrayList<Integer> serialize(Node root) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(root.data);
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                Node cur = queue.poll();
                Node left = cur.left;
                Node right = cur.right;
                list.add(getVal(left));
                list.add(getVal(right));
                if (left != null)
                    queue.add(left);
                if (right != null)
                    queue.add(right);
            }
        }
        return list;
    }

    // Function to deserialize a list and construct the tree.
    public Node deSerialize(ArrayList<Integer> arr) {
        Node root = new Node(arr.get(0));
        int ind = 1;
        int n = arr.size();
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                Node cur = queue.poll();
                Node left = getNode(ind++, arr);
                Node right = getNode(ind++, arr);
                cur.left = left;
                cur.right = right;
                if (left != null)
                    queue.add(left);
                if (right != null)
                    queue.add(right);
            }
        }
        return root;
    }

    Node getNode(int ind, ArrayList<Integer> list) {
        if (ind >= list.size() || list.get(ind) == null)
            return null;
        return new Node(list.get(ind));
    }

    Integer getVal(Node cur) {
        if (cur == null)
            return null;
        return cur.data;
    }
};

Was this solution helpful?