← Amazon questions
CodingReported in a candidate post, Jan 2010

Construct tree from ancestor matrix

Filed under Amazon

Free read 3 of 3

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

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

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.