CodingReported in a candidate post, Nov 2017
Extract leaf nodes of a tree into a Linked List
Filed under Microsoft
Free read 3 of 3Perform an in-order or pre-order traversal to identify leaf nodes.
The question
Extract all leaf nodes of a binary tree into a linked list by modifying the right pointers of the leaf nodes, maintaining left-to-right order.
Constraints
- Do not allocate extra memory (O(1) space)
- In-place modification
- Tree traversal required
Examples
- Input
- Tree: 1 -> (2, 3)
- Output
- 2 -> 3
- Why
- Leaf nodes 2 and 3 are linked via right pointers.
Approach
Perform an in-order or pre-order traversal to identify leaf nodes.
Maintain a 'prev' pointer to connect the current leaf node to the previously found leaf node.
Ensure the last leaf node's right pointer is set to null to terminate the list.
Solution
O(n) time, O(h) space (recursion stack)
class Node:
def __init__(self, val): self.val = val; self.left = self.right = None
def extract_leaves(root):
head = [None]
prev = [None]
def traverse(node):
if not node: return
if not node.left and not node.right:
if not head[0]: head[0] = node
if prev[0]: prev[0].right = node
prev[0] = node
else:
traverse(node.left)
traverse(node.right)
traverse(root)
if prev[0]: prev[0].right = None
return head[0]
Tips
- What they are testing: Test with a single node tree and a skewed tree.
- Common mistake: Losing track of the 'previous' leaf node during recursion.
Related Microsoft questions
Collected from public candidate posts and coding forums. Updated Nov 2026.