Prepin
Log in

L

Build a Binary Tree using an Ancestor Matrix.

Approach / Explanation

This question necessitates a deep understanding of binary trees and 2D matrices. The objective is to build a binary tree from a specified ancestor matrix. An ancestor matrix is a binary matrix that indicates whether one node is an ancestor of another within a binary tree. If AncestorMatrix[i][j] equals 1, it signifies that node i is an ancestor of node j. To grasp the question fully, you should be familiar with the characteristics and manipulation of both binary trees and 2D matrices. Additionally, you should be capable of relating the structure of the tree to the matrix and constructing a binary tree accordingly. An effective strategy for tackling this problem involves: Identifying the root of the binary tree, which will be a node that has no ancestors. Building the tree based on the following guidelines: Every node (aside from the root) must have a single parent. A node can be designated as the left child of another node only if all nodes in the trees rooted at the nodes filled up to the i-th row (nodes in the ancestor matrix filled up to the i-th row) do not include the node in their right subtree. A node can be designated as the right child of another node only if all nodes in the trees rooted at the nodes filled up to the i-th row (nodes in the ancestor matrix filled up to the i-th row) do not include the node in their left subtree.

Suggested Answer

Based on the ancestor matrix provided: 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 The resulting binary tree will be: 1 / \ 0 2 \ 3 In this scenario, node 1 serves as the root because it has no ancestors. The other nodes act as child nodes. Node 0 can correspond to both the 1st and 4th nodes but can only be connected as a left child to the 1st node. Node 2 can be the right child of the root, while node 3 can be the right child of node 2.

Alternative Answer

Based on the ancestor matrix provided: 0 0 0 0 0 0 1 1 0 The resulting binary tree will be: 2 / \ 0 1 Here, node 2 serves as the root because it has no ancestors. The other nodes, 0 and 1, act as child nodes, positioned as the left and right children of the root, respectively. The structure of the tree accurately reflects the original matrix.

Question Details

Difficulty & Category

Medium
data structures

Companies

LinkedIn

Product

AI Candidate AgentCompaniesBrowse JobsDeep ProfileSkill AssessmentOpportunity Matching
Prepin.ai

© 2026 Prepin | All rights reserved.