Find ancestors of a given node in a Binary Tree

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!

People are also reading:

• Find minimum jumps required to reach the destination
• Longest subarray with sum as K
• Data Structure Interview Questions
• Construct a Binary Tree from Inorder and Preorder traversals
• Data Structure & Algorithm: Interpolation Search
• Write a C++ Program to print a Man using Graphics
• Tree Data Structure & Algorithm
• DSA: Graph- Spanning Tree
• Sort an array in one swap whose two elements are swapped
• WAP to Count no. of alphabets, digits and spaces present in a file