Find all the ancestors of a given node in a binary tree | faceprep

Program to find all the ancestors of a given node in a binary tree is discussed here. Given a binary tree and a node, the ancestors of that node is to be printed.

For example, consider the tree given below.

              15
            /   \
          12     18
         /  \    / 
        8   13  24
/ \
22 27

Nodes Ancestors

15 -
12 15
18 15
8 12,15
13 12,15
24 18,15
22 24,18,15
27 24,18,15

ancestors of a given node in a binary tree

Solution to this problem can be provided in two different ways.

Method 1: Iterative approach to print all the ancestors of a given node in a binary tree.

Method 2: Recursive approach to print all the ancestors of a given node in a binary tree.

Algorithm to find all the ancestors of a given node in a binary tree

  • Input the binary tree and the key_node whose ancestors are to be printed.
  • Traverse all the nodes of the tree and perform iterative postorder traversal.
  • Stop the traversal when the desired key_node is reached.
  • Store the ancestors of the nodes while traversing in a stack.
  • Once we reach the key_node, print the stack.

Iterative program to find all the ancestors of a given node in a binary tree is given below.

// C++ program to find all the ancestors of a given node

# include<bits/stdc++.h>
# include<stdlib.h>
using namespace std;

// Structure to create a tree
struct node
{
int data;
struct node *left;
struct node *right;
};

struct node *newNode(int data)
{
struct node *temp = (struct node *) malloc(sizeof(struct node));
temp -> data = data;
temp -> left = NULL;
temp -> right = NULL;
return temp;
};

// Iterative Function to print all ancestors of a given key
void print_ancestors(struct node *root, int key)
{
if (root == NULL) return;

// Create a stack for ancestors
stack<struct node* > st;

// Traverse the complete tree
while (1)
{
// Traverse the left side. While traversing, push the nodes into the stack
while (root && root->data != key)
{
st.push(root);
root = root->left;
}

if (root && root->data == key)
break;

// Check if right sub-tree exists for the node at top, if not then pop that node
if (st.top()->right == NULL)
{
root = st.top();
st.pop();

// If the popped node is right child of top, then remove the top
while (!st.empty() && st.top()->right == root)
{root = st.top();
st.pop();
}
}

root = st.empty()? NULL: st.top()->right;
}

// If stack is not empty, print contents of stack
while (!st.empty())
{
cout<<st.top()->data<<” “;
st.pop();
}
}

void insert_node(struct node *root, int n1, int n2, char lr)
{
if(root == NULL)
return;
if(root -> data == n1)
{
switch(lr)
{
case ‘l’ :root -> left = newNode(n2);
break;
case ‘r’ : root -> right = newNode(n2);
break;
}
}
else
{
insert_node(root -> left, n1, n2, lr);
insert_node(root -> right, n1, n2, lr);
}
}

// Function that prints the inorder traversal of the tree
void inorder(struct node *root)
{
if(root == NULL)
return;
inorder(root -> left);
cout << root -> data << ” “;
inorder(root -> right);
}

int main()
{
struct node *root = NULL;
int n;
cout << “\nEnter the number of edges : “;
cin >> n;
cout << “\nInput the tree : \n”;
while(n–)
{
char lr;
int n1,n2;
cin >> n1;
cin >> n2;
cin >> lr;
if(root == NULL)
{
root = newNode(n1);
switch(lr)
{
case ‘l’ :root -> left = newNode(n2);
break;
case ‘r’ : root -> right = newNode(n2);
break;
}
}
else
{
insert_node(root,n1,n2,lr);
}
}
cout << “\nInorder Tree Traversal : “;
inorder(root);
cout << endl;
cout << “\nEnter the node whose ancestors are to be found : “);
int key;
cin >> key;
cout <<“\nAncestors of ” << key << ” : “;
print_ancestors(root, key);

cout << endl;
return 0;
}

Algorithm to find all the ancestors of a given node in a binary tree (Recursive approach)

 

  • Input the binary tree and the key_node whose ancestors are to be printed.
  • Traverse all the nodes of the tree and perform recursive postorder traversal.
  • Until the key_node is found, traverse the left and right subtrees recursively.
  • Once the key_node is reached, return the data of the nodes in the path.

Program to find all the ancestors of a given node using recursion is given below.

// C++ program to find all the ancestors of a given node recursively

# include<bits/stdc++.h>
# include<stdlib.h>
using namespace std;

// Structure to create a tree
struct node
{
int data;
struct node *left;
struct node *right;
};

struct node *newNode(int data)
{
struct node *temp = (struct node *) malloc(sizeof(struct node));
temp -> data = data;
temp -> left = NULL;
temp -> right = NULL;
return temp;
};

void insert_node(struct node *root, int n1, int n2, char lr)
{
if(root == NULL)
return;
if(root -> data == n1)
{
switch(lr)
{
case ‘l’ :root -> left = newNode(n2);
break;
case ‘r’ : root -> right = newNode(n2);
break;
}
}
else
{
insert_node(root -> left, n1, n2, lr);
insert_node(root -> right, n1, n2, lr);
}
}

// Function that prints the inorder traversal of the tree
void inorder(struct node *root)
{
if(root == NULL)
return;
inorder(root -> left);
cout << root -> data << ” “;
inorder(root -> right);
}
/* If key_node is present in tree, then print the ancestors */
int print_ancestors(struct node *root, int target)
{
/* base cases */
if (root == NULL)
return 0;

if (root->data == target)
return 1;

/* If key_node is present in either left or right subtree of this node,
then print this node */
if ( print_ancestors(root->left, target) ||
print_ancestors(root->right, target) )
{
cout << root->data << ” “;
return 1;
}

return 0;
}

int main()
{
struct node *root = NULL;
int n;
cout << “\nEnter the number of edges : “;
cin >> n;
cout << “\nInput the tree : \n”;
while(n–)
{
char lr;
int n1,n2;
cin >> n1;
cin >> n2;
cin >> lr;
if(root == NULL)
{
root = newNode(n1);
switch(lr)
{
case ‘l’ :root -> left = newNode(n2);
break;
case ‘r’ : root -> right = newNode(n2);
break;
}
}
else
{
insert_node(root,n1,n2,lr);
}
}
cout << “\nInorder Tree Traversal : “;
inorder(root);
cout << endl;
cout << “\nEnter the node whose ancestors are to be found : “;
int key;
cin >> key;
cout <<“\nAncestors of ” << key << ” : “;
print_ancestors(root, key);

cout << endl;
return 0;
}