Given an ancestor matrix mat[n][n] where the ancestor matrix is defined as below.
mat[i][j] = 1 if i is ancestor of j mat[i][j] = 0, otherwise
Construct a Binary Tree from the given ancestor matrix where all its values of nodes are from 0 to n-1.
- It may be assumed that the input provided by the program is valid and the tree can be constructed out of it.
- Many Binary trees can be constructed from one input. The program will construct any one of them.
Examples:
Input:
{ {0, 1, 1},
{0, 0, 0},
{0, 0, 0}
};
Output:
0
/ \
1 2
Input:
{ {0, 0, 0, 1, 1, 0},
{0, 0, 0, 0, 0, 1},
{1, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0}
};
Output:
2
/ \
0 1
/ \ /
3 4 5
Please refer to this article for Bottom-Up approach: Construct tree from ancestor matrix
Approach: First, we will find the root of the tree. The root is the one whose column has all zeros. Once we find the root, we can then construct a tree from the root using DFS recursive approach.
Below is the implementation of the above approach:
C++
// C++ implementation of// the above approach#include <bits/stdc++.h>using namespace std;// Node structure for// Binary Treestruct Node { int data; Node *left, *right; Node(int _val) { data = _val; left = right = NULL; }};// Function to return// root index of a// binary treeint getRootIndex(vector<vector<int> >& arr){ int root_index = -1; for (int j = 0; j < arr[0].size(); j++) { int count = 0; for (int i = 0; i < arr.size(); i++) if (arr[i][j] == 0) { count++; } if (count == arr.size()) { root_index = j; break; } } return root_index;}// Function to print// in-order traversal of// a treevoid printInorder(Node* node){ if (node == NULL) { return; } printInorder(node->left); cout << node->data << " "; printInorder(node->right);}// Function to generate binary// tree from parent matrixNode* createTreeRec(vector<vector<int> >& arr, int index){ Node* node = new Node(index); // If left is 1 then create // left child. (for 1st one in row) // If left is 2 then create // right child.(for 1st one in row) int left = 1; for (int j = 0; j < arr[index].size(); j++) { if (arr[index][j] == 1) { // recur for left sub-tree if (left == 1) { node->left = createTreeRec(arr, j); } // recur for right sub-tree else if (left == 2) { node->right = createTreeRec(arr, j); } left++; } } return node;}// Driver codeint main(){ // Assuming leftmost 1 in a // row is left child, if exists // and rightmost 1 in a row // is right child, if exists vector<vector<int> > arr = { { 0, 0, 0, 1, 1, 0 }, { 0, 0, 0, 0, 0, 1 }, { 1, 1, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0 }, }; int root_index = getRootIndex(arr); Node* root = createTreeRec(arr, root_index); // Printing inorder traversal // of tree to check the output printInorder(root); return 0;} |
Java
// Java implementation of// the above approachimport java.io.*;public class GFG { // Node structure for // Binary Tree static class Node { int data; Node left, right; Node(int _val) { data = _val; left = right = null; } }; // Function to return // root index of a // binary tree static int getRootIndex(int[][] arr) { int root_index = -1; for (int j = 0; j < arr[0].length; j++) { int count = 0; for (int i = 0; i < arr.length; i++) if (arr[i][j] == 0) { count++; } if (count == arr.length) { root_index = j; break; } } return root_index; } // Function to print // in-order traversal of // a tree static void printInorder(Node node) { if (node == null) { return; } printInorder(node.left); System.out.print(node.data + " "); printInorder(node.right); } // Function to generate binary // tree from parent matrix static Node createTreeRec(int[][] arr, int index) { Node node = new Node(index); // If left is 1 then create // left child. (for 1st one in row) // If left is 2 then create // right child.(for 1st one in row) int left = 1; for (int j = 0; j < arr[index].length; j++) { if (arr[index][j] == 1) { // recur for left sub-tree if (left == 1) { node.left = createTreeRec(arr, j); } // recur for right sub-tree else if (left == 2) { node.right = createTreeRec(arr, j); } left++; } } return node; } // Driver code public static void main(String[] args) { // Assuming leftmost 1 in a // row is left child, if exists // and rightmost 1 in a row // is right child, if exists int[][] arr = { { 0, 0, 0, 1, 1, 0 }, { 0, 0, 0, 0, 0, 1 }, { 1, 1, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0 }, }; int root_index = getRootIndex(arr); Node root = createTreeRec(arr, root_index); // Printing inorder traversal // of tree to check the output printInorder(root); }}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of# the above approach# Node structure for# Binary Treeclass Node: def __init__(self, data): self.data = data self.left = None self.right = None# Function to return# root index of a# binary treedef getRootIndex(arr : list) -> int: root_index = -1 for j in range(len(arr)): count = 0 for i in range(len(arr)): if (arr[i][j] == 0): count += 1 if (count == len(arr)): root_index = j break return root_index# Function to print# in-order traversal of# a treedef printInorder(node : Node) -> None: if (node is None): return printInorder(node.left) print(node.data, end = " ") printInorder(node.right)# Function to generate binary# tree from parent matrixdef createTreeRec(arr : list, index : int) -> Node: node = Node(index) # If left is 1 then create # left child. (for 1st one in row) # If left is 2 then create # right child.(for 1st one in row) left = 1 for j in range(len(arr[index])): if (arr[index][j] == 1): # recur for left sub-tree if (left == 1): node.left = createTreeRec(arr, j) # recur for right sub-tree elif (left == 2): node.right = createTreeRec(arr, j) left += 1 return node# Driver codeif __name__ == "__main__": # Assuming leftmost 1 in a # row is left child, if exists # and rightmost 1 in a row # is right child, if exists arr = [[0, 0, 0, 1, 1, 0], [0, 0, 0, 0, 0, 1], [1, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]] root_index = getRootIndex(arr) root = createTreeRec(arr, root_index) # Printing inorder traversal # of tree to check the output printInorder(root)# This code is contributed by sanjeev2552 |
C#
// C# implementation of// the above approachusing System;class GFG{// Node structure for// Binary Treeclass Node{ public int data; public Node left, right; public Node(int _val) { data = _val; left = right = null; }};// Function to return// root index of a// binary treestatic int getRootIndex(int [,]arr){ int root_index = -1; for (int j = 0; j < arr.GetLength(0); j++) { int count = 0; for (int i = 0; i < arr.GetLength(1); i++) if (arr[i, j] == 0) { count++; } if (count == arr.GetLength(0)) { root_index = j; break; } } return root_index;}// Function to print// in-order traversal of// a treestatic void printInorder(Node node){ if (node == null) { return; } printInorder(node.left); Console.Write(node.data + " "); printInorder(node.right);}// Function to generate binary// tree from parent matrixstatic Node createTreeRec(int [,]arr, int index){ Node node = new Node(index); // If left is 1 then create // left child. (for 1st one in row) // If left is 2 then create // right child.(for 1st one in row) int left = 1; for (int j = 0; j < arr.GetLength(1); j++) { if (arr[index, j] == 1) { // recur for left sub-tree if (left == 1) { node.left = createTreeRec(arr, j); } // recur for right sub-tree else if (left == 2) { node.right = createTreeRec(arr, j); } left++; } } return node;}// Driver codepublic static void Main(String[] args){ // Assuming leftmost 1 in a // row is left child, if exists // and rightmost 1 in a row // is right child, if exists int[,] arr = { { 0, 0, 0, 1, 1, 0 }, { 0, 0, 0, 0, 0, 1 }, { 1, 1, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0 }, }; int root_index = getRootIndex(arr); Node root = createTreeRec(arr, root_index); // Printing inorder traversal // of tree to check the output printInorder(root);}}// This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript implementation of// the above approach// Node structure for// Binary Treeclass Node{ constructor(_val) { this.data = _val; this.left = null; this.right = null; }};// Function to return// root index of a// binary treefunction getRootIndex(arr){ var root_index = -1; for(var j = 0; j < arr.length; j++) { var count = 0; for (var i = 0; i < arr.length; i++) if (arr[i][j] == 0) { count++; } if (count == arr[0].length) { root_index = j; break; } } return root_index;}// Function to print// in-order traversal of// a treefunction printInorder(node){ if (node == null) { return; } printInorder(node.left); document.write(node.data + " "); printInorder(node.right);}// Function to generate binary// tree from parent matrixfunction createTreeRec(arr, index){ var node = new Node(index); // If left is 1 then create // left child. (for 1st one in row) // If left is 2 then create // right child.(for 1st one in row) var left = 1; for (var j = 0; j < arr.length; j++) { if (arr[index][j] == 1) { // recur for left sub-tree if (left == 1) { node.left = createTreeRec(arr, j); } // recur for right sub-tree else if (left == 2) { node.right = createTreeRec(arr, j); } left++; } } return node;}// Driver code// Assuming leftmost 1 in a// row is left child, if exists// and rightmost 1 in a row// is right child, if existsvar arr = [ [ 0, 0, 0, 1, 1, 0 ], [ 0, 0, 0, 0, 0, 1 ], [ 1, 1, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0 ]];var root_index = getRootIndex(arr);var root = createTreeRec(arr, root_index);// Printing inorder traversal// of tree to check the outputprintInorder(root);</script> |
Output:
3 0 4 2 5 1
Time Complexity: O(N2), where N is the size of the binary tree.
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
