8

Create Binary Tree from given Array of relation between nodes

 1 year ago
source link: https://www.geeksforgeeks.org/create-binary-tree-from-given-array-of-relation-between-nodes/?utm_campaign=newhomepage
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Create Binary Tree from given Array of relation between nodes

  • Last Updated : 16 Dec, 2022

Given a 2D integer array where each row represents the relation between the nodes (relation[i] = [parenti, childi, isLefti]). The task is to construct the binary tree described by the 2D matrix and print the LevelOrder Traversal of the formed Binary Tree.

Examples:

Input: Relation[] = [[20, 15, 1], [20, 17, 0], [50, 20, 1], [50, 80, 0], [80, 19, 1]]
Output: [50, 20, 80, 15, 17, 19]
Explanation: The root node is the node with the value 50 since it has no parent.

art1-(1)drawio-300.png

Example1

Input: Relation[] = [[1, 2, 1], [2, 3, 0], [3, 4, 1]]
Output: [1, 2, 3, 4]
Explanation: The root node is the node with the value 1 since it has no parent.

art1-(1)drawio-(1)-300.png

Example 2

Approach: To solve the problem follow the below idea:

Iterate over the given 2D matrix(Relation Array) and see if the parent Node is present in the map or not.

Follow the Below steps to solve the above approach:

  • Create a map data Structure that will store the address of each of the nodes formed with their values.
  •  Iterate over the given 2D matrix(Relation Array) and see if the parentNode is present in the map or not. 
    • If the parentNode is present in the map then there is no need of making a new node, Just store the address of the parentNode in a variable. 
    • If the parentNode is not present in the map then form a parentNode of the given value and store its address in the map. (Because this parentNode can be the childNode of some other Node). 
  • Similarly, Repeat Step 2 for child Node also i.e.,
    • If the childNode is present in the map then there is no need of making a new node, Just store the address of the childNode in a variable.
    • If the childNode is not present in the map then form a childNode of the given value and store its address in the map(Because this childNode can be the parentNode of some other Node). 
  •  Form the relation between the parentNode and the childNode for each iteration depending on the value of the third value of the array of each iteration. i.e.,
    • If the third value of the array in the given iteration is 1 then it means that the childNode is the left child of the parentNode formed for the given iteration.
    • If the third value of the array in the given iteration is 0 then it means that the childNode is the left child of the parentNode formed for the given iteration.
  • If carefully observed we know that the root node is the only node that has no Parent.
  • Store all the values of the childNode that is present in the given 2D matrix (Relation Array) in a data structure (let’s assume a map data structure).
  • Again iterate the 2D matrix (RelationArray) to check which parentNode value is not present in the map data structure formed in step 5).
  • Print the level Order Traversal of the thus-formed tree.  

Below is the implementation of the above approach.

// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
// Binary Tree Node
struct Node {
int data;
Node *left, *right;
};
// Returns new Node with data as input
// to below function.
Node* newNode(int d)
{
Node* temp = new Node;
temp->data = d;
temp->left = nullptr;
temp->right = nullptr;
return temp;
}
// Function to create tree from
// given description
Node* createBinaryTree(vector<vector<int> >& descriptions)
{
unordered_map<int, Node*> mp;
for (auto it : descriptions) {
Node *parentNode, *childNode;
// Check if the parent Node is
// already formed or not
if (mp.find(it[0]) != mp.end()) {
parentNode = mp[it[0]];
}
else {
parentNode = newNode(it[0]);
mp[it[0]] = parentNode;
}
// Check if the child Node is
// already formed or not
if (mp.find(it[1]) != mp.end()) {
childNode = mp[it[1]];
}
else {
childNode = newNode(it[1]);
mp[it[1]] = childNode;
}
// Making the Edge Between parent
// and child Node
if (it[2] == 1) {
parentNode->left = childNode;
}
else {
parentNode->right = childNode;
}
}
// Store the childNode
unordered_map<int, int> storeChild;
for (auto it : descriptions) {
storeChild[it[1]] = 1;
}
// Find the root of the Tree
Node* root;
for (auto it : descriptions) {
if (storeChild.find(it[0]) == storeChild.end()) {
root = mp[it[0]];
}
}
return root;
}
// Level order Traversal
void printLevelOrder(Node* root)
{
// Base Case
if (root == nullptr) {
return;
}
// Create an empty queue for
// level order traversal
queue<Node*> q;
// Enqueue Root and initialize height
q.push(root);
while (q.empty() == false) {
// Print front of queue and
// remove it from queue
Node* node = q.front();
cout << node->data << " ";
q.pop();
// Enqueue left child
if (node->left != nullptr) {
q.push(node->left);
}
// Enqueue right child
if (node->right != nullptr) {
q.push(node->right);
}
}
}
// Driver Code
int main()
{
vector<vector<int> > RelationArray = { { 20, 15, 1 },
{ 20, 17, 0 },
{ 50, 20, 1 },
{ 50, 80, 0 },
{ 80, 19, 1 } };
Node* root = createBinaryTree(RelationArray);
printLevelOrder(root);
cout << endl;
vector<vector<int> > RelationArray2
= { { 1, 2, 1 }, { 2, 3, 0 }, { 3, 4, 1 } };
Node* root2 = createBinaryTree(RelationArray2);
printLevelOrder(root2);
return 0;
}
Output
50 20 80 15 17 19 1 2 3 4

Time Complexity: O(N) where N is the number of rows present in the 2D matrix + O(M) where M is the number of nodes present in the Tree (for Level Order Traversal)
Auxiliary Space: O(M) where M is the number of nodes present in the Tree (We are storing the values of the nodes along with their address in the map). 

Related Articles:


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK