Skip to content
Hello Python

Partition Traversal Ranges

Practice ExerciseInterviewEasyDivide and Conquer

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement partition_traversal_ranges(preorder, inorder) for unique values representing the same binary tree. Return the non-empty recursion frames [pre_left, pre_right, in_left, in_right] in root-left-right order, using half-open ranges.

Starter code

def partition_traversal_ranges(preorder, inorder):
    pass
Test cases

balanced-tree

{
  "args": [
    [
      3,
      9,
      20,
      15,
      7
    ],
    [
      9,
      3,
      15,
      20,
      7
    ]
  ]
}

Expected: [[0,5,0,5],[1,2,0,1],[2,5,2,5],[3,4,2,3],[4,5,4,5]]

single-node

{
  "args": [
    [
      1
    ],
    [
      1
    ]
  ]
}

Expected: [[0,1,0,1]]

Wizard outline
  1. Step 1: Return no empty frames

    Produce an empty frame list when preorder has no root. The recursive base case is the guard that stops every later empty subrange.

  2. Step 2: Record one root frame

    Represent the complete nonempty traversal with half-open preorder and inorder bounds. A one-node case fixes the frame format before left and right partitions are calculated.

  3. Step 3: Split recursive subranges

    Locate each root in inorder, derive left_size, and recurse over matching half-open child ranges. The root position is the proof that preorder child lengths align with inorder partitions.

Footguns and prerequisites
  • Including the inorder root in a child frame repeats the same root and prevents ranges from shrinking.
  • Using inclusive endpoints while recording half-open ranges creates off-by-one subtree sizes.
  • recursion and backtracking
Reviewed references
Prepared Interview Problems
  • Build Tree from Inorder and Postorder(opens in a new tab)

    Partition Traversal Ranges isolates each frame describes matching node sets, and the inorder root offset determines the exact left-subtree size in preorder. That focused state discipline is required when implementing build tree inorder postorder as a complete Interview Problem.

  • Build Tree from Preorder and Inorder(opens in a new tab)

    Partition Traversal Ranges isolates each frame describes matching node sets, and the inorder root offset determines the exact left-subtree size in preorder. That focused state discipline is required when implementing build tree preorder inorder as a complete Interview Problem.

  • Sorted List to Balanced BST(opens in a new tab)

    Partition Traversal Ranges isolates each frame describes matching node sets, and the inorder root offset determines the exact left-subtree size in preorder. That focused state discipline is required when implementing sorted list to bst as a complete Interview Problem.

Recommended approach and implementation

When one traversal identifies the root and another partitions left from right, index ranges avoid copying subarrays at each recursive call. Each frame describes matching node sets, and the inorder root offset determines the exact left-subtree size in preorder.

Why it works: The preorder start identifies the frame root, and its inorder position uniquely splits left and right node sets. Using the left-set size to partition preorder creates two smaller matching frames until every node is assigned.

def partition_traversal_ranges(preorder, inorder):
    positions = {value: index for index, value in enumerate(inorder)}
    frames = []
    def partition(pre_left, pre_right, in_left, in_right):
        if pre_left >= pre_right:
            return
        frames.append([pre_left, pre_right, in_left, in_right])
        root_index = positions[preorder[pre_left]]
        left_size = root_index - in_left
        partition(pre_left + 1, pre_left + 1 + left_size, in_left, root_index)
        partition(pre_left + 1 + left_size, pre_right, root_index + 1, in_right)
    partition(0, len(preorder), 0, len(inorder))
    return frames