FastPrepFlatten and Reconstruct an Ordered Tree
Problems/Flatten and Reconstruct an Ordered Tree

Flatten and Reconstruct an Ordered Tree

The Walt Disney Company logoThe Walt Disney Company● MediumFULLTIMEONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The onsite report describes flattening a tree variant and a bonus task to reconstruct the tree from the first task’s output. It does not define arity, child order, traversal, flat structural markers or node identity. This practice consolidates both directions for an ordered arbitrary-arity tree, using parent/value input records and preorder value/child-count encoding. Decoding preserves structure, values and sibling order while assigning new preorder row numbers; it does not recover original serialization IDs. Empty trees, duplicates and a 200-node bound are supplied practice conventions. About 65% of the reported task scope is represented, as an editorial estimate rather than recovered original detail.

Flatten an ordered tree into a structure-preserving sequence, or reconstruct the tree from that sequence. The tree may have any number of children per node and may contain duplicate values.

For this exercise, mode=0 encodes a tree. Input row i is [parentIndex,value]. The root has parent -1; a parent may appear before or after its child in the input. Children of each parent are ordered by increasing input row index. Return preorder rows [value,childCount], visiting a node before its children from first to last.

mode=1 decodes a valid preorder sequence of [value,childCount] rows. Return [parentIndex,value] records in preorder, using the output row indices as the new node numbers and -1 for the root. Preserve every node value, child relationship and sibling order. Original row numbers are serialization identifiers and are not recovered; reconstruction assigns new preorder numbers.

An empty tree is represented by an empty array in either direction. This ordered-tree model, traversal, child-count format and numbering rule are practice choices for the reported flatten-and-reconstruct pair.

Function

orderedTreeCodec(mode: int, records: int[][]) → int[][]

Examples

Example 1

mode = 0records = [[2,20],[2,30],[-1,10],[0,40]]return = [[10,2],[20,1],[40,0],[30,0]]

Input row 2 is root 10, whose children are rows 0 and 1 in that order. Node 20 has child 40. Preorder is 10,20,40,30, giving [[10,2],[20,1],[40,0],[30,0]].

Example 2

mode = 1records = [[7,2],[7,0],[9,1],[7,0]]return = [[-1,7],[0,7],[0,9],[2,7]]

The first 7 is the root. Its first child is a leaf 7; its second child is 9 with one leaf 7. New preorder indices yield [[-1,7],[0,7],[0,9],[2,7]]. Repeated values remain separate nodes.

Constraints

  • 0 <= mode <= 1
  • 0 <= records.length <= 200
  • records[i].length == 2
  • -1000000 <= records[i][j] <= 1000000
  • For mode 0, nonempty records form one valid rooted tree: one parent -1, every other parent is a valid row index, and every node reaches the root without a cycle.
  • For mode 1, nonempty records are a valid preorder encoding of exactly one tree, with nonnegative child counts less than records.length.

More The Walt Disney Company problems

  • Find All Paths for a Name in a File SystemPHONE SCREEN · Seen Nov 2026
  • Resizable Array-Backed Integer SetPHONE SCREEN · Seen Sep 2026
  • Shortest Path with Directional Move CostsPHONE SCREEN · Seen Sep 2026
All The Walt Disney Company interview questionsSee The Walt Disney Company hiring insights
Saved
class Solution {
    public int[][] orderedTreeCodec(int mode, int[][] records) {
        // Write your code here
    }
}
Checking account…