Explore
Placement Prep

Edit

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



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