Construct Ancestor Matrix from a Given Binary Tree

Given a Binary Tree where all values are from 0 to n-1. Construct an ancestor matrix mat[n][n]. Ancestor matrix is defined as below.

mat[i][j] = 1 if i is ancestor of j
mat[i][j] = 0, otherwise

Examples:

Input: Root of below Binary Tree.
          0
        /   
       1     2
Output: 0 1 1
        0 0 0 
        0 0 0 

Input: Root of below Binary Tree.
           5
        /    
       1      2
      /      /
     0    4  3
Output: 0 0 0 0 0 0 
        1 0 0 0 1 0 
        0 0 0 1 0 0 
        0 0 0 0 0 0 
        0 0 0 0 0 0 
        1 1 1 1 1 0

We strongly recommend you to minimize your browser and try this yourself first.

The idea is to traverse the tree. While traversing, keep track of ancestors in an array. When we visit a node, we add it to ancestor array and consider corresponding row in adjacency matrix. We mark all ancestors in its row as 1. Once a node and all its children are processed, we remove the node from ancestor array.

Below is the implementation of above idea.

C++

// C++ program to construct ancestor matrix for 
// given tree. 
#include<bits/stdc++.h> 
using namespace std; 
#define MAX 100 
  
/* A binary tree node */
struct Node 
{ 
    int data; 
    Node *left, *right; 
}; 
  
// Creating a global boolean matrix for simplicity 
bool mat[MAX][MAX]; 
  
// anc[] stores all ancestors of current node.  This 
// function fills ancestors for all nodes. 
// It also returns size of tree.  Size of tree is 
// used to print ancestor matrix. 
int ancestorMatrixRec(Node *root, vector<int> &anc) 
{ 
    /* base case */
    if (root == NULL) return 0;; 
  
    // Update all ancestors of current node 
    int data = root->data; 
    for (int i=0; i<anc.size(); i++) 
       mat[anc[i]][data] = true; 
  
    // Push data to list of ancestors 
    anc.push_back(data); 
  
    // Traverse left and right subtrees 
    int l = ancestorMatrixRec(root->left, anc); 
    int r = ancestorMatrixRec(root->right, anc); 
  
    // Remove data from list the list of ancestors 
    // as all descendants of it are processed now. 
    anc.pop_back(); 
  
    return l+r+1; 
} 
  
// This function mainly calls ancestorMatrixRec() 
void ancestorMatrix(Node *root) 
{ 
    // Create an empty ancestor array 
    vector<int> anc; 
  
    // Fill ancestor matrix and find size of 
    // tree. 
    int n = ancestorMatrixRec(root, anc); 
  
    // Print the filled values 
    for (int i=0; i<n; i++) 
    { 
        for (int j=0; j<n; j++) 
            cout << mat[i][j] << " "; 
        cout << endl; 
    } 
} 
  
/* Helper function to create a new node */
Node* newnode(int data) 
{ 
    Node* node = new Node; 
    node->data = data; 
    node->left = node->right = NULL; 
    return (node); 
} 
  
/* Driver program to test above functions*/
int main() 
{ 
    /* Construct the following binary tree 
                5 
              /   
            1      2 
          /      / 
         0    4  3    */
    Node *root        = newnode(5); 
    root->left        = newnode(1); 
    root->right       = newnode(2); 
    root->left->left  = newnode(0); 
    root->left->right = newnode(4); 
    root->right->left = newnode(3); 
  
    ancestorMatrix(root); 
  
    return 0; 
} 

/div>

Java

// Java Program to construct ancestor matrix for a given tree 
import java.util.*; 
  
class GFG 
{ 
    // ancestorMatrix function to populate the matrix of 
    public static void ancestorMatrix(Node root ,  
                                    int matrix[][],int size) 
    { 
          
        // base case: 
        if (root==null) 
        return ; 
          
        // call recursively for a preorder {left} 
        ancestorMatrix(root.left, matrix, size); 
          
        // call recursively for preorder {right} 
        ancestorMatrix(root.right, matrix, size); 
          
        // here we will reach the root node automatically 
        // try solving on pen and paper 
          
        if (root.left != null) 
        { 
            // make the current node as parent of its children node 
            matrix[root.data][root.left.data] = 1; 
              
            // iterate through all the columns of children node  
            // all nodes which are children to 
            // children of root node will also  
            // be children of root node 
            for (int i = 0; i < size; i++) 
            { 
                // if children of root node is a parent  
                // of someone (i.e 1) then make that node  
                // as children of root also 
                if (matrix[root.left.data][i] == 1) 
                matrix[root.data][i] = 1; 
            } 
        } 
          
        // same procedure followed for right node as well  
        if (root.right != null) 
        { 
            matrix[root.data][root.right.data] = 1; 
              
            for (int i = 0; i < size; i++) 
            { 
                if (matrix[root.right.data][i]==1) 
                matrix[root.data][i] = 1; 
            } 
        } 
              
          
    } 
      
    // Driver program to test the program 
    public static void main(String[] args)  
    { 
          
        // construct the binary tree as follows 
        Node tree_root = new Node(5); 
        tree_root.left = new Node (1); 
        tree_root.right = new Node(2); 
        tree_root.left.left = new Node(0); 
        tree_root.left.right = new Node(4); 
        tree_root.right.left = new Node(3); 
          
        // size of matrix  
        int size = 6; 
        int matrix [][] = new int[size][size]; 
          
        ancestorMatrix(tree_root, matrix, size); 
          
        for (int i = 0; i < size; i++) 
        { 
            for (int j = 0; j < size; j++) 
            { 
                System.out.print(matrix[i][j]+" "); 
            } 
            System.out.println(); 
        } 
    } 
      
    // node class for tree node 
    static class Node  
    { 
        public int data ; 
        public Node left ,right; 
        public Node (int data) 
        { 
            this.data = data; 
            this.left = this.right = null; 
        } 
    } 
} 
  
// This code is contributed by Sparsh Singhal 

Python3

# Python3 program to construct ancestor  
# matrix for given tree. 
  
class newnode: 
    def __init__(self, data): 
        self.data = data 
        self.left = self.right = None
          
# anc[] stores all ancestors of current node.  
# This function fills ancestors for all nodes.  
# It also returns size of tree. Size of tree   
# is used to print ancestor matrix.  
def ancestorMatrixRec(root, anc): 
    global mat, MAX
      
    # base case  
    if root == None: 
        return 0
  
    # Update all ancestors of current node  
    data = root.data 
    for i in range(len(anc)): 
        mat[anc[i]][data] = 1
  
    # Push data to list of ancestors  
    anc.append(data)  
  
    # Traverse left and right subtrees  
    l = ancestorMatrixRec(root.left, anc)  
    r = ancestorMatrixRec(root.right, anc)  
  
    # Remove data from list the list of ancestors  
    # as all descendants of it are processed now.  
    anc.pop(-1)  
  
    return l + r + 1
  
# This function mainly calls ancestorMatrixRec()  
def ancestorMatrix(root): 
      
    # Create an empty ancestor array  
    anc = [] 
  
    # Fill ancestor matrix and find  
    # size of tree.  
    n = ancestorMatrixRec(root, anc)  
  
    # Print the filled values 
    for i in range(n): 
        for j in range(n): 
            print(mat[i][j], end = " ")  
        print() 
  
# Driver Code 
MAX = 100
mat = [[0] * MAX for i in range(MAX)] 
  
# Construct the following binary tree  
#         5  
#         /   
#     1     2  
#     / /  
#     0 4 3  
root = newnode(5)  
root.left = newnode(1)  
root.right = newnode(2)  
root.left.left = newnode(0)  
root.left.right = newnode(4)  
root.right.left = newnode(3)  
  
ancestorMatrix(root) 
  
# This code is contributed by PranchalK  

C#

// C# Program to construct ancestor matrix for a given tree  
using System; 
  
class GFG  
{ 
    // ancestorMatrix function to populate the matrix of  
    public static void ancestorMatrix(Node root, 
                        int [,]matrix, int size)  
    { 
  
        // base case:  
        if (root == null)  
        { 
            return; 
        } 
  
        // call recursively for a preorder {left}  
        ancestorMatrix(root.left, matrix, size); 
  
        // call recursively for preorder {right}  
        ancestorMatrix(root.right, matrix, size); 
  
        // here we will reach the root node automatically  
        // try solving on pen and paper  
        if (root.left != null) 
        { 
            // make the current node as parent of its children node  
            matrix[root.data,root.left.data] = 1; 
  
            // iterate through all the columns of children node  
            // all nodes which are children to  
            // children of root node will also  
            // be children of root node  
            for (int i = 0; i < size; i++)  
            { 
                // if children of root node is a parent  
                // of someone (i.e 1) then make that node  
                // as children of root also  
                if (matrix[root.left.data,i] == 1)  
                { 
                    matrix[root.data,i] = 1; 
                } 
            } 
        } 
  
        // same procedure followed for right node as well  
        if (root.right != null) 
        { 
            matrix[root.data,root.right.data] = 1; 
  
            for (int i = 0; i < size; i++)  
            { 
                if (matrix[root.right.data,i] == 1)  
                { 
                    matrix[root.data,i] = 1; 
                } 
            } 
        } 
  
    } 
  
    // Driver code 
    public static void Main(String[] args) 
    { 
  
        // construct the binary tree as follows  
        Node tree_root = new Node(5); 
        tree_root.left = new Node(1); 
        tree_root.right = new Node(2); 
        tree_root.left.left = new Node(0); 
        tree_root.left.right = new Node(4); 
        tree_root.right.left = new Node(3); 
  
        // size of matrix  
        int size = 6; 
        int [,]matrix = new int[size,size]; 
  
        ancestorMatrix(tree_root, matrix, size); 
  
        for (int i = 0; i < size; i++)  
        { 
            for (int j = 0; j < size; j++)  
            { 
                Console.Write(matrix[i,j] + " "); 
            } 
            Console.WriteLine(); 
        } 
    } 
  
    // node class for tree node  
    public class Node 
    { 
  
        public int data; 
        public Node left, right; 
  
        public Node(int data)  
        { 
            this.data = data; 
            this.left = this.right = null; 
        } 
    } 
}  
  
// This code is contributed by 29AjayKumar  

Output:

0 0 0 0 0 0 
1 0 0 0 1 0 
0 0 0 1 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
1 1 1 1 1 0

Time complexity of above solution is O(n²).

How to do reverse – construct tree from ancestor matrix?
Construct tree from ancestor matrix

Construct Ancestor Matrix from a Given Binary Tree

C++

Java

Python3

C#

tags:

You Might Also Like

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books