Serialize and Deserialize N-ary Tree

hard tree dfs string design

Problem

Design serialize/deserialize for a tree where each node has an arbitrary number of children.

Inputroot = [1, [3, [5, 6], 2, 4]]

Output"1 4 3 2 5 0 6 0 2 0 4 0"

Each value is followed by its child count (here flattened with spaces).

tree (val,kids val,kids …)

class Codec:
    def serialize(self, root):
        out = []
        def dfs(node):
            if not node: return
            out.append(str(node.val)); out.append(str(len(node.children)))
            for c in node.children: dfs(c)
        dfs(root)
        return " ".join(out)
    def deserialize(self, data):
        if not data: return None
        toks = iter(data.split())
        def build():
            v = int(next(toks)); k = int(next(toks))
            node = Node(v, [])
            for _ in range(k): node.children.append(build())
            return node
        return build()

class Codec {
  serialize(root) {
    const out = [];
    const dfs = node => {
      if (!node) return;
      out.push(node.val, node.children.length);
      for (const c of node.children) dfs(c);
    };
    dfs(root);
    return out.join(" ");
  }
  deserialize(data) {
    if (!data) return null;
    const toks = data.split(" ");
    let idx = 0;
    const build = () => {
      const v = Number(toks[idx++]); const k = Number(toks[idx++]);
      const node = { val: v, children: [] };
      for (let i = 0; i < k; i++) node.children.push(build());
      return node;
    };
    return build();
  }
}

class Codec {
    public String serialize(Node root) {
        StringBuilder sb = new StringBuilder();
        dfs(root, sb);
        return sb.toString().trim();
    }
    void dfs(Node n, StringBuilder sb) {
        if (n == null) return;
        sb.append(n.val).append(' ').append(n.children.size()).append(' ');
        for (Node c : n.children) dfs(c, sb);
    }
    int idx;
    String[] toks;
    public Node deserialize(String data) {
        if (data.isEmpty()) return null;
        toks = data.split(" "); idx = 0;
        return build();
    }
    Node build() {
        int v = Integer.parseInt(toks[idx++]);
        int k = Integer.parseInt(toks[idx++]);
        Node n = new Node(v, new ArrayList<>());
        for (int i = 0; i < k; i++) n.children.add(build());
        return n;
    }
}

class Codec {
    int idx;
    vector toks;
    void dfs(Node* n, string& out) {
        if (!n) return;
        out += to_string(n->val) + " " + to_string(n->children.size()) + " ";
        for (auto* c : n->children) dfs(c, out);
    }
    Node* build() {
        int v = stoi(toks[idx++]);
        int k = stoi(toks[idx++]);
        Node* n = new Node(v, {});
        for (int i = 0; i < k; i++) n->children.push_back(build());
        return n;
    }
public:
    string serialize(Node* root) { string s; dfs(root, s); return s; }
    Node* deserialize(string data) {
        if (data.empty()) return nullptr;
        toks.clear();
        stringstream ss(data); string t;
        while (ss >> t) toks.push_back(t);
        idx = 0;
        return build();
    }
};

Explanation

In an N-ary tree a node can have any number of children, so we can't just write "left" and "right". The fix is simple: after each node's value, also write its child count. That number tells the rebuilder exactly how many children to read next.

Serialize does a DFS that emits node.val followed by node.children.length, then recurses into each child in order. So the stream is a flat list of value, count, value, count, ....

Deserialize reads tokens with a moving index. build() grabs the next value v and the next count k, makes a node, then calls build() exactly k times to produce its children. Because serialize wrote children right after their parent, the recursion consumes them in the right order.

Example: a root 1 with one child 3, where 3 has children 5, 6, 2, 4. The tokens read 1 1 3 4 5 0 6 0 2 0 4 0: node 1 says "1 child," so we build 3, which says "4 children," so we build 5, 6, 2, 4, each with count 0 (leaves).

Storing the count next to each value removes any need for null markers, and both passes touch every node once for linear-time work.

Time: O(n) Space: O(n)