Serialize and Deserialize Binary Tree - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const CURRENT = 'current', CURRENT_COLOR = 'blue';
const CURRENT_SUBTREE = 'current_subtree', CURRENT_SUBTREE_COLOR = 'orange';
const VISITED = 'visited', VISITED_COLOR = 'green';
const NULL_NODE = 'null_node', NULL_NODE_COLOR = 'red';

function visMainFunction(rootInput) { 
    initClassProperties();
    explanationAndColorSchemaNotifications();

    const originalRoot = convertInputToTree(rootInput);
    const originalTree = new VisBinaryTree(originalRoot, { dataPropName: 'val' }); 
    const result = serialize(originalRoot);
    deserialize(result);  

    notification(`🏁 <b>Deserialization complete!</b> The tree has been reconstructed.`);
}

function serialize(root) {
    startPartialBatch();
    const tree = new VisBinaryTree(root, { dataPropName: 'val' });
    const result = new VisArray();

    // Overview: what serialize will do and why
    notification(`
        🧭 <b>Serialize — Overview</b><br>
        We perform a <b>preorder traversal</b> (<b>node → left → right</b>) and record each node’s value, writing <code>#</code> for <b>null</b> children.  
        <i>Why preorder?</i> Because each node is visited <b>before</b> its children, and its <b>entire left subtree</b> is serialized 
        (completed fully) before moving to the right subtree.  
        This guarantees that in the serialized stream, every node is immediately followed by all the data needed to rebuild its left 
        and then right subtrees — making deserialization straightforward, one token at a time.  
        <i>Why record nulls?</i> Explicit <code>#</code> markers capture the tree’s <b>shape</b> as well as its values, so the serialized form 
        uniquely identifies the original tree.
    `);
    endBatch();

    function dfs(node) {
        if (!node) {
            notification(`
                🟥 ${makeColoredSpan('Null', NULL_NODE_COLOR)} at this position → write <code>#</code> to the stream.  
                <i>Why?</i> Without explicit nulls, different tree shapes could serialize to the same sequence, making
                deserialization ambiguous. The <code>#</code> preserves structure.
            `);
            result.push('#');
            return;
        }

        const vm = tree.makeVisManagerForNode(node);
        startPartialBatch();
        setCurrentNode(vm);
        notification(`
            🔵 ${makeColoredSpan('Preorder — visit current root first', CURRENT_COLOR)}: append root’s value (<b>${node.val}</b>) to the stream.  
            <i>Why?</i> Preorder always lists the <b>parent before its subtrees</b>, giving reconstruction a clear entry point for every subtree.  
            Next, we’ll traverse its <b>left subtree</b> completely before moving to the right, ensuring all left-side nodes appear first in the stream.
        `);
        result.push(node.val);
        vm.addClass(VISITED);
        endBatch();

        dfs(node.left);

        startPartialBatch();
        setCurrentNode(vm);
        notification(`
            ↪️ Finished the <b>left subtree</b> of ${makeColoredSpan('current root', CURRENT_COLOR)} with value <b>${node.val}</b>; moving to the <b>right subtree</b>.<br>
            <i>Why?</i> Preorder visits <b>node → left → right</b>, so after fully serializing the left side, we proceed to the right to preserve order in the stream.
        `);
        endBatch();

        dfs(node.right); 
    }

    dfs(root);

    notification(`
        📦 <b>Serialization complete.</b><br>
        Produced a preorder stream with <code>#</code> nulls that encodes both the tree’s <b>values</b> and its <b>structure</b>.<br>
        Returning <code>result.join(',')</code> — a comma-separated string representation of this stream.<br>
        <i>Why?</i> Joining the array into a single string provides a compact and easily transferable format that can later be
        split back into tokens (<code>data.split(',')</code>) during deserialization to rebuild the exact same tree.
    `);
    return result.join(',');
}

function deserialize(data) {
    // Overview: what deserialize will do and why
    startPartialBatch();
    const values = VisArray.from(data.split(','));
    let index = 0;
    notification(`
        🧭 <b>Deserialize — Overview</b><br>
        The input string <code>data</code> is first split by commas using <code>data.split(',')</code> to recreate the original token sequence.<br>
        We rebuild the tree by <b>consuming the preorder stream token-by-token</b> using a moving <code>index</code> pointer, 
        which starts at <code>0</code>:  
        <ul>
            <li>If the token is a <b>value</b> → create a node and then recursively build its <b>left</b> and <b>right</b> subtrees (in preorder order).</li>
            <li>If the token is <code>#</code> → return <code>null</code> to represent a missing child.</li>
        </ul>
        <i>Why?</i> Because the stream was serialized in <b>preorder with explicit nulls</b>, each token corresponds to exactly one node position, 
        ensuring there’s only one valid reconstruction.  
        The <code>index</code> acts as a <b>read pointer</b> into the token array: it starts at <code>0</code>, and each call to <code>buildTree()</code> 
        consumes exactly one token (either a value or <code>#</code>) and advances the pointer by 1.  
        As a result, we always <b>complete the entire left subtree first</b> — consuming all of its tokens — before moving to the right, 
        perfectly mirroring the original preorder traversal.
    `);
    makeVisVariable(index).registerAsIndexPointer(values, CURRENT, v => v - 1); 
    // makeVisVariable(index).registerAsIndexPointer(values, CURRENT); 
    endBatch();

    // Note that the path param is not the part of the actual algorithm it is provided just for providing a better visualization experience
    function buildTree(path='ROOT') {
        const value = values[index];
        startPartialBatch();
        index += 1;

        if (value === '#') { 
            notification(`
                🟥 Last read value is <code>#</code> → ${makeColoredSpan(`"${path}"`, NULL_NODE_COLOR)} is <b>null</b>.  
                <i>Why?</i> Explicit nulls ensure the shape is unambiguous—this position has no node.
            `);
            endBatch();
            return null; 
        }

        const node = new TreeNode(parseInt(value));
        notification(`
            🌱 Create node with last read value: <b>${value}</b> for ${makeColoredSpan(`subtree "${path}"`, CURRENT_SUBTREE_COLOR)}.  
            <i>Why?</i> In preorder, a value token denotes the <b>root</b> of the subtree; its children follow immediately in the stream.
        `);
        const tree = new VisBinaryTree(node, { dataPropName: 'val' }).options({ label: path });
        endBatch();

        // Left subtree
        notification(`
            ⬅️ <b>Build the left subtree</b> of ${makeColoredSpan(`"${path}"`, CURRENT_SUBTREE_COLOR)} by <b>recursing left</b>.  
            <i>Why?</i> The preorder contract guarantees that <b>immediately after the root token</b>, the stream contains the
            <b>entire left subtree</b> (values and <code>#</code> markers) next.  
            The recursive call will read and consume those tokens internally until the left subtree is fully constructed,
            after which the pointer will naturally sit at the start of the right subtree.
        `);
        node.left = buildTree(expandPath(path, 'L'));  

        // Right subtree
        startPartialBatch();
        setCurrentSubtree(tree);
        notification(`
            ➡️ The <b>left subtree</b> of ${makeColoredSpan(`"${path}"`, CURRENT_SUBTREE_COLOR)} is complete.  
            <b>Recurse right</b> to build its right subtree.  
            <i>Why?</i> Once the left subtree is fully constructed, the next unread token in the preorder stream
            naturally marks the start of the <b>right subtree</b>.  
            The recursive call will now read and consume those tokens in preorder,
            since the single <code>index</code> pointer always tracks progress through the stream.
        `);
        endBatch();
        node.right = buildTree(expandPath(path, 'R'));

        startPartialBatch();
        setCurrentSubtree(tree);
        notification(`
            ✅ Completed ${makeColoredSpan(`subtree "${path}"`, CURRENT_SUBTREE_COLOR)}: root <b>${value}</b> with left and right assigned.  
            <i>Why?</i> Both children were reconstructed solely by consuming the preorder stream (values and <code>#</code> markers) in sequence,  
            making this subtree’s structure and values uniquely determined—faithful to the original tree.
        `);
        endBatch();

        path !== 'ROOT' && tree.destroyVis();
        return node;
    } 

    return buildTree();
}

// --- Visual helpers ---

function expandPath(path, direction) {
    return path + '.' + direction;
}

let currentNodeVM = null;
function setCurrentNode(vm) {
    if (currentNodeVM) currentNodeVM.removeClass(CURRENT);
    vm.addClass(CURRENT);
    currentNodeVM = vm;
}

let currentSubtree;
function setCurrentSubtree(subtree) {
    if (currentSubtree === subtree) return;
    startBatch();
    currentSubtree?.visManager.removeClass(CURRENT_SUBTREE);
    subtree?.visManager.addClass(CURRENT_SUBTREE);
    currentSubtree = subtree;
    endBatch();
}

function initClassProperties() {
    setClassProperties(CURRENT, { borderColor: CURRENT_COLOR });
    setClassProperties(VISITED, { backgroundColor: VISITED_COLOR });
    setClassProperties(NULL_NODE, { backgroundColor: NULL_NODE_COLOR }); 
    setClassProperties(CURRENT_SUBTREE, { backgroundColor: CURRENT_SUBTREE_COLOR });
}

function convertInputToTree(arr) {
    if (!arr.length || arr[0] === null) return null;
    const nodes = arr.map(val => (val === null ? null : new TreeNode(val)));
    for (let i = 0; i < arr.length; i++) {
        if (nodes[i]) {
            nodes[i].left = nodes[2 * i + 1] || null;
            nodes[i].right = nodes[2 * i + 2] || null;
        }
    }
    return nodes[0];
}

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function explanationAndColorSchemaNotifications() {
  explanationNotification();
  notification(`
    <h3>🎨 Visual Cues (Color Schema)</h3>
    <ul>
      <li>${makeColoredSpan('Current node', CURRENT_COLOR)} — ${CURRENT_COLOR} border while visiting/processing in serialization.</li>
      <li>${makeColoredSpan('Visited (serialized) node', VISITED_COLOR)} — ${VISITED_COLOR} background after its value is appended to the stream.</li>
      <li>${makeColoredSpan('Null marker (#)', NULL_NODE_COLOR)} — ${NULL_NODE_COLOR} background where a child is absent (we write <code>#</code>).</li>
      <li>${makeColoredSpan('Current subtree (deserialization)', CURRENT_SUBTREE_COLOR)} — ${CURRENT_SUBTREE_COLOR} background for the subtree currently being reconstructed.</li>
    </ul>
  `);
}

Approach

We use a preorder traversal (node → left → right) with explicit null markers (#) to serialize, and a single moving index over the token stream to deserialize. This pairing guarantees a unique, unambiguous reconstruction with a simple, one-pass algorithm.

🎯 Goals

Serialization: Produce a linear stream that faithfully encodes both the node values and the tree’s shape.
Deserialization: Consume the stream token-by-token to rebuild the original tree exactly.

🧠 Why Preorder + Null Markers?

Preorder always lists the parent before its subtrees. That means every time we see a non-# token, it’s the root of the current subtree; immediately afterwards, the stream contains its entire left subtree, then its entire right subtree.
Explicit nulls (#) ensure shape is preserved. Without them, multiple different trees could serialize to the same sequence.
Together, these properties let us deserialize with a single pointer that advances once per token, consuming all of the left first and then all of the right for each subtree—no ambiguity, no re-reading.

🗂️ Serialization (DFS Preorder)

What we do: We perform a recursive DFS. At each node:

If the node is null → append # to the stream. Why? The # is a structural placeholder that prevents “phantom” nodes during reconstruction and keeps the encoding unambiguous.
If the node exists → append its value to the stream first (preorder “visit root first”). Why? Putting the root before its children gives deserialization a clear entry point for this subtree.
Then recurse left fully, then right fully. Why? Preorder’s contract guarantees the stream will contain the left subtree’s complete encoding immediately after the root, followed by the right subtree. This exact ordering is what deserialization relies on.

Wrap-up: The result is a comma-separated preorder stream containing values and # markers. It encodes both values and shape, so it can be consumed to rebuild the exact original tree.

🧩 Deserialization (Consume Stream with a Moving Index)

Setup: Split the serialized string on commas to get an array values. Maintain an integer index that starts at 0 and always points to the next token to read. Each call to buildTree():

Reads exactly one token from values[index] and then advances index by 1.

Algorithm per subtree (function buildTree(path)):

Read the next token (at values[index], then increment index).
If token is # → return null. Why? This position is an absent child; explicit nulls keep shape faithful.
Otherwise, token is a value → create a node with that value; this is the root of the current subtree.
Recurse to build the left subtree: Why? In preorder, right after the root token comes the entire left subtree (values and # markers). The recursive call consumes all its tokens internally. When it returns, the index naturally sits at the start of the right subtree.
Recurse to build the right subtree: Why? The next unread token now begins the right subtree, again in preorder.
Return the constructed node.

Important invariants & rationale:

Left fully before right: Because serialization recorded all left before any right, deserialization consumes tokens in the same order.
One-pass pointer: The single index ensures tokens are neither reused nor skipped; each recursive call consumes exactly one token on entry.

✅ Correctness & Uniqueness

Preorder puts each root before its children, so every subtree has a clear starting token.
Null markers ensure shape is encoded; there is only one tree that matches the stream.
Single moving index consumes tokens in order; left is completed before right—no ambiguity remains.

Time Complexity

O(n), where n is the number of actual nodes in the tree. Each node and its # markers for missing children are processed once during both serialization and deserialization. Why still O(n)? The number of # markers grows only at most a constant rate relative to nodes, so the total work remains linear.

Space Complexity

O(n) for the output stream, plus O(h) for the recursion stack, where h is the height of the tree (height is equal to the number of nodes in the worst case). Therefore, the overall space complexity is O(n).

Input-1

Serialize and Deserialize Binary Tree - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

🎯 Goals

🧠 Why Preorder + Null Markers?

🗂️ Serialization (DFS Preorder)

🧩 Deserialization (Consume Stream with a Moving Index)

✅ Correctness & Uniqueness

Time Complexity

Space Complexity