Link copied to clipboard. Share away!

Dismiss

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.

- 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

- 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**

×