Construct and Convert
What is this?
These problems all ask you to change a tree's shape: add sibling links, rebuild it from two traversals, turn a sorted list into a balanced tree, thread it so it can be traversed without a stack, or walk its outline. 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.
Core 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) extra 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:
The lesson's problem is a perfect tree, where the connections are regular: a left child points to its sibling, and a right child points to the left child of its parent's next. The follow-up, a general tree, needs a dummy node and a moving tail pointer to handle missing children without 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.
| Traversal pair | Root is | Split found by |
|---|---|---|
| preorder + inorder | preorder[0] |
the root's position in inorder |
| inorder + postorder | postorder[-1] |
the root's position in inorder |
| preorder + postorder | preorder[0] |
the position of preorder[1] in postorder |
The third is the one in this chapter, 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 observation interviewers look for.
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 copy in Copy List with Random Pointer.
4. Where you'll actually meet this
- Deserialisation. Rebuilding a tree from flat sequences is what every deserialiser does; the traversal-pair problem is that in miniature.
- Bulk-loading an index. Building a B-tree from already sorted data can go bottom-up in sorted order, the same idea as the sorted-list conversion.
- Range scans. B+trees chain their leaf pages left to right so a scan follows a link instead of re-descending from the root, which is the next-pointer idea applied to one level.
- Constrained memory. Threaded traversal exists to avoid a stack that grows with tree height.
5. Problems in this chapter
Populating Next Right Pointers in Each Node
Link each node of a perfect tree to its right neighbour on the same level. Use the previous level's links to build the next. The general-tree follow-up uses a dummy head.
Pattern: build level k+1 by walking level k. Target: O(n) time, O(1) extra 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 and O(n) space with an index map and a moving preorder pointer (O(n²) with linear search and slicing).
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 stack.
Morris Inorder Traversal (Threaded Binary Tree)
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) extra space (an explicit stack costs O(h)).
Boundary of Binary Tree
Return the boundary anti-clockwise: root, left edge (excluding leaves), leaves left to right, 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) auxiliary space.
6. Common pitfalls
- Reaching for a queue in the next-pointer problem. It is correct but uses O(n) extra 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 and slicing to find the split. Without an index map and index ranges, 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 and the leaves that also sit on an edge are the classic duplicates, so decide once which part owns them.
- Mishandling a root with only one subtree. Only-left and only-right trees are where boundary solutions break.
7. Key takeaways
- Reuse the structure you just built. Linked levels build the next level; established order removes searching.
- Rebuilding is always "find the split". Which traversal pair you have decides how you find it.
- Preorder + postorder is ambiguous for single-child nodes, so know it and say it.
- Build in in-order sequence when the source is already sorted; the recursion supplies the balance.
- Unused null pointers are free storage, as long as you put them back.
- Partitioned walks need ownership rules so shared nodes are emitted exactly once.
- Why interviewers like it: most problems here have an obvious answer that allocates (a queue, an array copy, a stack) and a better one, so the conversation moves to whether you can exploit structure instead.
Order: Populating Next Right Pointers → Construct Binary Tree from Preorder and Postorder → Convert Sorted List to Binary Search Tree → Morris Inorder Traversal → Boundary of Binary Tree.
Morris Inorder Traversal (Threaded Binary Tree)
Core idea: A binary tree is full of wasted pointers: every leaf has two
None
children, every half-node has one. Morris traversal borrows theright = Noneslot
of each left subtree's rightmost node and points it at the node you would otherwise
need a stack to remember. That temporary link is a thread to the inorder
successor. Follow it, emit the node, then tear the thread out. No stack, no
recursion,O(1)extra space.
Problem, rephrased
A firmware module on a microcontroller must read out its configuration tree in sorted (inorder) order, and the device has a few kilobytes of RAM, so the traversal itself is not allowed to allocate. You're given the root of a binary tree, and you may use only a constant number of extra pointers: no recursion stack, no explicit stack, no parent pointers, no hash set.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson