Construct and Convert

What is this?

These problems all ask you to change a tree's shape — add sibling links, rebuild it from a serialised form, turn a sorted list into a balanced tree, or thread it so it can be traversed without a stack. The recurring move is that the structure you have already built is itself a tool. Level k's next pointers let you walk level k to build level k+1's. A traversal's ordering tells you where the split between subtrees must fall. An unused null pointer can hold a shortcut back to where you came from.

💡 Fun fact: Convert Sorted List to Binary Search Tree has a solution that feels backwards and is far better than the obvious one. Rather than finding the middle of the list — O(n log n) with repeated traversals — you build the tree in in-order sequence, recursing left first, consuming one list node as the current root, then recursing right. The list pointer marches forward exactly once, so the whole conversion is O(n). You never search for a midpoint; you let the recursion's shape do it.

🔓 The 5 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: to build structure cheaply, use structure you already have — established pointers, traversal ordering, or the null links a tree is not using — instead of allocating a queue, a map, or a second pass.

1. Use the level you just linked

Populating Next Right Pointers is usually solved with BFS and a queue, which is O(n) space. But once level k is fully linked, you can walk it left to right using those very next pointers and stitch level k+1 as you go — a dummy head makes the stitching uniform:

level k already linked:   A → B → C → nil
walk it, and for each node connect its children in order:
                          A.left → A.right → B.left → B.right → C.left → ...
result: level k+1 is linked, using O(1) extra space

For a perfect tree the connections are regular. For the general version, a dummy node and a moving tail pointer handle missing children without any special cases.

2. Locate the split

Rebuilding a tree from two traversals is always the same question: where does the left subtree end? Each traversal pair answers it differently.

The third is the one here, and it comes with a caveat worth stating unprompted: preorder plus postorder does not determine a unique tree. A node with a single child is ambiguous — nothing distinguishes a lone left child from a lone right one. Any valid answer is accepted, and knowing why is the senior observation.

3. Borrow the null pointers

Morris traversal walks a tree in O(1) space by temporarily pointing a subtree's rightmost node back at the current node — a link the tree was not using. When the walk returns, that thread is found again, removed, and the traversal continues. The tree ends exactly as it began. It is the same "restructure then restore" instinct as the interleaved list copy.

4. Where you'll actually meet this

• Serialisation formats. Reconstructing a tree from a flat representation is what every deserialiser does; the traversal-pair problems are that in miniature.
• Database index construction. Bulk-loading a B-tree from sorted data builds bottom-up in sorted order, the same idea as the sorted-list conversion.
• Embedded and constrained runtimes. Threaded traversal exists because recursion stacks were once unaffordable — and still are in some firmware.
• UI and DOM manipulation. Adding sibling pointers to a hierarchy to make traversal cheaper is a standard optimisation.
• Compilers. AST transformations rewire nodes in place rather than rebuilding, for exactly the reasons here.

5. Problems in this chapter

▶ Populating Next Right Pointers in Each Node

Link each node to its right neighbour on the same level. Use the previous level's links to build the next; a dummy head keeps the general case clean.
Pattern: build level k+1 by walking level k. Target: O(n) time, O(1) space.

▶ Construct Binary Tree from Preorder and Postorder

Rebuild a tree from those two traversals. Locate preorder[1] in postorder to size the left subtree; note the answer is not unique.
Pattern: locate the split, recurse. Target: O(n) time with an index map.

▶ Convert Sorted List to Binary Search Tree

Turn a sorted linked list into a height-balanced BST. Build in in-order sequence, consuming the list one node at a time.
Pattern: in-order construction driven by a moving pointer. Target: O(n) time, O(log n) recursion.

▶ Threaded Binary Tree (Morris Traversal)

Traverse in order with O(1) extra space by parking return links in unused null pointers, then removing them.
Pattern: restructure and restore. Target: O(n) time, O(1) space.

▶ Boundary of Binary Tree

Print the boundary anti-clockwise: left edge, leaves, right edge reversed. Three careful walks with strict rules about which node belongs to which part.
Pattern: partitioned traversal with de-duplication. Target: O(n) time, O(h) space.

6. Common pitfalls 🚫

• Reaching for a queue in the next-pointer problem. It is correct and O(n) space; the point of the exercise is the O(1) version.
• Searching the list for its middle in the sorted-list conversion. That is O(n log n); in-order construction is O(n).
• Claiming preorder + postorder is unique. It is not, and saying so unprompted is a strong signal.
• Linear scans to find the split. Without an index map, rebuilding is O(n²).
• Leaving Morris threads in place. The tree must be restored exactly; a stray thread turns it into a cyclic structure.
• Double-counting corners in the boundary walk. The root, the leftmost leaf and the rightmost leaf are the classic duplicates — decide once which part owns them.
• Treating a single-child root as having both boundaries. Degenerate trees are where boundary solutions break.

7. Key takeaways

1. Reuse the structure you just built. Linked levels build the next level; established order removes searching.
2. Rebuilding is always "find the split". Which traversal pair you have decides how you find it.
3. Preorder + postorder is ambiguous for single-child nodes — know it and say it.
4. Build in in-order sequence when the source is already sorted; the recursion supplies the balance.
5. Unused null pointers are free storage, as long as you put them back.
6. Partitioned walks need ownership rules so shared nodes are emitted exactly once.
7. Why interviewers like it: every problem here has an obvious O(n)-space answer and a better one, so the conversation naturally moves to whether you can exploit structure instead of allocating.

Order: Populating Next Right Pointers → Construct Binary Tree from Preorder and Postorder → Convert Sorted List to Binary Search Tree → Threaded Binary Tree → Boundary of Binary Tree.