Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Live Aptitude Training
Live Programming Training
Webinars
About Us

Edit
Reply




Edit

Finding all the ancestors of a given node in a binary tree | FACE Prep

Published on 10 Mar 2020

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 post order 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++

Output
Input - Enter the number of edges : 7 Input the tree : 15 12 l 12 8 l 12 13 r 15 18 r 18 24 r 24 22 l 24 27 r Output - Inorder Tree Traversal : 8 12 13 15 18 22 24 27 Enter the node whose ancestors are to be found : 22 Ancestors of 22 : 24 18 15


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 post order traversal.
  • Until the key_node is found, traverse the left and right sub trees 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++

Output
Input - Enter the number of edges : 7 Input the tree : 15 12 l 12 8 l 12 13 r 15 18 r 18 24 r 24 22 l 24 27 r Output - Inorder Tree Traversal : 8 12 13 15 18 22 24 27 Enter the node whose ancestors are to be found : 22 Ancestors of 22 : 24 18 15


Time complexity: O(n)


Recommended Programs




If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in
Explore 'c plus plus'
Articles Practice Exercises