#38 · Trees

Serialize and Deserialize Binary Tree

Design an algorithm to turn a binary tree into a string (serialize) and to rebuild exactly the same tree from that string (deserialize). The encoding format is up to you.

HardLeetCode

Current node
On the path / call stack
Done / found
Rejected
Temporary thread (Morris)

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Tree traversal with null markers

A traversal of values alone cannot recover a tree (many trees share one in-order sequence). Adding a marker for every missing child makes the sequence self-describing: a pre-order walk with "#" for empty children can be read back with one pass.

Memory layout

A list of at most 2n + 1 tokens (n values and n + 1 markers), joined by a delimiter. The delimiter is essential: values like 1 and 23 must not merge into "123".

Operation	Cost
serialize	O(n) time, O(n) output
deserialize	O(n) time (with a pointer), O(h) stack

Pre-order vs level-order encodings

Pre-order (node, left, right) is decoded recursively: the next token is always the root of the next subtree. Level order (BFS) is decoded with a queue: tokens come in pairs, the children of the queued nodes in order. Both are linear; pre-order is shorter for deep trees, level order is the familiar printing format.

Memory layout

Pre-order decoding keeps a stack of pending nodes (depth h); level-order decoding keeps a queue of nodes (width w).

Operation	Cost
choose by shape	stack O(h) versus queue O(w)

Why it fits

Marking absent children turns the tree into a complete binary shape, so the token stream has exactly one valid reading: this is what makes decoding unambiguous.
Both directions are one linear pass: each node and each empty slot produces one token and consumes one.
The decoder never needs lookahead: in pre-order the next token is the next root, in level order the next two tokens are the next children.

Why alternatives degrade

In-order sequence only:: Many different trees have the same in-order sequence, so it cannot be decoded without extra information.
Pre-order without null markers:: Ambiguous: a left-only and a right-only child produce the same sequence.
Two traversals (pre-order + in-order):: Works for distinct values (see the construct-tree problem) but doubles the size and fails with duplicate values.
No delimiter between values:: Values such as 1,23 and 12,3 would both become "123".

Four approaches, from naive to production

1 · beginner

Pre-order recursion with strings

time serialize O(n), deserialize O(n²) worst casespace O(n)

Serialize: return "value,left,right" recursively, "#" for a missing node. Deserialize: split on commas and build recursively, always taking the next token as the next root.

class Codec {
public:
    string serialize(TreeNode* root) {
        if (!root) return "#";
        return to_string(root->val) + "," + serialize(root->left) + "," + serialize(root->right);
    }
    TreeNode* deserialize(string data) {
        deque<string> tokens;
        stringstream ss(data); string tok;
        while (getline(ss, tok, ',')) tokens.push_back(tok);
        function<TreeNode*()> build = [&]() -> TreeNode* {
            string t = tokens.front(); tokens.pop_front();
            if (t == "#") return nullptr;
            TreeNode* node = new TreeNode(stoi(t));
            node->left = build();
            node->right = build();
            return node;
        };
        return build();
    }
};

class Codec {
    public String serialize(TreeNode root) {
        if (root == null) return "#";
        return root.val + "," + serialize(root.left) + "," + serialize(root.right);
    }

    public TreeNode deserialize(String data) {
        Deque<String> tokens = new ArrayDeque<>(Arrays.asList(data.split(",")));
        return build(tokens);
    }

    private TreeNode build(Deque<String> tokens) {
        String t = tokens.poll();
        if (t.equals("#")) return null;
        TreeNode node = new TreeNode(Integer.parseInt(t));
        node.left = build(tokens);
        node.right = build(tokens);
        return node;
    }
}

class Codec:
    def serialize(self, root):
        if not root: return '#'
        return f"{root.val},{self.serialize(root.left)},{self.serialize(root.right)}"

    def deserialize(self, data):
        tokens = deque(data.split(','))
        def build():
            t = tokens.popleft()
            if t == '#': return None
            node = TreeNode(int(t))
            node.left = build()
            node.right = build()
            return node
        return build()

class Codec {
  serialize(root: TreeNode | null): string {
    if (!root) return '#';
    return `${root.val},${this.serialize(root.left)},${this.serialize(root.right)}`;
  }
  deserialize(data: string): TreeNode | null {
    const tokens = data.split(',');
    const build = (): TreeNode | null => {
      const t = tokens.shift()!;
      if (t === '#') return null;
      const node = new TreeNode(Number(t));
      node.left = build();
      node.right = build();
      return node;
    };
    return build();
  }
}

Flaws & bottlenecks

tokens.shift() removes the first element of an array, which is O(n): decoding becomes O(n²).
Recursive string concatenation creates many intermediate strings.
Recursion depth equals the tree height; a chain of 10⁵ nodes overflows the stack.

Interviewer cross-questions

Why is a "#" marker needed?

Say: Without it you cannot tell where a subtree ends. With a marker for every missing child the sequence reads like a complete description: the decoder knows after each "#" that one subtree has just been finished.

Why does decoding consume tokens in order?

Say: The encoding is pre-order, so the next token is always the root of the subtree being built next: first the left subtree is built from the following tokens, then the right one.

How do you remove the O(n²) behavior?

Say: Replace shift() with a read index (O(1) per token), or use a deque. The advanced approach does exactly that.

2 · intermediate

Level order (BFS) with a queue

time O(n)space O(w)

Serialize with a queue, writing each node and its two children slots (including missing ones, as "#"). Deserialize with a queue of created nodes: each pair of tokens gives the left and right child of the next queued node.

class Codec {
public:
    string serialize(TreeNode* root) {
        vector<string> out;
        vector<TreeNode*> queue = {root};
        size_t head = 0;
        while (head < queue.size()) {
            TreeNode* node = queue[head++];
            if (!node) { out.push_back("#"); continue; }
            out.push_back(to_string(node->val));
            queue.push_back(node->left); queue.push_back(node->right);
        }
        string s; for (size_t k = 0; k < out.size(); k++) { if (k) s += ","; s += out[k]; }
        return s;
    }
    TreeNode* deserialize(string data) {
        vector<string> tokens; stringstream ss(data); string tok;
        while (getline(ss, tok, ',')) tokens.push_back(tok);
        if (tokens[0] == "#") return nullptr;
        TreeNode* root = new TreeNode(stoi(tokens[0]));
        vector<TreeNode*> queue = {root};
        size_t head = 0;
        for (size_t i = 1; i < tokens.size(); i += 2) {
            TreeNode* parent = queue[head++];
            if (tokens[i] != "#") { parent->left = new TreeNode(stoi(tokens[i])); queue.push_back(parent->left); }
            if (tokens[i + 1] != "#") { parent->right = new TreeNode(stoi(tokens[i + 1])); queue.push_back(parent->right); }
        }
        return root;
    }
};

class Codec {
    public String serialize(TreeNode root) {
        List<String> out = new ArrayList<>();
        List<TreeNode> queue = new ArrayList<>(); queue.add(root);
        int head = 0;
        while (head < queue.size()) {
            TreeNode node = queue.get(head++);
            if (node == null) { out.add("#"); continue; }
            out.add(String.valueOf(node.val));
            queue.add(node.left); queue.add(node.right);
        }
        return String.join(",", out);
    }

    public TreeNode deserialize(String data) {
        String[] tokens = data.split(",");
        if (tokens[0].equals("#")) return null;
        TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
        List<TreeNode> queue = new ArrayList<>(); queue.add(root);
        int head = 0;
        for (int i = 1; i < tokens.length; i += 2) {
            TreeNode parent = queue.get(head++);
            if (!tokens[i].equals("#")) { parent.left = new TreeNode(Integer.parseInt(tokens[i])); queue.add(parent.left); }
            if (!tokens[i + 1].equals("#")) { parent.right = new TreeNode(Integer.parseInt(tokens[i + 1])); queue.add(parent.right); }
        }
        return root;
    }
}

class Codec:
    def serialize(self, root):
        out = []
        queue = [root]
        head = 0
        while head < len(queue):
            node = queue[head]
            head += 1
            if not node:
                out.append('#')
                continue
            out.append(str(node.val))
            queue.append(node.left); queue.append(node.right)
        return ','.join(out)

    def deserialize(self, data):
        tokens = data.split(',')
        if tokens[0] == '#': return None
        root = TreeNode(int(tokens[0]))
        queue = [root]
        head = 0
        for i in range(1, len(tokens), 2):
            parent = queue[head]
            head += 1
            if tokens[i] != '#':
                parent.left = TreeNode(int(tokens[i])); queue.append(parent.left)
            if tokens[i + 1] != '#':
                parent.right = TreeNode(int(tokens[i + 1])); queue.append(parent.right)
        return root

class Codec {
  serialize(root: TreeNode | null): string {
    const out: string[] = [];
    const queue: (TreeNode | null)[] = [root];
    let head = 0;
    while (head < queue.length) {
      const node = queue[head++];
      if (!node) { out.push('#'); continue; }
      out.push(String(node.val));
      queue.push(node.left, node.right);
    }
    return out.join(',');
  }
  deserialize(data: string): TreeNode | null {
    const tokens = data.split(',');
    if (tokens[0] === '#') return null;
    const root = new TreeNode(Number(tokens[0]));
    const queue: TreeNode[] = [root];
    let head = 0;
    for (let i = 1; i < tokens.length; i += 2) {
      const parent = queue[head++];
      if (tokens[i] !== '#') { parent.left = new TreeNode(Number(tokens[i])); queue.push(parent.left); }
      if (tokens[i + 1] !== '#') { parent.right = new TreeNode(Number(tokens[i + 1])); queue.push(parent.right); }
    }
    return root;
  }
}

Flaws & bottlenecks

Writes trailing "#" tokens for every leaf (about n + 1 markers), so the text is longer than necessary (trailing markers could be trimmed).
The queue can hold a whole level: O(n) for a wide tree.
Two slightly different loops (null-aware in serialize, pair-based in deserialize) that must stay consistent.

Interviewer cross-questions

How many tokens does it produce?

Say: n values plus n + 1 "#" markers: 2n + 1 tokens in total, because a binary tree with n nodes has n + 1 empty child slots.

Why are the tokens read in pairs?

Say: Every node in the queue has exactly two child slots in the encoding, left then right, and nodes are processed in the same order as they were written.

Can you shorten the output?

Say: Yes: drop trailing "#" tokens (a decoder can treat missing tokens as empty), or use a compact binary format.

3 · advanced

Pre-order with a token array and an index

time O(n)space O(n)

Write tokens into an array during a pre-order walk and join once. Read them back with a shared index that advances by one per token.

class Codec {
public:
    string serialize(TreeNode* root) {
        vector<string> out;
        function<void(TreeNode*)> walk = [&](TreeNode* node) {
            if (!node) { out.push_back("#"); return; }
            out.push_back(to_string(node->val));
            walk(node->left);
            walk(node->right);
        };
        walk(root);
        string s; for (size_t k = 0; k < out.size(); k++) { if (k) s += ","; s += out[k]; }
        return s;
    }
    TreeNode* deserialize(string data) {
        vector<string> tokens; stringstream ss(data); string tok;
        while (getline(ss, tok, ',')) tokens.push_back(tok);
        size_t i = 0;
        function<TreeNode*()> build = [&]() -> TreeNode* {
            string t = tokens[i++];
            if (t == "#") return nullptr;
            TreeNode* node = new TreeNode(stoi(t));
            node->left = build();
            node->right = build();
            return node;
        };
        return build();
    }
};

class Codec {
    public String serialize(TreeNode root) {
        List<String> out = new ArrayList<>();
        walk(root, out);
        return String.join(",", out);
    }

    private void walk(TreeNode node, List<String> out) {
        if (node == null) { out.add("#"); return; }
        out.add(String.valueOf(node.val));
        walk(node.left, out);
        walk(node.right, out);
    }

    public TreeNode deserialize(String data) {
        String[] tokens = data.split(",");
        return build(tokens, new int[]{0});
    }

    private TreeNode build(String[] tokens, int[] i) {
        String t = tokens[i[0]++];
        if (t.equals("#")) return null;
        TreeNode node = new TreeNode(Integer.parseInt(t));
        node.left = build(tokens, i);
        node.right = build(tokens, i);
        return node;
    }
}

class Codec:
    def serialize(self, root):
        out = []
        def walk(node):
            if not node:
                out.append('#')
                return
            out.append(str(node.val))
            walk(node.left)
            walk(node.right)
        walk(root)
        return ','.join(out)

    def deserialize(self, data):
        tokens = data.split(',')
        i = 0
        def build():
            nonlocal i
            t = tokens[i]
            i += 1
            if t == '#': return None
            node = TreeNode(int(t))
            node.left = build()
            node.right = build()
            return node
        return build()

class Codec {
  serialize(root: TreeNode | null): string {
    const out: string[] = [];
    const walk = (node: TreeNode | null): void => {
      if (!node) { out.push('#'); return; }
      out.push(String(node.val));
      walk(node.left);
      walk(node.right);
    };
    walk(root);
    return out.join(',');
  }
  deserialize(data: string): TreeNode | null {
    const tokens = data.split(',');
    let i = 0;
    const build = (): TreeNode | null => {
      const t = tokens[i++];
      if (t === '#') return null;
      const node = new TreeNode(Number(t));
      node.left = build();
      node.right = build();
      return node;
    };
    return build();
  }
}

Flaws & bottlenecks

Recursion depth equals the tree height in both directions.
The shared index i is mutable state captured by the closure: decoding is not re-entrant.
Text format: numbers are written in decimal, which is bulky for large trees.

Interviewer cross-questions

Why is the index better than shift()?

Say: Advancing an integer is O(1), while removing the first array element shifts every other element, which is O(n). Over n tokens that is O(n) versus O(n²).

How would you make decoding safe against malformed input?

Say: Check i against the token count before every read, validate that every token is "#" or an integer, and verify that all tokens are consumed at the end. Reject anything else instead of returning a partial tree.

Is the format unique?

Say: Yes for a given tree: pre-order with markers is a canonical form, and distinct trees give distinct strings (because the marker positions encode the shape).

4 · expert

Iterative both ways

time O(n)space O(n)

Serialize with an explicit stack (push right then left). Deserialize with a stack of nodes each flagged "needs left" or "needs right": read a token, attach it to the top node, advance the flag, and push the new node.

class Codec {
public:
    string serialize(TreeNode* root) {
        vector<string> out;
        vector<TreeNode*> stack = {root};
        while (!stack.empty()) {
            TreeNode* node = stack.back(); stack.pop_back();
            if (!node) { out.push_back("#"); continue; }
            out.push_back(to_string(node->val));
            stack.push_back(node->right); stack.push_back(node->left);
        }
        string s; for (size_t k = 0; k < out.size(); k++) { if (k) s += ","; s += out[k]; }
        return s;
    }
    TreeNode* deserialize(string data) {
        vector<string> tokens; stringstream ss(data); string tok;
        while (getline(ss, tok, ',')) tokens.push_back(tok);
        if (tokens[0] == "#") return nullptr;
        TreeNode* root = new TreeNode(stoi(tokens[0]));
        struct Frame { TreeNode* node; bool left; };
        vector<Frame> stack = {{root, true}};
        size_t i = 1;
        while (!stack.empty() && i < tokens.size()) {
            Frame& top = stack.back();
            string t = tokens[i++];
            TreeNode* child = t == "#" ? nullptr : new TreeNode(stoi(t));
            if (top.left) { top.node->left = child; top.left = false; }
            else { top.node->right = child; stack.pop_back(); }
            if (child) stack.push_back({child, true});
        }
        return root;
    }
};

class Codec {
    public String serialize(TreeNode root) {
        List<String> out = new ArrayList<>();
        List<TreeNode> stack = new ArrayList<>(); stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.remove(stack.size() - 1);
            if (node == null) { out.add("#"); continue; }
            out.add(String.valueOf(node.val));
            stack.add(node.right); stack.add(node.left);
        }
        return String.join(",", out);
    }

    public TreeNode deserialize(String data) {
        String[] tokens = data.split(",");
        if (tokens[0].equals("#")) return null;
        TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
        Deque<Object[]> stack = new ArrayDeque<>(); stack.push(new Object[]{root, true});
        int i = 1;
        while (!stack.isEmpty() && i < tokens.length) {
            Object[] top = stack.peek();
            String t = tokens[i++];
            TreeNode child = t.equals("#") ? null : new TreeNode(Integer.parseInt(t));
            TreeNode owner = (TreeNode) top[0];
            if ((Boolean) top[1]) { owner.left = child; top[1] = false; }
            else { owner.right = child; stack.pop(); }
            if (child != null) stack.push(new Object[]{child, true});
        }
        return root;
    }
}

class Codec:
    def serialize(self, root):
        out = []
        stack = [root]
        while stack:
            node = stack.pop()
            if not node:
                out.append('#')
                continue
            out.append(str(node.val))
            stack.append(node.right); stack.append(node.left)
        return ','.join(out)

    def deserialize(self, data):
        tokens = data.split(',')
        if tokens[0] == '#': return None
        root = TreeNode(int(tokens[0]))
        stack = [[root, True]]
        i = 1
        while stack and i < len(tokens):
            top = stack[-1]
            t = tokens[i]
            i += 1
            child = None if t == '#' else TreeNode(int(t))
            if top[1]:
                top[0].left = child
                top[1] = False
            else:
                top[0].right = child
                stack.pop()
            if child: stack.append([child, True])
        return root

class Codec {
  serialize(root: TreeNode | null): string {
    const out: string[] = [];
    const stack: (TreeNode | null)[] = [root];
    while (stack.length > 0) {
      const node = stack.pop()!;
      if (!node) { out.push('#'); continue; }
      out.push(String(node.val));
      stack.push(node.right, node.left);
    }
    return out.join(',');
  }
  deserialize(data: string): TreeNode | null {
    const tokens = data.split(',');
    if (tokens[0] === '#') return null;
    const root = new TreeNode(Number(tokens[0]));
    const stack: { node: TreeNode; left: boolean }[] = [{ node: root, left: true }];
    let i = 1;
    while (stack.length > 0 && i < tokens.length) {
      const top = stack[stack.length - 1];
      const t = tokens[i++];
      const child = t === '#' ? null : new TreeNode(Number(t));
      if (top.left) { top.node.left = child; top.left = false; }
      else { top.node.right = child; stack.pop(); }
      if (child) stack.push({ node: child, left: true });
    }
    return root;
  }
}

Flaws & bottlenecks

More intricate control flow than the recursive code (the left/right flag is easy to get wrong).
Pushing the two children, including missing ones, allocates more entries than a recursive walk would hold at once.
No input validation: a truncated or corrupt string can leave the tree incomplete.

Interviewer cross-questions

Why does the serializer push the right child before the left child?

Say: The stack is last-in first-out, so pushing right first and left second pops the left child first, giving pre-order (node, left subtree, right subtree).

What does the "left" flag represent when decoding?

Say: Whether the node on top of the stack is still waiting for its left child (true) or for its right child (false). After the right child is attached, the node is complete and is popped.

Why avoid recursion at all?

Say: A degenerate tree (a chain of 100,000 nodes) would need 100,000 stack frames, which overflows in most runtimes. The explicit stack is limited only by heap memory.

Synchronized code walkthrough

Showing: Pre-order recursion with strings — shares the player above; click any step to jump.

class Codec {
public:
    string serialize(TreeNode* root) {
        if (!root) return "#";
        return to_string(root->val) + "," + serialize(root->left) + "," + serialize(root->right);
    }
    TreeNode* deserialize(string data) {
        deque<string> tokens;
        stringstream ss(data); string tok;
        while (getline(ss, tok, ',')) tokens.push_back(tok);
        function<TreeNode*()> build = [&]() -> TreeNode* {
            string t = tokens.front(); tokens.pop_front();
            if (t == "#") return nullptr;
            TreeNode* node = new TreeNode(stoi(t));
            node->left = build();
            node->right = build();
            return node;
        };
        return build();
    }
};

class Codec {
    public String serialize(TreeNode root) {
        if (root == null) return "#";
        return root.val + "," + serialize(root.left) + "," + serialize(root.right);
    }

    public TreeNode deserialize(String data) {
        Deque<String> tokens = new ArrayDeque<>(Arrays.asList(data.split(",")));
        return build(tokens);
    }

    private TreeNode build(Deque<String> tokens) {
        String t = tokens.poll();
        if (t.equals("#")) return null;
        TreeNode node = new TreeNode(Integer.parseInt(t));
        node.left = build(tokens);
        node.right = build(tokens);
        return node;
    }
}

class Codec:
    def serialize(self, root):
        if not root: return '#'
        return f"{root.val},{self.serialize(root.left)},{self.serialize(root.right)}"

    def deserialize(self, data):
        tokens = deque(data.split(','))
        def build():
            t = tokens.popleft()
            if t == '#': return None
            node = TreeNode(int(t))
            node.left = build()
            node.right = build()
            return node
        return build()

class Codec {
  serialize(root: TreeNode | null): string {
    if (!root) return '#';
    return `${root.val},${this.serialize(root.left)},${this.serialize(root.right)}`;
  }
  deserialize(data: string): TreeNode | null {
    const tokens = data.split(',');
    const build = (): TreeNode | null => {
      const t = tokens.shift()!;
      if (t === '#') return null;
      const node = new TreeNode(Number(t));
      node.left = build();
      node.right = build();
      return node;
    };
    return build();
  }
}

class Codec {
public:
    string serialize(TreeNode* root) {
        vector<string> out;
        vector<TreeNode*> queue = {root};
        size_t head = 0;
        while (head < queue.size()) {
            TreeNode* node = queue[head++];
            if (!node) { out.push_back("#"); continue; }
            out.push_back(to_string(node->val));
            queue.push_back(node->left); queue.push_back(node->right);
        }
        string s; for (size_t k = 0; k < out.size(); k++) { if (k) s += ","; s += out[k]; }
        return s;
    }
    TreeNode* deserialize(string data) {
        vector<string> tokens; stringstream ss(data); string tok;
        while (getline(ss, tok, ',')) tokens.push_back(tok);
        if (tokens[0] == "#") return nullptr;
        TreeNode* root = new TreeNode(stoi(tokens[0]));
        vector<TreeNode*> queue = {root};
        size_t head = 0;
        for (size_t i = 1; i < tokens.size(); i += 2) {
            TreeNode* parent = queue[head++];
            if (tokens[i] != "#") { parent->left = new TreeNode(stoi(tokens[i])); queue.push_back(parent->left); }
            if (tokens[i + 1] != "#") { parent->right = new TreeNode(stoi(tokens[i + 1])); queue.push_back(parent->right); }
        }
        return root;
    }
};

class Codec {
    public String serialize(TreeNode root) {
        List<String> out = new ArrayList<>();
        List<TreeNode> queue = new ArrayList<>(); queue.add(root);
        int head = 0;
        while (head < queue.size()) {
            TreeNode node = queue.get(head++);
            if (node == null) { out.add("#"); continue; }
            out.add(String.valueOf(node.val));
            queue.add(node.left); queue.add(node.right);
        }
        return String.join(",", out);
    }

    public TreeNode deserialize(String data) {
        String[] tokens = data.split(",");
        if (tokens[0].equals("#")) return null;
        TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
        List<TreeNode> queue = new ArrayList<>(); queue.add(root);
        int head = 0;
        for (int i = 1; i < tokens.length; i += 2) {
            TreeNode parent = queue.get(head++);
            if (!tokens[i].equals("#")) { parent.left = new TreeNode(Integer.parseInt(tokens[i])); queue.add(parent.left); }
            if (!tokens[i + 1].equals("#")) { parent.right = new TreeNode(Integer.parseInt(tokens[i + 1])); queue.add(parent.right); }
        }
        return root;
    }
}

class Codec:
    def serialize(self, root):
        out = []
        queue = [root]
        head = 0
        while head < len(queue):
            node = queue[head]
            head += 1
            if not node:
                out.append('#')
                continue
            out.append(str(node.val))
            queue.append(node.left); queue.append(node.right)
        return ','.join(out)

    def deserialize(self, data):
        tokens = data.split(',')
        if tokens[0] == '#': return None
        root = TreeNode(int(tokens[0]))
        queue = [root]
        head = 0
        for i in range(1, len(tokens), 2):
            parent = queue[head]
            head += 1
            if tokens[i] != '#':
                parent.left = TreeNode(int(tokens[i])); queue.append(parent.left)
            if tokens[i + 1] != '#':
                parent.right = TreeNode(int(tokens[i + 1])); queue.append(parent.right)
        return root

class Codec {
  serialize(root: TreeNode | null): string {
    const out: string[] = [];
    const queue: (TreeNode | null)[] = [root];
    let head = 0;
    while (head < queue.length) {
      const node = queue[head++];
      if (!node) { out.push('#'); continue; }
      out.push(String(node.val));
      queue.push(node.left, node.right);
    }
    return out.join(',');
  }
  deserialize(data: string): TreeNode | null {
    const tokens = data.split(',');
    if (tokens[0] === '#') return null;
    const root = new TreeNode(Number(tokens[0]));
    const queue: TreeNode[] = [root];
    let head = 0;
    for (let i = 1; i < tokens.length; i += 2) {
      const parent = queue[head++];
      if (tokens[i] !== '#') { parent.left = new TreeNode(Number(tokens[i])); queue.push(parent.left); }
      if (tokens[i + 1] !== '#') { parent.right = new TreeNode(Number(tokens[i + 1])); queue.push(parent.right); }
    }
    return root;
  }
}

class Codec {
public:
    string serialize(TreeNode* root) {
        vector<string> out;
        function<void(TreeNode*)> walk = [&](TreeNode* node) {
            if (!node) { out.push_back("#"); return; }
            out.push_back(to_string(node->val));
            walk(node->left);
            walk(node->right);
        };
        walk(root);
        string s; for (size_t k = 0; k < out.size(); k++) { if (k) s += ","; s += out[k]; }
        return s;
    }
    TreeNode* deserialize(string data) {
        vector<string> tokens; stringstream ss(data); string tok;
        while (getline(ss, tok, ',')) tokens.push_back(tok);
        size_t i = 0;
        function<TreeNode*()> build = [&]() -> TreeNode* {
            string t = tokens[i++];
            if (t == "#") return nullptr;
            TreeNode* node = new TreeNode(stoi(t));
            node->left = build();
            node->right = build();
            return node;
        };
        return build();
    }
};

class Codec {
    public String serialize(TreeNode root) {
        List<String> out = new ArrayList<>();
        walk(root, out);
        return String.join(",", out);
    }

    private void walk(TreeNode node, List<String> out) {
        if (node == null) { out.add("#"); return; }
        out.add(String.valueOf(node.val));
        walk(node.left, out);
        walk(node.right, out);
    }

    public TreeNode deserialize(String data) {
        String[] tokens = data.split(",");
        return build(tokens, new int[]{0});
    }

    private TreeNode build(String[] tokens, int[] i) {
        String t = tokens[i[0]++];
        if (t.equals("#")) return null;
        TreeNode node = new TreeNode(Integer.parseInt(t));
        node.left = build(tokens, i);
        node.right = build(tokens, i);
        return node;
    }
}

class Codec:
    def serialize(self, root):
        out = []
        def walk(node):
            if not node:
                out.append('#')
                return
            out.append(str(node.val))
            walk(node.left)
            walk(node.right)
        walk(root)
        return ','.join(out)

    def deserialize(self, data):
        tokens = data.split(',')
        i = 0
        def build():
            nonlocal i
            t = tokens[i]
            i += 1
            if t == '#': return None
            node = TreeNode(int(t))
            node.left = build()
            node.right = build()
            return node
        return build()

class Codec {
  serialize(root: TreeNode | null): string {
    const out: string[] = [];
    const walk = (node: TreeNode | null): void => {
      if (!node) { out.push('#'); return; }
      out.push(String(node.val));
      walk(node.left);
      walk(node.right);
    };
    walk(root);
    return out.join(',');
  }
  deserialize(data: string): TreeNode | null {
    const tokens = data.split(',');
    let i = 0;
    const build = (): TreeNode | null => {
      const t = tokens[i++];
      if (t === '#') return null;
      const node = new TreeNode(Number(t));
      node.left = build();
      node.right = build();
      return node;
    };
    return build();
  }
}

class Codec {
public:
    string serialize(TreeNode* root) {
        vector<string> out;
        vector<TreeNode*> stack = {root};
        while (!stack.empty()) {
            TreeNode* node = stack.back(); stack.pop_back();
            if (!node) { out.push_back("#"); continue; }
            out.push_back(to_string(node->val));
            stack.push_back(node->right); stack.push_back(node->left);
        }
        string s; for (size_t k = 0; k < out.size(); k++) { if (k) s += ","; s += out[k]; }
        return s;
    }
    TreeNode* deserialize(string data) {
        vector<string> tokens; stringstream ss(data); string tok;
        while (getline(ss, tok, ',')) tokens.push_back(tok);
        if (tokens[0] == "#") return nullptr;
        TreeNode* root = new TreeNode(stoi(tokens[0]));
        struct Frame { TreeNode* node; bool left; };
        vector<Frame> stack = {{root, true}};
        size_t i = 1;
        while (!stack.empty() && i < tokens.size()) {
            Frame& top = stack.back();
            string t = tokens[i++];
            TreeNode* child = t == "#" ? nullptr : new TreeNode(stoi(t));
            if (top.left) { top.node->left = child; top.left = false; }
            else { top.node->right = child; stack.pop_back(); }
            if (child) stack.push_back({child, true});
        }
        return root;
    }
};

class Codec {
    public String serialize(TreeNode root) {
        List<String> out = new ArrayList<>();
        List<TreeNode> stack = new ArrayList<>(); stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.remove(stack.size() - 1);
            if (node == null) { out.add("#"); continue; }
            out.add(String.valueOf(node.val));
            stack.add(node.right); stack.add(node.left);
        }
        return String.join(",", out);
    }

    public TreeNode deserialize(String data) {
        String[] tokens = data.split(",");
        if (tokens[0].equals("#")) return null;
        TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
        Deque<Object[]> stack = new ArrayDeque<>(); stack.push(new Object[]{root, true});
        int i = 1;
        while (!stack.isEmpty() && i < tokens.length) {
            Object[] top = stack.peek();
            String t = tokens[i++];
            TreeNode child = t.equals("#") ? null : new TreeNode(Integer.parseInt(t));
            TreeNode owner = (TreeNode) top[0];
            if ((Boolean) top[1]) { owner.left = child; top[1] = false; }
            else { owner.right = child; stack.pop(); }
            if (child != null) stack.push(new Object[]{child, true});
        }
        return root;
    }
}

class Codec:
    def serialize(self, root):
        out = []
        stack = [root]
        while stack:
            node = stack.pop()
            if not node:
                out.append('#')
                continue
            out.append(str(node.val))
            stack.append(node.right); stack.append(node.left)
        return ','.join(out)

    def deserialize(self, data):
        tokens = data.split(',')
        if tokens[0] == '#': return None
        root = TreeNode(int(tokens[0]))
        stack = [[root, True]]
        i = 1
        while stack and i < len(tokens):
            top = stack[-1]
            t = tokens[i]
            i += 1
            child = None if t == '#' else TreeNode(int(t))
            if top[1]:
                top[0].left = child
                top[1] = False
            else:
                top[0].right = child
                stack.pop()
            if child: stack.append([child, True])
        return root

class Codec {
  serialize(root: TreeNode | null): string {
    const out: string[] = [];
    const stack: (TreeNode | null)[] = [root];
    while (stack.length > 0) {
      const node = stack.pop()!;
      if (!node) { out.push('#'); continue; }
      out.push(String(node.val));
      stack.push(node.right, node.left);
    }
    return out.join(',');
  }
  deserialize(data: string): TreeNode | null {
    const tokens = data.split(',');
    if (tokens[0] === '#') return null;
    const root = new TreeNode(Number(tokens[0]));
    const stack: { node: TreeNode; left: boolean }[] = [{ node: root, left: true }];
    let i = 1;
    while (stack.length > 0 && i < tokens.length) {
      const top = stack[stack.length - 1];
      const t = tokens[i++];
      const child = t === '#' ? null : new TreeNode(Number(t));
      if (top.left) { top.node.left = child; top.left = false; }
      else { top.node.right = child; stack.pop(); }
      if (child) stack.push({ node: child, left: true });
    }
    return root;
  }
}