# Find ancestors of a given node in a Binary Tree

Posted in  Vinay Khatri
Last updated on December 7, 2023

## Find all the ancestors of a given node in a binary tree

You are given a binary tree and a node. Your task is to find all the ancestors of the given node and print the ancestors of that node. The ancestors of node N will be all those nodes that lie in the path from the root node to that given node N .

Example 1 ```Node: 8
Output: 1 3```

Explanation:

The nodes on the path from the root node to the given node 8 are 1 and 3. A path in a tree is the sequence of nodes that come along from traveling from one node to another in the tree. So, there is a unique path between the root and any other tree node. So, the path connecting the root node, i.e. 3, and the given node, i.e., 8 will be 3->1->8. Therefore, the ancestors of node 8 will be 1 and 3.

Example 2 ```Node: 7
Output: 2 5 3```

Explanation:

The nodes on the path from the root node to the given node 7 are 2, 5, and 3. The path connecting the root node, i.e. 3, and the given node, i.e., 7 will be 3->5->2->7. Therefore, the ancestors of node 7 will be 2, 5, and 3.

### Approach 1: Recursive Approach

The idea is to traverse the tree in a post-order fashion from the root node until the given node is encountered and print the nodes that are in the path. A post-order traversal is one of the methods to visit all the nodes in a tree.

As the name suggests, here, the order of traversing the nodes of the entire tree is firstly the left subtree, then it is followed by visiting all nodes of the right subtree, and at last, the root node is traversed.

So, using the postorder method to traverse all the nodes for finding the given node, we are actually first searching all the nodes in the left subtree, then in the right subtree. Therefore, if a node is not present in either of the subtrees, then we can simply say that the given node does not exist in the tree.

## Algorithm

Let us consider the given node to be N.

1. Start a post-order traversal of the tree from the root node.
2. If the root of the tree is equal to NULL, then return false, which means that N is not found in the tree.
3. If the root is equal to N, return true, which means that N is found in the tree.
4. Check the left and right subtrees recursively.
5. If N is present in either of the left subtree or the right subtree:
1. This means that root will be an ancestor to N, so print root.
2. Since node N is found in the tree, so return true.
6. If N is not present in either of the left and right subtrees, then return false.

Below is the implementation of the approach discussed above:

### CPP

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

// Structure to store binary tree having
// data with left child pointer and right child pointer.
struct Node
{
int data;
Node *left, *right;

Node(int data)
{
this->data = data;
this->left = this->right = NULL;
}
};

// Function that recursively checks the
// presence of the given node in the tree.
// Returns true and prints the ancestors if node is present,
// otherwise returns false.
bool printAncestors(Node* root, int node)
{
// base case
if (root == NULL) {
return false;
}

// if the given node is found, return true
if (root->data == node) {
return true;
}

// traverse and check if node is present in the left subtree
bool isLeft = printAncestors(root->left, node);

// traverse and check if node is present in the left subtree
bool isRight = false;
if (!isLeft) {
isRight = printAncestors(root->right, node);
}

// if either of the left or right subtrees contains
// given node, then the current node will be an ancestor
if (isLeft || isRight) {
// print the ancestor
cout << root->data << " "; } // if the node is found, returns true // else returns false return isLeft || isRight; } int main() { /* Construct the following tree 3 / \ / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4 */ Node* root = new Node(3); root->left = new Node(5);
root->right = new Node(1);
root->left->left = new Node(6);
root->left->right = new Node(2);
root->right->left = new Node(0);
root->right->right = new Node(8);
root->left->right->left = new Node(7);
root->left->right->right = new Node(4);

int node = 8;
printAncestors(root, node);

return 0;
}``````

### Output

``1 3`` ### Java

``````// Class to store binary tree having
// data with left child pointer and right child pointer.

class Node
{
int data;
Node left = null, right = null;

Node(int data) {
this.data = data;
}
}

class Main
{
// Function that recursively checks if
// given node is present in the tree or not.
// Returns true and prints the ancestors if node is present,
// otherwise returns false.

public static boolean printAncestors(Node root, int node)
{
// base case
if (root == null) {
return false;
}

// if the given node is found, return true
if (root.data == node) {
return true;
}

// traverse and check if node is present in the left subtree
boolean isLeft = printAncestors(root.left, node);

// traverse and check if node is present in the left subtree
boolean isRight = false;
if (!isLeft) {
isRight = printAncestors(root.right, node);
}

// if either of the left or right subtrees contains
// given node, then the current node will be an ancestor

if (isLeft || isRight) {
// print the ancestor
System.out.print(root.data + " ");
}

// if the node is found, returns true
// else returns false
return isLeft || isRight;
}

public static void main(String[] args)
{
/* Construct the following tree
3
/   \
/     \
5       1
/ \     / \
6   2   0   8
/ \
7   4

*/

Node root = new Node(3);
root.left = new Node(5);
root.right = new Node(1);
root.left.left = new Node(6);
root.left.right = new Node(2);
root.right.left = new Node(0);
root.right.right = new Node(8);
root.left.right.left = new Node(7);
root.left.right.right = new Node(4);

int node = 8;
printAncestors(root, node);
}
}``````

### Output

``1 3`` ### Python

``````# Class to store binary tree having
# data with left child pointer and right child pointer.
class Node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right

# that recursively checks if
# given node is present in the tree or not.
# Returns true and prints the ancestors if the node is present,
# otherwise returns false.

def printAncestors(root, node):

# base case
if root is None:
return False

# if the given node is found, return true
if root.data == node:
return True

# traverse and check if node is present in the left subtree
isLeft = printAncestors(root.left, node)

# traverse and check if node is present in the left subtree
isRight = False
if not isLeft:
isRight = printAncestors(root.right, node)

# if either of the left or right subtrees contains
# given node, then the current node will be an ancestor
if isLeft or isRight:
# print the ancestor
print(root.data, end=' ')

# if the node is found, returns true
# else returns false
return isLeft or isRight

if __name__ == '__main__':

''' Construct the following tree
3
/   \
/     \
5       1
/ \     / \
6   2   0   8
/ \
7   4
'''
root = Node(3)
root.left = Node(5)
root.right = Node(1)
root.left.left = Node(6)
root.left.right = Node(2)
root.right.left = Node(0)
root.right.right = Node(8)
root.left.right.left = Node(7)
root.left.right.right = Node(4)

node = 8
printAncestors(root, node)``````

### Output

``1 3`` ### Complexity Analysis

Time Complexity: O(n), where n is the total node. In the worst case, we will have to visit all the nodes in the tree to find the given node. So, for a tree having n nodes, the time complexity of the above approach is O(n).

Space Complexity: O(h), where h denotes the tree height due to the space utilized by the recursion stack, which could be equal to the height of the tree in the worst case.

### Approach 2: Iterative Approach

For the iterative approach, we will be using a stack data structure. We will iterate the tree in a postorder fashion and insert all the ancestor nodes in the stack, and when we reach NULL, we will print the stack.

The reason why the stack data structure will be used is so that the parent node of all the subtrees can be accessed from the top of the stack. Using the iterative approach, we will first visit the left subtree (following the postorder tree traversal method) while pushing all the nodes into the stack so that the right subtree can be accessed through these nodes using the top of the stack.

## Algorithm

Let us consider the given node to be N.

1. Start a post-order traversal of the tree from the root node.
2. First, the left subtree will be traversed while pushing the nodes into the stack.
3. If node N is found, break the loop.
4. In the stack, check if, for the node at the top, there exists a right subtree or not.
5. If the right subtree of the node at the top does not exist, then pop the top node.
6. Remove the top node; if the node popped out is the right child of the node at the top.
7. Now, if the stack is not empty, then assign the top’s right child to the root. Now, start traversal of the right subtree.
8. Finally, print the stack containing the ancestor nodes (if the stack is not empty).

The implementation of the approach discussed above is as follows:

### CPP

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

// Structure to store binary tree having
// data with left child pointer and right child pointer.
struct Node
{
int data;
struct Node *left, *right;
};

// Function to create a new node in the tree
struct Node* newNode(int data)
{
struct Node* node = (struct Node*) malloc(sizeof(struct Node));
node->data = data;
node->left = node->right = NULL;
return node;
}
// Function to iteratively print all the ancestors of the given node
void printAncestors(struct Node *root, int node)
{
if (root == NULL) return;

// stack to store the ancestor nodes
stack ancestors;

// Start traversing the tree in a post-order fashion
// break the loop when the node is found
while (1)
{

// Visit the nodes of the left subtree,
// while pushing the nodes into the stack
while (root && root->data != node)
{
// push the current node into stack
ancestors.push(root);
root = root->left;
}

// break the loop if node N is found.
if (root && root->data == node)
{
break;
}

// If the right subtree of node at top,
// does not exist,
// then pop the top node
if (ancestors.top()->right == NULL)
{
root = ancestors.top();
ancestors.pop();

// Remove the top node,
// if the node popped out is
// the right child of the node at top

while (!ancestors.empty() && ancestors.top()->right == root)
{
root = ancestors.top();
ancestors.pop();
}
}

// if the stack is not empty,
// then assign the top’s right child to root.
// start traversal of the right subtree
root = ancestors.empty()? NULL: ancestors.top()->right;
}

// print the stack containing the ancestor nodes
while (!ancestors.empty())
{
cout<<ancestors.top()->data<<" "; ancestors.pop(); } } // Driver program to test above functions int main() { /* Construct the following tree 3 / \ / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4 */ struct Node* root = newNode(3); root->left = newNode(5);
root->right = newNode(1);
root->left->left = newNode(6);
root->left->right = newNode(2);
root->right->left = newNode(0);
root->right->right = newNode(8);
root->left->right->left = newNode(7);
root->left->right->right = newNode(4);

int node = 8;
printAncestors(root, node);

return 0;
}``````

### Output

``1 3`` ### Java

``````import java.util.Stack;

class Main
{
// Class to store binary tree having
// data with left child pointer and right child pointer.
static class Node
{
int data;
Node left,right;

// constructor to create a new node in the tree
Node(int data)
{
this.data = data;
}
}

// Function to iteratively print all the ancestors of the given node
static void printAncestors(Node root,int node)
{
if(root == null)
return;

// stack to store the ancestor nodes
Stack ancestors = new Stack<>();

// Start traversing the tree in post-order fashion
// break the loop when the node is found
while(true)
{

// Traverse the left subtree,
// while pushing the nodes into the stack
while(root != null && root.data != node)
{
// push the current node into stack
ancestors.push(root);
root = root.left;
}

// break the loop if node N is found.
if(root != null && root.data == node)
{
break;
}

// If the right subtree of node at top,
// does not exist,
// then pop the top node
if(ancestors.peek().right == null)
{
root =ancestors.peek();
ancestors.pop();

// Remove the top node,
// if the node popped out is
// the right child of the node at top
while( ancestors.empty() == false && ancestors.peek().right == root)
{
root = ancestors.peek();
ancestors.pop();
}
}

// if the stack is not empty,
// then assign the top’s right child to root.
// start traversal of the right subtree
root = ancestors.empty() ? null : ancestors.peek().right;
}

// print the stack containing the ancestor nodes
while( !ancestors.empty() )
{
System.out.print(ancestors.peek().data+" ");
ancestors.pop();
}
}

// Driver program to test above functions
public static void main(String[] args)
{
/* Construct the following tree
3
/   \
/     \
5       1
/ \     / \
6   2  0   8
/ \
7   4

*/
Node root = new Node(3);
root.left = new Node(5);
root.right = new Node(1);
root.left.left = new Node(6);
root.left.right = new Node(2);
root.right.left = new Node(0);
root.right.right = new Node(8);
root.left.right.left = new Node(7);
root.left.right.right = new Node(4);

int node = 8;
printAncestors(root, node);

}

}``````

### Output

``1 3`` ### Python

``````# Class to store binary tree having
# data with left child pointer and right child pointer.
class Node:

def __init__(self, data):
self.data = data
self.left = None
self.right = None

# Function to iteratively print all
# the ancestors of the given node
def printAncestors(root, key):
if(root == None):
return;

# Create a stack to hold ancestors
ancestors = []

# Start traversing the tree in a post-order fashion
# break the loop when the node is found

while(True):

# Traverse the left subtree,
# while pushing the nodes into the stack
while(root != None and root.data != key):

# push the current node into stack
ancestors.append(root);
root = root.left

# break the loop if node N is found.
if(root != None and root.data == key):
break;

# If the right subtree of node at the top,
# does not exist,
# then pop the top node

if(ancestors[-1].right == None):
root = ancestors[-1]
ancestors.pop()

# Remove the top node,
# if the node popped out is
# the right child of the node at top
while(len(ancestors) != 0 and ancestors[-1].right == root):
root = ancestors[-1]
ancestors.pop()

# if the stack is not empty,
# then assign the top’s right child to root.
# start traversal of the right subtree
root = None if len(ancestors) == 0 else ancestors[-1].right;

# print the stack containing the ancestor nodes
while(len(ancestors) != 0):
print(ancestors[-1].data, end = " ")
ancestors.pop()

# Driver program to test above functions
if __name__=='__main__':

root = Node(3)
root.left = Node(5)
root.right = Node(1)
root.left.left = Node(6)
root.left.right = Node(2)
root.right.left = Node(0)
root.right.right = Node(8)
root.left.right.left = Node(7)
root.left.right.right = Node(4)

node = 8
printAncestors(root, node)``````

### Output

``1 3`` ### Complexity Analysis

Time Complexity: O(n), where n is the total node. In the worst case, we will have to visit all the nodes in the tree to find the given node. So, for a tree having n nodes, the time complexity of the approach discussed above is O(n).

Space Complexity: O(n), where n is the size of the tree, as the stack is being used to store all the visited nodes in the tree. So, the space complexity due to the stack storage will be equal to O(n), for a tree having a size of n.

## Wrapping Up!

In this article, we have learned an amazing concept of Binary Trees. A binary Tree is one of the most important data structures and is usually asked in the top interview questions as well. “Finding ancestral nodes of a given node” is a popular as well as a very important problem that has been asked in various interview questions.

In this article, we have skimmed about what are the ancestor nodes in Binary Trees and how we can get the ancestor nodes of a given node in a detailed as well as well-explained manner. We have included proper diagrams of trees for a better understanding of the readers.

We also learned about what post-order traversal is and how it will be beneficial over other traversals i.e., inorder traversal and preorder traversal in such kinds of problems. We also discussed two well-explained approaches along with some suitable examples to solve this problem:

• Recursive Approach
• Iterative Approach

We also covered in detail how both of the approaches work and what is the significance of both of them respectively. Discussed their time complexity as well as space complexity along with a proper explanation. Different programmers prefer different languages for coding. So we kept in mind all our readers.

That’s why this article also contains well-explained codes of both the approaches in the three most popular languages, which are c++, Java, and Python, along with their respective outputs attached to the article for a better understanding of a wide range of our readers.

We sincerely hope that this article has walked you through some deep and important concepts of Binary Trees and how we should approach such kinds of problems. We surely wish you to keep up your practice and crack all the questions easily. With this, we are wrapping up this article.

Happy Learning!