Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Description
2.
Algorithm Explanation
2.1.
C++ Binary Tree Node Representation
2.2.
The main Function
2.2.1.
C++ Implementation
2.3.
Python Binary TreeNode Representation
2.3.1.
Python Implementation
2.4.
Time Complexity and Space Complexity
3.
Frequently Asked Questions
3.1.
Define the ancestor of a binary tree?
3.2.
Can a node be an ancestor of itself?
3.3.
Are trees also graphs?
3.4.
Can a binary tree have only one child?
3.5.
What is a sibling in a binary tree?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

Construct an Ancestor Matrix from the given Binary Tree

Author Ankit Mishra
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Description

Construct an N×N ancestor matrix using a binary tree with nodes labelled from 0 to N-1. An ancestor matrix is a boolean matrix in which the cell (i, j) is true if i is a binary tree ancestor of j in a given binary tree. For more intuition of the question, kindly take reference from the below example as shown.

Example: 

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

Let's Discuss the method to approach this problem from an interview perspective.

Algorithm Explanation

The intention is to traverse through the tree and Keep track of the ancestors in an array when traversing the tree. When we visit a node, we add it to the ancestor array and consider the row in the adjacency matrix that corresponds to it. All ancestors in that row are given the number one(1). We delete a node from the ancestor array once it has been processed with all of its children.

Let’s look at the implementation of the above approach.

C++ Binary Tree Node Representation

struct TreeNode
{
   int data;
   TreeNode *left, *right;
};

The main Function

C++ Implementation

#include <bits/stdc++.h>
using namespace std;
#define VAR 100

// Global boolean matrix for ease
// To ensure all variables are working smoothly and make dry run easy, all variables are explained below.
// ancestors[] stores all ancestors of current node.
// function fills ancestors for all nodes.
// It also returns size of tree.  Size of tree is
// used to print ancestor matrix.
bool matrix[VAR][VAR];
int ancestor_Matrix_from_BT_helper(TreeNode *root, vector<int> &anc)
{
   /* base case for this rec func */
   if (root == NULL)
       return 0;
   ;


   // Update all the ancestors of current node
   int data = root->data;
   for (int i = 0; i < anc.size(); i++)
       matrix[anc[i]][data] = true;


   // Push data to the list of ancestors
   anc.push_back(data);


   // Traverse left and right of the subtrees
   int l = ancestor_Matrix_from_BT_helper(root->left, anc);
   int r = ancestor_Matrix_from_BT_helper(root->right, anc);


   // Remove data from the list of ancestors
   // as all descendants of it are processed now.
   anc.pop_back();


   return l + r + 1;
}


// This helper function to call ancestor_Matrix_from_BT_helper()
void ancestor_Matrix_from_BT(TreeNode *root)
{
   // Creating a empty ancestor array
   vector<int> ancestors;


   // Fill the ancestor matrix and find size of
   // tree.
   int n = ancestor_Matrix_from_BT_helper(root, ancestors);


   // Print the filled values
   for (int i = 0; i < n; i++)
   {
       for (int j = 0; j < n; j++)
           cout << matrix[i][j] << " ";
       cout << endl;
   }
}


/* Helper function will create a new node */
TreeNode *newnode(int data)
{
   TreeNode *node = new TreeNode;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}


/* Driver program*/
int main()
{
   /* Construct the following binary tree
            4
          /   \
         3     1
        / \     \
       2   0     5
  */
   TreeNode *root = newnode(4);
   root->left = newnode(3);
   root->right = newnode(1);
   root->left->left = newnode(2);
   root->left->right = newnode(0);
   root->right->left = newnode(5);


   ancestor_Matrix_from_BT(root);


   return 0;
}

 

Output:

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

Python Binary TreeNode Representation

class newnode:
   def __init__(self, data):
       self.data = data
       self.left = self.right = None

Python Implementation

def length_of(root):
   # base case
   if root is None:
       return 0

   return length_of(root.left) + 1 + length_of(root.right)


# Traverse the given tree in a preorder fashion and keep updating the ancestors of
of# all nodes in the ancestor matrix which we declared
def constructAncestorMatrix(root, ancestors, ancestorMatrix):

   # base case for the recursive function
   if root is None:
       return

   # updating all the ancestors of the current node
   for node in ancestors:
       ancestorMatrix[node.data][root.data] = 1

   # adding the current node on to the set of ancestors
   ancestors.add(root)

   # recursion for the left and right subtree of the provided tree
   constructAncestorMatrix(root.left, ancestors, ancestorMatrix)
   constructAncestorMatrix(root.right, ancestors, ancestorMatrix)

   # removing the current node from all the set of ancestors since all
the descendants of the current node are already processed
   ancestors.remove(root)


# Function to construct the ancestor matrix from provided binary tree
def Helper(root):

   # calculate the length_of of the binary tree
   n = length_of(root)

   # creating an ancestor matrix of length N*N , initialized at zero
   ancestorMatrix = [[0 for x in range(n)] for y in range(n)]

   # storing all the ancestors of a node
   ancestors = set()

   # Construction the ancestor matrix
   constructAncestorMatrix(root, ancestors, ancestorMatrix)

   return ancestorMatrix


if __name__ == '__main__':

   ''' Construct the following tree
             4
          /   \
         3     1
        / \     \
       2   0     5
   '''

   root = Node(4)
   root.left = Node(3)
   root.right = Node(1)
   root.left.left = Node(2)
   root.left.right = Node(0)
   root.right.right = Node(5)
   ancestorMatrix = Helper(root)
   #To show the Matrix
   for row in ancestorMatrix:
       print(row)

 

Output:

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

Time Complexity and Space Complexity

Time complexity: O(N) 
O(N) for accessing left and right node in helper function and another O(N) for utility function to call a helper function
Space Complexity O(N2

O(N2) for storing the ancestors in a 2D matrix, where N is the size of the binary tree.

Check out this problem - Diameter Of Binary Tree

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

Define the ancestor of a binary tree?

The ancestor of a node in a binary tree is a node that is at the upper level of the given node.

Can a node be an ancestor of itself?

Every node is an ancestor of itself. A proper ancestor of n is any node y such that node y is an ancestor of node n and y is not the same node as n. Any node y for which n is an ancestor of y. Every node is a descendent of itself.

Are trees also graphs?

A tree is a graph, but a graph is not always a tree. Directed and undirected graphs are the two types of graphs: The edges of a directed graph are arrows (directed from one node to another), whereas the edges of an undirected graph are plain lines (they have no direction).

Can a binary tree have only one child?

A binary tree is a variety of trees, in which each node has not more than two children and each kid is either a left or right child, even if it is the parent's only child. A full binary tree is one with two children for each internal node.

What is a sibling in a binary tree?

Nodes that belong to the same parent are called siblings. In other words, nodes with the same parent are sibling nodes.

Conclusion

In this article, we have extensively discussed the question based on Binary Tree and the CPP and Python code, along with the Time complexity and Space Complexity.

After reading about this question, are you not feeling excited to read/explore more articles on the topic of Binary Tree? Don't worry; Coding Ninjas has you covered. To learn, See  Binary Tree TutorialIntroduction to Binary Tree-Blog, and BST.

 

Recommended problems -

 

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enrol in our courses, refer to the mock test and problems; look at the interview experiences and interview bundle for placement preparations. Check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look

at the problems, interview experiences and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Perfect Binary Tree Specific Level Order Traversal
Next article
Diagonal Sum of a Binary Tree
Live masterclass