{"id":6196,"date":"2025-01-05T21:13:14","date_gmt":"2025-01-05T21:13:14","guid":{"rendered":"https:\/\/algocademy.com\/blog\/how-to-handle-tree-serialization-a-comprehensive-guide\/"},"modified":"2026-10-15T12:51:16","modified_gmt":"2026-10-15T12:51:16","slug":"how-to-handle-tree-serialization-a-comprehensive-guide","status":"publish","type":"post","link":"https:\/\/algocademy.com\/blog\/how-to-handle-tree-serialization-a-comprehensive-guide\/","title":{"rendered":"Tree Serialization and Deserialization: Preorder and Level Order"},"content":{"rendered":"

To serialize a binary tree, walk it in a fixed order and write a marker such as null<\/code> for every missing child. To deserialize, read the tokens back in the same order. The markers are what make the result unambiguous: without them, a list of values cannot tell you where the branches are. This is the problem behind LeetCode 297, “Serialize and Deserialize Binary Tree”, and the two standard answers are preorder (depth-first) and level order (breadth-first). Both are below, with code that has been run.<\/p>\n

The setup<\/h2>\n

All the code uses this node class. The functions must work for any tree, including an empty tree, a single node, a skewed tree and negative values.<\/p>\n

from collections import deque\n\nclass TreeNode:\n    def __init__(self, val=0, left=None, right=None):\n        self.val = val\n        self.left = left\n        self.right = right<\/code><\/pre>\n
The example tree used throughout:<\/p>\n
#      1\n#     \/ \\\n#    2   3\n#       \/ \\\n#      4   5\nroot = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))<\/code><\/pre>\n
Why you need null markers<\/h2>\n
The preorder values of this tree are 1,2,3,4,5<\/code>. So are the preorder values of a right-leaning chain 1 -> 2 -> 3 -> 4 -> 5<\/code>. One traversal of values alone does not identify a tree. (For a binary search tree it does, because the ordering rule tells you where each value goes. That special case is covered near the end.) For a general binary tree, record the empty children too, and the traversal becomes reversible.<\/p>\n
Approach 1: preorder with null markers<\/h2>\n
Visit the node, then the left subtree, then the right subtree. Emit null<\/code> whenever you hit an empty child.<\/p>\n
def serialize_preorder(root):\n    out = []\n    def dfs(node):\n        if node is None:\n            out.append(\"null\")\n            return\n        out.append(str(node.val))\n        dfs(node.left)\n        dfs(node.right)\n    dfs(root)\n    return \",\".join(out)\n\ndef deserialize_preorder(data):\n    tokens = iter(data.split(\",\"))\n    def build():\n        tok = next(tokens)\n        if tok == \"null\":\n            return None\n        node = TreeNode(int(tok))\n        node.left = build()\n        node.right = build()\n        return node\n    return build()<\/code><\/pre>\n
For the example tree this prints:<\/p>\n
1,2,null,null,3,4,null,null,5,null,null<\/code><\/pre>\n
How deserialization reads it back<\/h3>\n
The shared iterator is the whole trick. Each call to build()<\/code> consumes exactly the tokens of one subtree, then returns, so the next call starts at the right place.<\/p>\n
    \n
  1. 1<\/code>: create node 1, then build its left subtree.<\/li>\n
  2. 2<\/code>: create node 2, build its left subtree. The next token is null<\/code>, so left is empty. The token after is null<\/code> too, so right is empty. Node 2 is a leaf; return it.<\/li>\n
  3. Back at node 1, build the right subtree. 3<\/code> becomes a node; its left reads 4<\/code>, null<\/code>, null<\/code> (a leaf), its right reads 5<\/code>, null<\/code>, null<\/code>.<\/li>\n
  4. All tokens are used and the tree is rebuilt.<\/li>\n<\/ol>\n
    Serializing the rebuilt tree gives the same string back, which confirms the round trip.<\/p>\n
    Approach 2: level order (BFS) with null markers<\/h2>\n
    This is the format LeetCode uses to display trees, so it is the one you see in examples like [1,2,3,null,null,4,5]<\/code>. Use a queue, and push both children of every real node, including missing ones.<\/p>\n
    def serialize_level(root):\n    if root is None:\n        return \"\"\n    out, queue = [], deque([root])\n    while queue:\n        node = queue.popleft()\n        if node is None:\n            out.append(\"null\")\n        else:\n            out.append(str(node.val))\n            queue.append(node.left)\n            queue.append(node.right)\n    while out[-1] == \"null\":   # trailing nulls carry no information\n        out.pop()\n    return \",\".join(out)\n\ndef deserialize_level(data):\n    if not data:\n        return None\n    tokens = data.split(\",\")\n    root = TreeNode(int(tokens[0]))\n    queue, i = deque([root]), 1\n    while queue and i < len(tokens):\n        node = queue.popleft()\n        if i < len(tokens) and tokens[i] != \"null\":\n            node.left = TreeNode(int(tokens[i]))\n            queue.append(node.left)\n        i += 1\n        if i < len(tokens) and tokens[i] != \"null\":\n            node.right = TreeNode(int(tokens[i]))\n            queue.append(node.right)\n        i += 1\n    return root<\/code><\/pre>\n
    For the example tree this prints:<\/p>\n
    1,2,3,null,null,4,5<\/code><\/pre>\n
    How deserialization reads it back<\/h3>\n
    Tokens are consumed two at a time, as the left and right child of the next node in the queue. Only real nodes enter the queue, so each node in it is waiting for its children.<\/p>\n
      \n
    1. Root is 1. Queue: [1]. Read 2<\/code>, 3<\/code>: they become the children of 1. Queue: [2, 3].<\/li>\n
    2. Pop 2. Read null<\/code>, null<\/code>: no children. Queue: [3].<\/li>\n
    3. Pop 3. Read 4<\/code>, 5<\/code>: its children. Queue: [4, 5].<\/li>\n
    4. Pop 4 and 5: tokens are used up, the loop ends.<\/li>\n<\/ol>\n
      Note that the output omits the nulls under 4 and 5. Trailing nulls are redundant because the reader stops when the tokens run out. Without trimming, the string would be 1,2,3,null,null,4,5,null,null,null,null<\/code>.<\/p>\n
      Which one to use<\/h2>\n\n\n\n\n\n\n\n\n\n
      <\/th>\nPreorder<\/th>\nLevel order<\/th>\n<\/tr>\n<\/thead>\n
      Time<\/td>\nO(n)<\/td>\nO(n)<\/td>\n<\/tr>\n
      Extra space<\/td>\nO(h) call stack, plus the output<\/td>\nO(w) queue, where w is the widest level, plus the output<\/td>\n<\/tr>\n
      Code<\/td>\nShortest; recursion mirrors the tree<\/td>\nIterative; no recursion limit<\/td>\n<\/tr>\n
      Output size<\/td>\nn values and n + 1 nulls<\/td>\nSame, minus the trailing nulls<\/td>\n<\/tr>\n
      Matches LeetCode’s display format<\/td>\nNo<\/td>\nYes<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
      Here n is the number of nodes and h is the height. In the worst case h = n (a skewed tree). In an interview, preorder is usually the faster one to write correctly. Choose level order when the format matters or the tree can be very deep. Both visit every node once, so time is linear either way.<\/p>\n
      Edge cases to test<\/h2>\n
      These cases were all run against both pairs of functions:<\/p>\n