Serialize and Deserialize Binary Tree

Hard

#0284Time: O(N) - Both serialization and deserialization processes visit each node exactly once, where N is the total number of nodes in the tree.Space: O(N) - In the worst-case scenario (a complete binary tree), the maximum number of nodes in the queue at any time is proportional to the number of nodes in the tree (W ≈ N/2), leading to O(N) space. The string itself also takes O(N) space.10 companies

Patterns

Design

Algorithms

Depth-First Search Breadth-First Search Merkle Tree

Data structures

String Tree Binary Tree

Companies

DoorDash Intuit LinkedIn Nvidia

Prompt

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 10⁴].
-1000 <= Node.val <= 1000

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a Breadth-First Search (BFS), also known as a level-order traversal, to serialize the tree. We traverse the tree level by level, from left to right, and record the value of each node. A special marker (e.g., "N" or "#") is used for null nodes to ensure the tree's structure can be perfectly reconstructed.

Algorithm

Serialization (BFS)
1. If the root is null, return an empty string or a specific marker for an empty tree.
2. Initialize a queue (java.util.Queue) and add the root node to it.
3. Initialize a StringBuilder to construct the serialized string.
4. Loop while the queue is not empty: a. Dequeue a node curr. b. If curr is null, append a null marker (e.g., "N") and a delimiter to the StringBuilder. c. If curr is not null, append its value and a delimiter. Then, enqueue its left and right children.
5. Return the final string from the StringBuilder.
Deserialization (BFS)
1. If the input string is empty or represents a null tree, return null.
2. Split the input string by the delimiter to get an array of value strings.
3. Create the root node from the first value in the array.
4. Initialize a queue and add the root to it. This queue will hold parent nodes awaiting their children.
5. Iterate through the rest of the value strings, starting from the second element (i = 1).
6. In each iteration, dequeue a parent node.
7. Process the next value string (nodes[i]) for the left child. If it's not the null marker, create a new node, attach it as parent.left, and enqueue the new node.
8. Process the subsequent value string (nodes[i+1]) for the right child in the same manner.
9. Continue until all values are processed and the tree is reconstructed.
10. Return the root.

Walkthrough

Serialization

The serialization process involves a level-order traversal using a queue. We start with the root. As we visit each node, we append its value to a string. If a node is null, we append a special marker. Crucially, for any non-null node we visit, we add both its left and right children to the queue, even if they are null. This ensures that the structure of the tree is preserved. The process continues until the queue is empty.

1public class Codec {2    private static final String NULL_SYMBOL = "N";3    private static final String DELIMITER = ",";4 5    // Encodes a tree to a single string.6    public String serialize(TreeNode root) {7        if (root == null) {8            return "";9        }10 11        StringBuilder sb = new StringBuilder();12        Queue<TreeNode> queue = new LinkedList<>();13        queue.offer(root);14 15        while (!queue.isEmpty()) {16            TreeNode node = queue.poll();17            if (node == null) {18                sb.append(NULL_SYMBOL).append(DELIMITER);19                continue;20            }21            sb.append(node.val).append(DELIMITER);22            queue.offer(node.left);23            queue.offer(node.right);24        }25        return sb.toString();26    }

Deserialization

To deserialize, we first split the string by our delimiter to get an array of values. The first value corresponds to the root. We create the root node and add it to a queue. This queue will keep track of the parent nodes whose children we need to attach. We then iterate through the rest of the values in pairs. For each parent node we dequeue, the next two values in the array represent its left and right children. If a value is not our null marker, we create a new node, attach it to the parent, and add the new node to the queue to have its own children attached later. This reconstructs the tree in the same level-order it was serialized.

1    // Decodes your encoded data to tree.2    public TreeNode deserialize(String data) {3        if (data == null || data.isEmpty()) {4            return null;5        }6 7        String[] nodes = data.split(DELIMITER);8        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));9        Queue<TreeNode> queue = new LinkedList<>();10        queue.offer(root);11        int i = 1;12 13        while (!queue.isEmpty() && i < nodes.length) {14            TreeNode parent = queue.poll();15 16            // Left child17            if (!nodes[i].equals(NULL_SYMBOL)) {18                TreeNode left = new TreeNode(Integer.parseInt(nodes[i]));19                parent.left = left;20                queue.offer(left);21            }22            i++;23 24            // Right child25            if (i < nodes.length && !nodes[i].equals(NULL_SYMBOL)) {26                TreeNode right = new TreeNode(Integer.parseInt(nodes[i]));27                parent.right = right;28                queue.offer(right);29            }30            i++;31        }32        return root;33    }34}

Complexity

Time

O(N) - Both serialization and deserialization processes visit each node exactly once, where N is the total number of nodes in the tree.

Space

O(N) - In the worst-case scenario (a complete binary tree), the maximum number of nodes in the queue at any time is proportional to the number of nodes in the tree (W ≈ N/2), leading to O(N) space. The string itself also takes O(N) space.

Trade-offs

Pros

The logic is straightforward and follows the standard iterative BFS pattern.
It avoids deep recursion, which prevents potential StackOverflowError for very deep trees.

Cons

Can be less space-efficient than a DFS approach for balanced trees, as the queue's size is proportional to the tree's maximum width (O(N) in the worst case).
The serialized string might contain many trailing null markers for the last level, which can make the string longer than necessary (though this can be optimized).

This approach utilizes a Depth-First Search (DFS), specifically a pre-order traversal (Root-Left-Right), for both serialization and deserialization. The pre-order sequence is ideal for reconstruction because the root of any subtree is always processed before its children, making it easy to rebuild the tree recursively.

Algorithm

Serialization (Pre-order DFS)
1. Define a recursive helper function, buildString(node, stringBuilder).
2. Base Case: If the current node is null, append a null marker (e.g., "#") and a delimiter to the stringBuilder, then return.
3. Recursive Step: a. Append the current node.val and a delimiter. b. Recursively call buildString for the left child: buildString(node.left, stringBuilder). c. Recursively call buildString for the right child: buildString(node.right, stringBuilder).
4. The main serialize function initializes the StringBuilder and starts the recursion from the root.
Deserialization (Pre-order DFS)
1. Split the serialized string by the delimiter into a queue of values.
2. Define a recursive helper function, buildTree(nodesQueue).
3. Base Case: Dequeue a value. If it's the null marker, return null.
4. Recursive Step: a. Create a new TreeNode with the dequeued value. b. Reconstruct the left subtree by recursively calling node.left = buildTree(nodesQueue). c. Reconstruct the right subtree by recursively calling node.right = buildTree(nodesQueue). d. Return the created node.
5. The main deserialize function initializes the queue and starts the recursion.

Walkthrough

Serialization

Serialization is performed using a recursive pre-order traversal. The helper function traverses the tree and builds a string. When it encounters a non-null node, it appends the node's value followed by a delimiter. When it encounters a null child pointer, it appends a special null marker (e.g., "#") and a delimiter. This marking of nulls is essential to distinguish between different tree structures that might otherwise have the same pre-order traversal of values.

1public class Codec {2    private static final String NULL_SYMBOL = "#";3    private static final String DELIMITER = ",";4 5    // Encodes a tree to a single string.6    public String serialize(TreeNode root) {7        StringBuilder sb = new StringBuilder();8        buildString(root, sb);9        return sb.toString();10    }11 12    private void buildString(TreeNode node, StringBuilder sb) {13        if (node == null) {14            sb.append(NULL_SYMBOL).append(DELIMITER);15        } else {16            sb.append(node.val).append(DELIMITER);17            buildString(node.left, sb);18            buildString(node.right, sb);19        }20    }

Deserialization

For deserialization, we first split the string into a list or queue of values. We then use a recursive helper function that consumes values from this queue to build the tree. The function reads the next value: if it's the null marker, it returns null. Otherwise, it creates a new node with the value. Then, it makes a recursive call to build the left subtree and another to build the right subtree. Because the data is in pre-order, the recursive calls naturally consume the correct values from the queue to form the left and right subtrees in the correct order.

1    // Decodes your encoded data to tree.2    public TreeNode deserialize(String data) {3        if (data == null || data.isEmpty()) {4            return null;5        }6        Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(DELIMITER)));7        return buildTree(nodes);8    }9 10    private TreeNode buildTree(Queue<String> nodes) {11        String val = nodes.poll();12        if (val.equals(NULL_SYMBOL)) {13            return null;14        } else {15            TreeNode node = new TreeNode(Integer.parseInt(val));16            node.left = buildTree(nodes);17            node.right = buildTree(nodes);18            return node;19        }20    }21}

Complexity

Time

O(N) - Both serialization and deserialization require visiting each node and null marker once. Therefore, the time complexity is linear with respect to the number of nodes.

Space

O(N) - The space is dominated by the recursion call stack and the storage for the serialized string. The recursion depth is equal to the height of the tree, H. In the worst case of a skewed tree, H can be N, leading to O(N) space. For a balanced tree, it's O(log N). The string itself also requires O(N) space.

Trade-offs

Pros

Elegant and concise recursive implementation that naturally maps to the tree structure.
Generally more space-efficient for average and balanced trees, as the space complexity of the call stack is O(H), where H is the tree height (O(log N) for a balanced tree).

Cons

For very deep and skewed trees, the recursion depth can be large, potentially leading to a StackOverflowError.
The recursive implementation might be slightly less intuitive for beginners compared to the iterative BFS approach.

Solutions

Solution

1/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int x) { val = x; } * } */ public class Codec { // Encodes a tree to a single string. public string serialize ( TreeNode root ) { if ( root == null ) { return null ; } List < string > ans = new List < string >(); Queue < TreeNode > q = new Queue < TreeNode >(); q . Enqueue ( root ); while ( q . Count > 0 ) { TreeNode node = q . Dequeue (); if ( node != null ) { ans . Add ( node . val . ToString ()); q . Enqueue ( node . left ); q . Enqueue ( node . right ); } else { ans . Add ( "#" ); } } return string . Join ( "," , ans ); } // Decodes your encoded data to tree. public TreeNode deserialize ( string data ) { if ( data == null ) { return null ; } string [] vals = data . Split ( ',' ); int i = 0 ; TreeNode root = new TreeNode ( int . Parse ( vals [ i ++])); Queue < TreeNode > q = new Queue < TreeNode >(); q . Enqueue ( root ); while ( q . Count > 0 ) { TreeNode node = q . Dequeue (); if ( vals [ i ] != "#" ) { node . left = new TreeNode ( int . Parse ( vals [ i ])); q . Enqueue ( node . left ); } i ++; if ( vals [ i ] != "#" ) { node . right = new TreeNode ( int . Parse ( vals [ i ])); q . Enqueue ( node . right ); } i ++; } return root ; } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.deserialize(codec.serialize(root));

1/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Codec { private static final String NULL = "#" ; private static final String SEP = "," ; // Encodes a tree to a single string. public String serialize ( TreeNode root ) { if ( root == null ) { return "" ; } StringBuilder sb = new StringBuilder (); preorder ( root , sb ); return sb . toString (); } private void preorder ( TreeNode root , StringBuilder sb ) { if ( root == null ) { sb . append ( NULL + SEP ); return ; } sb . append ( root . val + SEP ); preorder ( root . left , sb ); preorder ( root . right , sb ); } // Decodes your encoded data to tree. public TreeNode deserialize ( String data ) { if ( data == null || "" . equals ( data )) { return null ; } List < String > vals = new LinkedList <>(); for ( String x : data . split ( SEP )) { vals . add ( x ); } return deserialize ( vals ); } private TreeNode deserialize ( List < String > vals ) { String first = vals . remove ( 0 ); if ( NULL . equals ( first )) { return null ; } TreeNode root = new TreeNode ( Integer . parseInt ( first )); root . left = deserialize ( vals ); root . right = deserialize ( vals ); return root ; } } // Your Codec object will be instantiated and called as such: // Codec ser = new Codec(); // Codec deser = new Codec(); // TreeNode ans = deser.deserialize(ser.serialize(root));

1/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * Encodes a tree to a single string. * * @param {TreeNode} root * @return {string} */ var serialize =2  function (root) {3    return rserialize(root, "");4  };5/** * Decodes your encoded data to tree. * * @param {string} data * @return {TreeNode} */ var deserialize =6  function (data) {7    const dataArray = data.split(" , ");8    return rdeserialize(dataArray);9  };10const rserialize = (root, str) => {11  if (root === null) {12    str += " #, ";13  } else {14    str += root.val + "" + " , ";15    str = rserialize(root.left, str);16    str = rserialize(root.right, str);17  }18  return str;19};20const rdeserialize = (dataList) => {21  if (dataList[0] === " # ") {22    dataList.shift();23    return null;24  }25  const root = new TreeNode(parseInt(dataList[0]));26  dataList.shift();27  root.left = rdeserialize(dataList);28  root.right = rdeserialize(dataList);29  return root;30}; /** * Your functions will be called as such: * deserialize(serialize(root)); */

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Codec { public: // Encodes a tree to a single string. string serialize ( TreeNode * root ) { if ( ! root ) return "" ; string s = "" ; preorder ( root , s ); return s ; } void preorder ( TreeNode * root , string & s ) { if ( ! root ) s += "# " ; else { s += to_string ( root -> val ) + " " ; preorder ( root -> left , s ); preorder ( root -> right , s ); } } // Decodes your encoded data to tree. TreeNode * deserialize ( string data ) { if ( data == "" ) return nullptr ; stringstream ss ( data ); return deserialize ( ss ); } TreeNode * deserialize ( stringstream & ss ) { string first ; ss >> first ; if ( first == "#" ) return nullptr ; TreeNode * root = new TreeNode ( stoi ( first )); root -> left = deserialize ( ss ); root -> right = deserialize ( ss ); return root ; } }; // Your Codec object will be instantiated and called as such: // Codec ser, deser; // TreeNode* ans = deser.deserialize(ser.serialize(root));

1# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Codec : def serialize ( self , root ): """Encodes a tree to a single string. :type root: TreeNode :rtype: str """ if root is None : return '' res = [] def preorder ( root ): if root is None : res . append ( "#," ) return res . append ( str ( root . val ) + "," ) preorder ( root . left ) preorder ( root . right ) preorder ( root ) return '' . join ( res ) def deserialize ( self , data ): """Decodes your encoded data to tree. :type data: str :rtype: TreeNode """ if not data : return None vals = data . split ( ',' ) def inner (): first = vals . pop ( 0 ) if first == '#' : return None return TreeNode ( int ( first ), inner (), inner ()) # seems using a constructor __init__(val, left, right) return inner () # Your Codec object will be instantiated and called as such: # ser = Codec() # deser = Codec() # ans = deser.deserialize(ser.serialize(root)) ############ from collections import deque # bfs, each level based class Codec : def serialize ( self , root ): """Encodes a tree to a single string. :type root: TreeNode :rtype: str """ ret = [] queue = deque ([ root ]) while queue : top = queue . popleft () if not top : ret . append ( "None" ) continue else : ret . append ( str ( top . val )) queue . append ( top . left ) queue . append ( top . right ) return "," . join ( ret ) def deserialize ( self , data ): """Decodes your encoded data to tree. :type data: str :rtype: TreeNode """ data = data . split ( "," ) if data [ 0 ] == "None" : return None root = TreeNode ( int ( data [ 0 ])) queue = deque ([ root ]) i = 0 while queue and i < len ( data ): top = queue . popleft () i += 1 left = right = None if i < len ( data ) and data [ i ] != "None" : left = TreeNode ( int ( data [ i ])) queue . append ( left ) i += 1 if i < len ( data ) and data [ i ] != "None" : right = TreeNode ( int ( data [ i ])) queue . append ( right ) top . left = left top . right = right return root # Your Codec object will be instantiated and called as such: # codec = Codec() # codec.deserialize(codec.serialize(root))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem