Tree Construction and Serialization – Introduction

Tree Construction and Serialization – Introduction

A binary tree exists in memory as a collection of nodes connected through left and right pointers. However, trees are often provided in other forms, such as:

• A level-order sequence

• Preorder and inorder traversals

• Inorder and postorder traversals

• A serialized string

• A list containing node values and NULL markers

Before performing traversal, searching, or modification, this input must be converted into an actual tree structure. This process is known as tree construction.

Similarly, when a tree must be stored in a file, transferred through a network, saved in a database, or reproduced later, its structure must first be converted into a linear representation. This process is called serialization.

The reverse operation, which recreates the original tree from its serialized representation, is called deserialization.

A correct serialization system should satisfy:

Deserialize(Serialize(Tree)) = Original Tree

The reconstructed tree does not need to contain the same node objects in memory, but it must preserve:

• Every node value

• Every parent-child relationship

• The position of each left and right child

• Every missing child

Understanding tree construction and serialization is important because trees cannot be stored or communicated directly using memory pointers.

Tree Construction

Tree construction is the process of creating nodes and connecting their left and right pointers according to the given input.

For example, consider the level-order representation:

[1, 2, 3, NULL, 4, 5, NULL]

It describes the following relationships:

• Node 1 is the root.

• Node 2 is the left child of 1.

• Node 3 is the right child of 1.

• Node 2 has no left child.

• Node 4 is the right child of 2.

• Node 5 is the left child of 3.

• Node 3 has no right child.

The construction process creates five nodes and connects them according to these positions.

Construction may be performed from:

• Level-order data

• Preorder traversal with NULL markers

• Preorder and inorder traversals

• Postorder and inorder traversals

• Parent-child relationships

• A previously serialized sequence

The construction method depends entirely on what information the input provides.

What Is Serialization?

Serialization converts a binary tree into a linear format that can be stored or transmitted.

The output may be:

• A string

• An array

• A list of tokens

• A binary sequence

• A file or database record

For example, a tree may be serialized as:

1,2,3,#,4,5,#

Here, # represents a missing node.

The format itself is not universal. Different programs may use different:

• Traversal orders

• Separators

• NULL symbols

• Number formats

• Rules for removing trailing NULL markers

The important requirement is that the deserializer must understand exactly the same format used by the serializer.

What Is Deserialization?

Deserialization converts the stored sequence back into a binary tree.

During deserialization, the algorithm:

• Reads the sequence in the expected order.

• Creates a node whenever a valid value is found.

• Creates no node when a NULL marker is found.

• Reconnects every left and right child.

• Returns the root of the reconstructed tree.

Serialization and deserialization therefore operate as a matched pair. A sequence produced by one serialization format cannot safely be decoded using a different deserialization format.

Why Are Node Values Alone Not Enough?

A traversal containing only node values may not uniquely describe the shape of a binary tree.

Consider the sequence:

[1, 2]

It could represent a tree in which node 2 is the left child of node 1.

It could also represent a tree in which node 2 is the right child of node 1.

Both trees contain the same values, but their structures are different.

Using preorder serialization with NULL markers:

• Left-child tree: 1, 2, #, #, #

• Right-child tree: 1, #, 2, #, #

The NULL markers remove the ambiguity by recording exactly which child positions are empty.

Why NULL Markers Preserve Structure

Every node in a binary tree has two possible child positions:

• Left child

• Right child

Even if a position is empty, that absence is part of the tree’s structure.

Consider this tree:

• Node 1 is the root.

• Nodes 2 and 3 are its children.

• Node 2 has only a right child 4.

• Node 3 has only a left child 5.

The missing left child of 2 and missing right child of 3 are structurally important. If those positions are ignored, the reconstructed tree may attach nodes to the wrong side.

A complete serialization format must either:

• Explicitly store missing positions using NULL markers, or

• Use another representation that allows those positions to be derived unambiguously.

Preorder DFS Serialization

One of the simplest serialization techniques uses preorder traversal:

Root → Left → Right

The important difference from an ordinary preorder traversal is that missing children are also recorded.

For the example tree, the preorder serialization is:

1, 2, #, 4, #, #, 3, 5, #, #, #

Each # represents a NULL pointer.

Algorithm

• If the current node is NULL, append the NULL marker and return because the missing position must be preserved.

• Append the current node’s value before processing its children because preorder visits the root first.

• Recursively serialize the left subtree so its complete structure follows the root.

• Recursively serialize the right subtree using the same rule.

• Separate consecutive tokens using a delimiter so that multi-digit and negative values can be parsed correctly.

• Return the completed token sequence after the entire tree has been processed.

Preorder DFS Deserialization

The preorder sequence can be reconstructed from left to right.

The next unread token always describes the next required position in the tree:

• A NULL marker means that the current position contains no node.

• A value means that a node must be created at that position.

After creating a node, its left subtree is reconstructed first, followed by its right subtree.

Algorithm

• Maintain an index pointing to the next unread token in the serialized sequence.

• Read the current token and move the index forward so every token is consumed exactly once.

• If the token is the NULL marker, return NULL because the current child position is empty.

• Otherwise, create a new node containing the token’s value.

• Recursively construct the node’s left subtree and then its right subtree because the sequence follows preorder.

• Return the newly created node as the root of the reconstructed subtree.

Dry Run of Preorder Serialization

Consider the tree described earlier.

Begin at node 1:

1

Move to its left child 2:

1, 2

Node 2 has no left child:

1, 2, #

Its right child is 4:

1, 2, #, 4

Node 4 has no children:

1, 2, #, 4, #, #

Return to node 1 and process its right child 3:

1, 2, #, 4, #, #, 3

Node 3 has left child 5:

1, 2, #, 4, #, #, 3, 5

Node 5 has no children, and node 3 has no right child:

1, 2, #, 4, #, #, 3, 5, #, #, #

This sequence records both the values and the complete structure of the tree.

Complexity of DFS Serialization

Every real node is processed once, and every missing child position is recorded once.

A binary tree containing N nodes has N + 1 NULL child pointers, so the total number of processed tokens remains proportional to N.

Serialization Time Complexity: O(N)

Deserialization Time Complexity: O(N)

Auxiliary Space Complexity: O(H) for the recursion stack, where H is the height of the tree.

The serialized result requires O(N) output space. The reconstructed tree also requires O(N) space, but that is generally treated as required output rather than auxiliary space.

For a balanced tree, H = O(log N). For a completely skewed tree, H = O(N).

Level-Order BFS Serialization

A binary tree can also be serialized using level-order traversal.

BFS processes nodes one level at a time using a queue. Whenever a real node is processed:

• Record its value.

• Add its left child position.

• Add its right child position.

If a child is missing, record a NULL marker for that position.

For the example tree, a complete level-order representation is:

1, 2, 3, #, 4, 5, #, #, #, #, #

If the format allows trailing NULL markers to be removed, the compact representation becomes:

1, 2, 3, #, 4, 5

The internal # before node 4 cannot be removed because it records that node 2 has no left child.

Algorithm

• Return the chosen empty-tree representation if the root is NULL.

• Place the root in a queue because BFS begins from the first level.

• Remove one position from the queue and append its value or the NULL marker.

• Whenever the removed position contains a real node, add both its left and right child positions to the queue.

• Continue until every required position has been processed.

• Remove trailing NULL markers only when both the serializer and deserializer explicitly support that convention.

Level-Order BFS Deserialization

BFS deserialization reconstructs children in pairs.

After creating the root, each real node removed from the queue expects:

• One token for its left child

• One token for its right child

Real children are created and added to the queue. NULL tokens leave the corresponding position empty.

Algorithm

• If the sequence is empty or begins with a NULL marker, return NULL.

• Create the root using the first token and place it in a queue.

• Remove the next parent node from the queue.

• Consume the next available token as its left child and create the child when the token is not NULL.

• Consume the following token as its right child using the same rule.

• Continue until all valid tokens have been consumed and all queued parents have been processed.

Complexity of BFS Serialization

Each node and each required child position is processed once.

Serialization Time Complexity: O(N)

Deserialization Time Complexity: O(N)

Auxiliary Space Complexity: O(W), where W is the maximum number of nodes or positions stored in the queue at one time.

In the worst case, the width of a binary tree can be proportional to N, so the worst-case auxiliary space is:

O(N)

The serialized sequence also requires O(N) output space.

DFS and BFS Serialization Comparison

Neither method is universally better. The best representation depends on how the tree will be stored, reconstructed, inspected, and processed.

Constructing a Tree from Level-Order Input

Level-order input is commonly used in coding problems because it describes the tree from top to bottom.

Example:

[1, 2, 3, NULL, 4, 5, NULL]

The construction process is:

• Create node 1 as the root.

• Place node 1 in a queue.

• Read the next two entries as the left and right children of 1.

• Place created children 2 and 3 in the queue.

• Process node 2 and read NULL and 4 as its children.

• Process node 3 and read 5 and NULL as its children.

The queue ensures that input values are assigned to parents in level order.

Algorithm

• Return NULL if the input is empty or its first entry represents a missing node.

• Create the root from the first entry and add it to a queue.

• Remove the next parent from the queue because its child positions must be filled.

• Read the next input entry as the left child and create it when it is not NULL.

• Read the following entry as the right child and create it when it is not NULL.

• Add every created child to the queue and continue until the input is exhausted.

Time Complexity: O(N)

Space Complexity: O(W), which is O(N) in the worst case.

Array Indexing and Level-Order Construction

A complete binary tree stored in an array often uses these relationships for a node at index i:

• Left child index: 2i + 1

• Right child index: 2i + 2

• Parent index: (i - 1) / 2

These formulas are useful when every position in the complete-tree layout is preserved.

However, they should not automatically be applied to every compact level-order sequence.

For example:

[1, 2, 3, NULL, 4, 5]

If the input format removes some missing positions, direct index formulas may no longer describe the intended tree. A queue-based construction should be used whenever the format assigns children only to previously created real nodes.

Always understand the input convention before choosing the construction method.

Construction from Preorder and Inorder Traversals

A binary tree can be reconstructed from its preorder and inorder traversals when node values are distinct.

Preorder follows:

Root → Left → Right

Inorder follows:

Left → Root → Right

Consider:

Preorder = [1, 2, 4, 3, 5]

Inorder = [2, 4, 1, 5, 3]

The first preorder value is 1, so 1 must be the root.

Find 1 in inorder:

[2, 4] | 1 | [5, 3]

Everything to the left of 1 belongs to the left subtree. Everything to the right belongs to the right subtree.

The same reasoning is then applied recursively to both sections.

Algorithm

• Select the next preorder value as the root because preorder always visits a subtree’s root first.

• Locate that value in the current inorder range.

• Treat the inorder elements before the root as the left subtree.

• Treat the inorder elements after the root as the right subtree.

• Recursively construct the left subtree before the right subtree to match preorder consumption.

• Return the created root after connecting both constructed subtrees.

Construction from Postorder and Inorder Traversals

Postorder follows:

Left → Right → Root

Therefore, the last value in a postorder range is the subtree’s root.

Using:

Postorder = [4, 2, 5, 3, 1]

Inorder = [2, 4, 1, 5, 3]

The last postorder value is 1, so 1 is the root.

Its position in inorder again divides the tree into:

• Left subtree: [2, 4]

• Right subtree: [5, 3]

When consuming postorder from right to left, the right subtree must generally be constructed before the left subtree because the reversed visit order becomes:

Root → Right → Left

Algorithm

• Select the last unused postorder value as the root because postorder visits a subtree’s root last.

• Find the root inside the current inorder range.

• Use the inorder portion to the right of the root for the right subtree.

• Use the inorder portion to the left of the root for the left subtree.

• When reading postorder backward, construct the right subtree before the left subtree.

• Connect both subtrees and return the created root.

Optimizing Traversal-Based Construction

A simple implementation may search the inorder array linearly every time a root is selected.

In a skewed tree, this repeated searching can produce:

O(N²) time complexity.

The search can be optimized by preprocessing the inorder traversal into a mapping:

Node value → Inorder index

Each root position can then be found in O(1) average time.

With distinct values:

Time Complexity: O(N)

Auxiliary Space Complexity: O(N) for the inorder-position mapping, plus O(H) recursion-stack space.

The constructed tree requires O(N) output space.

When Is Reconstruction Unique?

Not every traversal sequence uniquely identifies a binary tree.

A full binary tree is a tree in which every node has either zero or two children.

For arbitrary binary trees, preorder and postorder together may not reveal whether a single child belongs on the left or the right. Additional constraints are required to remove this ambiguity.

What Happens When Values Are Duplicated?

Traversal-based construction usually assumes that every node value is distinct.

If duplicates exist, a mapping such as:

value → inorder index

is no longer sufficient because the same value may appear at multiple positions.

For example:

Inorder = [2, 1, 2]

The value 2 refers to two different nodes.

Possible solutions include:

• Assigning a unique identifier to every occurrence

• Storing occurrence counts

• Maintaining all inorder positions for each value

• Defining a consistent rule for selecting occurrences

• Including additional structural information

• Using complete NULL markers in the serialized representation

Without additional information, traversal sequences containing duplicate values may describe multiple valid trees.

Serialization Format Design

A reliable format must clearly define how every token should be interpreted.

Important decisions include:

Traversal Order

The format must specify whether it uses:

• Preorder

• Postorder

• Level order

• Another custom order

NULL Representation

Common choices include:

• #

• N

• NULL

• null

The chosen marker must not be confused with a valid node value.

Delimiter

A delimiter separates consecutive values.

For example:

10,-3,#,#,25,#,#

Without a delimiter, values such as 1, 11, and 111 would be difficult to distinguish.

Empty Tree Representation

An empty tree may be represented as:

• An empty sequence

• #

• NULL

• A dedicated header value

The serializer and deserializer must use the same rule.

Data-Type Handling

The format should define how to parse:

• Negative numbers

• Multi-digit numbers

• Floating-point values

• Strings

• Special characters

• Duplicate values

If node values are strings, delimiters and special markers may need escaping or length-based encoding.

Versioning

A stored tree may be read by a newer version of the program. For long-term storage or communication between different systems, the format may include a version identifier so that future deserializers know which rules to apply.

Validating Serialized Input

A deserializer should not blindly assume that every sequence is valid.

Malformed input may contain:

• Too few tokens

• Extra unused tokens

• Invalid node values

• An invalid NULL marker

• Missing child information

• Incorrect delimiters

• Impossible traversal combinations

• Traversals of different lengths

• Different value frequencies between traversals

For example, a preorder deserializer may finish constructing a complete tree while some tokens remain unread. Those extra tokens indicate that the sequence does not match the expected format.

Similarly, if the sequence ends while a node still requires child information, the data is incomplete.

Validation is particularly important when serialized data comes from files, users, databases, or networks.

Choosing the Correct Representation

The best format depends on the problem. A coding interview may provide traversal arrays, while a storage system may require a stable and versioned serialized format.

Applications

Tree construction and serialization are used in:

• Saving trees in files or databases

• Sending trees over a network

• Cloning binary trees

• Restoring application state

• Storing abstract syntax trees

• Saving decision trees and expression trees

• Representing directory structures

• Creating test cases for tree problems

• Transferring data between different programs

• Caching previously constructed trees

• Reconstructing trees from traversal results

• Encoding and decoding hierarchical information

Common Mistakes

• Storing node values without preserving missing child positions.

• Omitting internal NULL markers from level-order serialization.

• Using different traversal orders during serialization and deserialization.

• Treating an empty tree as a normal node.

• Forgetting to define a delimiter between values.

• Removing trailing NULL markers without updating the deserialization rules.

• Applying complete-tree index formulas to a compact level-order sequence.

• Assuming a single ordinary traversal uniquely identifies a binary tree.

• Assuming preorder and postorder always produce a unique tree.

• Using a single inorder index for values that may be duplicated.

• Searching the inorder traversal repeatedly and accidentally creating an O(N²) solution.

• Constructing the left subtree first while consuming postorder from right to left.

• Failing to reset a shared traversal index between separate deserialization operations.

• Ignoring extra tokens after the tree has already been reconstructed.

• Reading beyond the sequence when serialized input is incomplete.

• Treating the serialized string as trusted input without validation.