Print Ancestors of a Given Node

Algorithm

Below is the algorithm for finding ancestors of a given node in a binary tree:

Let "p" be the pointer to the root node of a given binary tree.

• If the ‘p’ equals NULL, return false(node not found).
• If the ‘p’ equals N(where N is a node), return true(node found) .
• Recursively search ‘N’ in the left and right subtree. If any subtree contains N, then the root must be an ancestor of ‘N’.
• If neither the left subtree nor the right subtree contains ‘N’, then N is not an ancestor.

Solution

For finding the ancestor of a given node, we have written a function that checks whether the given key is on the right or left, ‘p’ represents the root node, and the function print ancestors provide us with the output required. Hence, by running these programs, we can find the ancestors of a given node in a binary tree.

C++

/*
  Print ancestors of a given node  
*/

#include<bits/stdc++.h> 
using namespace std;
/*
   A left child pointer and a right child pointer are all present in a binary tree node.
*/
 struct node1
{
   int data;
   struct node1* left;
   struct node1* right;
};

/*
  Target prints its ancestors and returns true if it is present in the tree; otherwise, it returns false. 
*/  
bool printAncestors(struct node1 *p, int target)
{
  if (p == NULL)
     return false;
 
  if (p->data == target)
     return true;
  /*
   Print this node if the target is present in either the left or right subtree.
  */
  if ( printAncestors(p->left, target) || printAncestors(p->right, target))
  {
    cout << p->data << " ";
    return true;
  }
 
  return false;
}

/*
  The helper function allocates a new node with the specified data and  NULL left and right pointers.
*/  
struct node1* newnode1(int data)
{
  struct node1* node1 = (struct node1*)
  malloc(sizeof(struct node1));
  node1->data = data;
  node1->left = NULL;
  node1->right = NULL;
 
  return(node1);
}
 
int main()
{
  struct node1 *p = newnode1(1);
  p->left = newnode1(7);
  p->right = newnode1(3);
  p->left->left = newnode1(4);
  p->left->right = newnode1(6);
  p->left->left->left = newnode1(8);
  
  int num;
  cout<<"Enter the node: ";
  cin>>num;
  cout<<"Ancestors of the node are:" ;
  printAncestors(p, num);
 
  getchar();
  return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Java

/*
  Print ancestors of a given node  
*/

import java.util.*;
/*
   A left child pointer and a right child pointer are all present in a binary tree node.
*/
class Node
{
    int data;
    Node left, right, nextRight;
  
    Node(int item)
    {
        data = item;
        left = right = nextRight = null;
    }
}
  
class Main
{
    Node p;
	/*
  		Target prints its ancestors and returns true if it is present in the tree; otherwise, it returns false.
	*/  
    boolean printAncestors(Node node, int target)
    {
         
        if (node == null)
            return false;
  
        if (node.data == target)
            return true;
  
        /*
         	Print this node if the target is present in either the left or right subtree.
        */
        if (printAncestors(node.left, target)||printAncestors(node.right, target))
        {
            System.out.print(node.data + " ");
            return true;
        }
  
        /* Else return false */
        return false;
    }
  

    public static void main(String args[])
    {
        Scanner s=new Scanner(System.in);
        Main tree = new Main();
        tree.p = new Node(1);
        tree.p.left = new Node(7);
        tree.p.right = new Node(3);
        tree.p.left.left = new Node(4);
        tree.p.left.right = new Node(6);
        tree.p.left.left.left = new Node(8);
        System.out.print("Enter the node: ");
        int num=s.nextInt();
        System.out.print("Ancestors of the node are:");
        tree.printAncestors(tree.p,num);
  
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

Python

# Print ancestors of a given node 
class Node:
    # A left child pointer and a right child pointer are all present 
    # in a binary tree node.
    def __init__(self, data,left=None,right=None):
        self.data = data
        self.left = left
        self.right = right
 
# Target prints its ancestors and returns true if it is present in the 
# tree otherwise, it returns false.
def printAncestors(root, node):
    
    if root == None:
        return False
     
    if root.data == node:
        return True
 
    # Print this node if the target is present in either the left 
    # or right subtree.
    if (printAncestors(root.left, node) or printAncestors(root.right, node)):
        print(root.data,end=' ')
        return True
 
    # Else return False
    return False
 

root = Node(1)
root.left = Node(7)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(6)
root.left.left.left = Node(8)
num = int(input("Enter the node: "))
print("Ancestors of the node are:",end="")
printAncestors(root,num)

You can also try this code with Online Python Compiler

Run Code

Output

Time Complexity

The time complexity to find the ancestors of a given node in a binary tree is O(n), in which ‘n’ represents several nodes in a binary tree. The complexity of O(n) is because we are checking each node of the binary tree to find the ancestor of a given node.

Space Complexity

O(h), where h stands for the height of the tree because the recursion stack takes up space that, in the worst case, might be equivalent to the tree's height.

Frequently Asked Questions

How to find the ancestors of a given node in a binary tree?

The idea to find the ancestors of a given node in a binary tree is to traverse the tree in a postorder manner and then search for the given node in a binary tree. The current node is its ancestor if the given node is found in the left or right subtree.

What are the ancestors of a given node in a binary tree?

The binary tree is a particular tree in which each node has two children at its max. Ancestors of a given node are said to be a node that is at the upper level of the given node.

How to check if a node is an ancestor of another node?

The easiest way to find if a node is an ancestor of another node is to climb upwards towards the root node. On the path towards the root node, every ancestor of a node can be visited and reported.

What is the ancestor and descendant of the tree?

In a tree, an ancestor node of a node is the parent of a node or the parent of some ancestors of a node. In contrast, the descendant of a node is a child of a node or child of some descendant of a node. 

Describe a binary tree.

A rooted tree with at most two children per node is called a binary tree, sometimes called a plane tree.

Conclusion

In this article, we have discussed the program to find the ancestors of a given node in a binary tree. We started with an introduction and saw the algorithm to find the ancestors of a given node in a binary tree, and then we wrote programs in different languages to find the ancestors of a given node in a binary tree. 

If you want to learn more about such topics, you can see An introduction to a Binary Tree, Learn Binary Tree, and Binary Tree. You can also visit our website, Coding Ninjas! 

Suggested problems are Check if two trees are Mirror, Construct a Binary Tree From Preorder and Postorder, Construct a Binary Tree From its Linked-List Representation, Print Nodes At Distance K From Node and many more.

You can also refer to our Guided path on Coding Ninjas Studio to upskill yourself in Data Structure and Algorithms, Competitive Programming, Javascript, and System Design.

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

Happy learning!