CodingReported in a candidate post, Jan 2010
Construct tree from ancestor matrix
Filed under Amazon
Free read 3 of 3A node 'i' is the parent of 'j' if matrix[i][j] == 1 and there is no node 'k' such that matrix[i][k] == 1 and matrix[k][j] == 1.
The question
Given an ancestor matrix where matrix[i][j] == 1 if i is an ancestor of j, reconstruct the tree structure.
Constraints
- Matrix is N x N
- Input represents a valid tree
- Nodes are 0 to N-1
Approach
A node 'i' is the parent of 'j' if matrix[i][j] == 1 and there is no node 'k' such that matrix[i][k] == 1 and matrix[k][j] == 1.
The number of ancestors for a node corresponds to its depth in the tree.
Sort nodes by their ancestor count (depth) and link each node to its direct parent.
Tips
- What they are testing: Test with a skewed tree (linked list) and a balanced tree.
- Common mistake: Confusing direct parent-child relationships with indirect ancestor relationships.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.