Building a tree from scratch and converting it to/from a string are classic interview problems. They test whether we truly understand how traversals work — not just how to run them, but how they encode a tree’s structure.
Why We Need Two Traversals
A single traversal doesn’t uniquely define a tree. For example, the preorder [1, 2, 3] could be a left-skewed tree, a right-skewed tree, or a balanced tree. But if we have both preorder and inorder, the tree is uniquely determined.
The key insight: preorder tells us the root, inorder tells us what’s left and right of that root.
Build Tree from Preorder + Inorder
The algorithm is recursive:
- The first element in preorder is the root.
- Find that root in inorder — everything to its left goes in the left subtree, everything to the right goes in the right subtree.
- Recurse on both halves.
function buildTree(preorder, inorder) {
if (!preorder.length) return null;
const root = new TreeNode(preorder[0]);
const mid = inorder.indexOf(preorder[0]); // root's position in inorder
root.left = buildTree(
preorder.slice(1, mid + 1), // left portion of preorder
inorder.slice(0, mid) // left portion of inorder
);
root.right = buildTree(
preorder.slice(mid + 1), // right portion of preorder
inorder.slice(mid + 1) // right portion of inorder
);
return root;
}def build_tree(preorder, inorder):
if not preorder: return None
root = TreeNode(preorder[0])
mid = inorder.index(preorder[0]) # root's position in inorder
root.left = build_tree(
preorder[1:mid + 1], # left portion of preorder
inorder[:mid] # left portion of inorder
)
root.right = build_tree(
preorder[mid + 1:], # right portion of preorder
inorder[mid + 1:] # right portion of inorder
)
return rootint preIdx = 0;
Map<Integer, Integer> inMap = new HashMap<>();
TreeNode buildTree(int[] preorder, int[] inorder) {
for (int i = 0; i < inorder.length; i++)
inMap.put(inorder[i], i); // O(1) lookup for root position
return build(preorder, 0, inorder.length - 1);
}
TreeNode build(int[] pre, int lo, int hi) {
if (lo > hi) return null;
TreeNode root = new TreeNode(pre[preIdx++]);
int mid = inMap.get(root.val);
root.left = build(pre, lo, mid - 1);
root.right = build(pre, mid + 1, hi);
return root;
}Time: O(n) with a hash map for inorder lookups (O(n^2) without). Space: O(n).
The Java version is optimized — it uses a hash map to avoid the linear indexOf call and passes indices instead of creating new arrays.
Serialization: Tree to String
Serialization means converting a tree to a string so we can store it or send it over a network. Deserialization is the reverse — building the tree back from the string.
The simplest approach uses level-order (BFS) traversal. We include null markers for missing children so we know exactly where each node belongs.
Serialize (BFS Approach)
function serialize(root) {
if (!root) return "";
const result = [], queue = [root];
while (queue.length) {
const node = queue.shift();
if (node) {
result.push(node.val);
queue.push(node.left);
queue.push(node.right);
} else {
result.push("null");
}
}
return result.join(",");
}from collections import deque
def serialize(root):
if not root: return ""
result, queue = [], deque([root])
while queue:
node = queue.popleft()
if node:
result.append(str(node.val))
queue.append(node.left)
queue.append(node.right)
else:
result.append("null")
return ",".join(result)String serialize(TreeNode root) {
if (root == null) return "";
StringBuilder sb = new StringBuilder();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node != null) {
sb.append(node.val).append(",");
queue.add(node.left);
queue.add(node.right);
} else {
sb.append("null,");
}
}
return sb.toString();
}Deserialize (BFS Approach)
We reverse the process: read values one by one, using a queue to assign children to each node in level order.
function deserialize(data) {
if (!data) return null;
const vals = data.split(",");
const root = new TreeNode(parseInt(vals[0]));
const queue = [root];
let i = 1;
while (queue.length && i < vals.length) {
const node = queue.shift();
if (vals[i] !== "null") {
node.left = new TreeNode(parseInt(vals[i]));
queue.push(node.left);
}
i++;
if (vals[i] !== "null") {
node.right = new TreeNode(parseInt(vals[i]));
queue.push(node.right);
}
i++;
}
return root;
}def deserialize(data):
if not data: return None
vals = data.split(",")
root = TreeNode(int(vals[0]))
queue, i = deque([root]), 1
while queue and i < len(vals):
node = queue.popleft()
if vals[i] != "null":
node.left = TreeNode(int(vals[i]))
queue.append(node.left)
i += 1
if vals[i] != "null":
node.right = TreeNode(int(vals[i]))
queue.append(node.right)
i += 1
return rootTreeNode deserialize(String data) {
if (data.isEmpty()) return null;
String[] vals = data.split(",");
TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int i = 1;
while (!queue.isEmpty() && i < vals.length) {
TreeNode node = queue.poll();
if (!vals[i].equals("null")) {
node.left = new TreeNode(Integer.parseInt(vals[i]));
queue.add(node.left);
}
i++;
if (!vals[i].equals("null")) {
node.right = new TreeNode(Integer.parseInt(vals[i]));
queue.add(node.right);
}
i++;
}
return root;
}Time: O(n) for both serialize and deserialize. Space: O(n) for the queue and output.
Which Traversal Pairs Work?
Not all pairs of traversals can uniquely reconstruct a tree:
| Pair | Works? | Why |
|---|---|---|
| Preorder + Inorder | Yes | Preorder gives root, inorder splits left/right |
| Postorder + Inorder | Yes | Postorder gives root (last element), inorder splits |
| Preorder + Postorder | Only for full binary trees | Can’t determine left vs right without inorder |
| Level-order + Inorder | Yes | Level-order gives root, inorder splits |
Key Takeaways
- We need two traversals (and one must be inorder) to uniquely reconstruct a binary tree.
- The recursive construction pattern: find root from preorder/postorder, split using inorder, recurse on both halves.
- Serialization with null markers lets us reconstruct from a single traversal — because the nulls encode the structure.
- BFS-based serialization is the most intuitive and commonly asked in interviews.
In simple language, constructing a tree is about figuring out “who’s the root?” and “what goes left vs right?” Serialization is just saving enough info to answer those questions later.