← Microsoft questions
CodingReported in a candidate post, Nov 2017

Extract leaf nodes of a tree into a Linked List

Filed under Microsoft

Free read 3 of 3

Perform 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

  1. Perform an in-order or pre-order traversal to identify leaf nodes.

Solution

O(n) time, O(h) space (recursion stack)

Python
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.