Open In App

Print ancestors of a given binary tree node without recursion

Last Updated : 14 Dec, 2022
Improve
Improve
Like Article
Like
Save
Share
Report

Given a Binary Tree and a key, write a function that prints all the ancestors of the key in the given binary tree.
For example, consider the following Binary Tree 

            1
        /       \
       2         3
     /   \     /   \
    4     5    6    7 
   /       \       /
  8         9     10  

Following are different input keys and their ancestors in the above tree

Input Key    List of Ancestors 
-------------------------
 1            
 2            1
 3            1
 4            2 1
 5            2 1
 6            3 1
 7            3 1
 8            4 2 1
 9            5 2 1
10            7 3 1

A recursive solution for this problem is discussed here

It is clear that we need to use a stack-based iterative traversal of the Binary Tree. The idea is to have all ancestors in the stack when we reach the node with the given key. Once we reach the key, all we have to do is print the contents of the stack. 

How to get all ancestors in the stack when we reach the given node? We can traverse all nodes in a Postorder way. If we take a closer look at the recursive postorder traversal, we can easily observe that, when the recursive function is called for a node, the recursion call stack contains ancestors of the node. So the idea is to do iterative Postorder traversal and stop the traversal when we reach the desired node. 
Following is the implementation of the above approach. 
Implementation:

C




// C program to print all ancestors of a given key
#include <stdio.h>
#include <stdlib.h>
 
// Maximum stack size
#define MAX_SIZE 100
 
// Structure for a tree node
struct Node
{
    int data;
    struct Node *left, *right;
};
 
// Structure for Stack
struct Stack
{
    int size;
    int top;
    struct Node* *array;
};
 
// A utility function to create a new tree node
struct Node* newNode(int data)
{
    struct Node* node = (struct Node*) malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
 
// A utility function to create a stack of given size
struct Stack* createStack(int size)
{
    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
    stack->size = size;
    stack->top = -1;
    stack->array = (struct Node**) malloc(stack->size * sizeof(struct Node*));
    return stack;
}
 
// BASIC OPERATIONS OF STACK
int isFull(struct Stack* stack)
{
    return ((stack->top + 1) == stack->size);
}
int isEmpty(struct Stack* stack)
{
    return stack->top == -1;
}
void push(struct Stack* stack, struct Node* node)
{
    if (isFull(stack))
        return;
    stack->array[++stack->top] = node;
}
struct Node* pop(struct Stack* stack)
{
    if (isEmpty(stack))
        return NULL;
    return stack->array[stack->top--];
}
struct Node* peek(struct Stack* stack)
{
    if (isEmpty(stack))
        return NULL;
    return stack->array[stack->top];
}
 
// Iterative Function to print all ancestors of a given key
void printAncestors(struct Node *root, int key)
{
    if (root == NULL) return;
 
    // Create a stack to hold ancestors
    struct Stack* stack = createStack(MAX_SIZE);
 
    // Traverse the complete tree in postorder way till we find the key
    while (1)
    {
        // Traverse the left side. While traversing, push the nodes into
        // the stack so that their right subtrees can be traversed later
        while (root && root->data != key)
        {
            push(stack, root);   // push current node
            root = root->left;  // move to next node
        }
 
        // If the node whose ancestors are to be printed is found,
        // then break the while loop.
        if (root && root->data == key)
            break;
 
        // Check if right sub-tree exists for the node at top
        // If not then pop that node because we don't need this
        // node any more.
        if (peek(stack)->right == NULL)
        {
            root = pop(stack);
 
            // If the popped node is right child of top, then remove the top
            // as well. Left child of the top must have processed before.
            // Consider the following tree for example and key = 3.  If we
            // remove the following loop, the program will go in an
            // infinite loop after reaching 5.
            //          1
            //        /   \
            //       2     3
            //         \
            //           4
            //             \
            //              5
            while (!isEmpty(stack) && peek(stack)->right == root)
               root = pop(stack);
        }
 
        // if stack is not empty then simply set the root as right child
        // of top and start traversing right sub-tree.
        root = isEmpty(stack)? NULL: peek(stack)->right;
    }
 
    // If stack is not empty, print contents of stack
    // Here assumption is that the key is there in tree
    while (!isEmpty(stack))
        printf("%d ", pop(stack)->data);
}
 
// Driver program to test above functions
int main()
{
    // Let us construct a binary tree
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->left->left->left = newNode(8);
    root->left->right->right = newNode(9);
    root->right->right->left = newNode(10);
 
    printf("Following are all keys and their ancestors\n");
    for (int key = 1; key <= 10; key++)
    {
        printf("%d: ", key);
        printAncestors(root, key);
        printf("\n");
    }
 
    getchar();
    return 0;
}


C++




// C++ program to print all ancestors of a given key
#include <bits/stdc++.h>
using namespace std;
 
 
// Structure for a tree node
struct Node
{
    int data;
    struct Node *left, *right;
};
 
// A utility function to create a new tree node
struct Node* newNode(int data)
{
    struct Node* node = (struct Node*) malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
 
// Iterative Function to print all ancestors of a given key
void printAncestors(struct Node *root, int key)
{
    if (root == NULL) return;
 
    // Create a stack to hold ancestors
    stack<struct Node* > st;
 
    // Traverse the complete tree in postorder way till we find the key
    while (1)
    {
        // Traverse the left side. While traversing, push the nodes into
        // the stack so that their right subtrees can be traversed later
        while (root && root->data != key)
        {
            st.push(root);   // push current node
            root = root->left;  // move to next node
        }
 
        // If the node whose ancestors are to be printed is found,
        // then break the while loop.
        if (root && root->data == key)
            break;
 
        // Check if right sub-tree exists for the node at top
        // If not then pop that node because we don't need this
        // node any more.
        if (st.top()->right == NULL)
        {
            root = st.top();
            st.pop();
 
            // If the popped node is right child of top, then remove the top
            // as well. Left child of the top must have processed before.
 
            while (!st.empty() && st.top()->right == root)
               {root = st.top();
               st.pop();
               }
        }
 
        // if stack is not empty then simply set the root as right child
        // of top and start traversing right sub-tree.
        root = st.empty()? NULL: st.top()->right;
    }
 
    // If stack is not empty, print contents of stack
    // Here assumption is that the key is there in tree
    while (!st.empty())
    {
        cout<<st.top()->data<<" ";
        st.pop();
    }
}
 
// Driver program to test above functions
int main()
{
    // Let us construct a binary tree
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->left->left->left = newNode(8);
    root->left->right->right = newNode(9);
    root->right->right->left = newNode(10);
 
    cout<<"Following are all keys and their ancestors"<<endl;
    for (int key = 1; key <= 10; key++)
    {
        cout<<key<<":"<<" ";
        printAncestors(root, key);
        cout<<endl;
    }
 
    return 0;
}
// This code is contributed by Gautam Singh


Java




// Java program to print all ancestors of a given key
import java.util.Stack;
 
public class GFG
{
    // Class for a tree node
    static class Node
    {
        int data;
        Node left,right;
         
        // constructor to create Node
        // left and right are by default null
        Node(int data)
        {
            this.data = data;
        }
    }
     
    // Iterative Function to print all ancestors of a given key
    static void printAncestors(Node root,int key)
    {
        if(root == null)
            return;
         
         // Create a stack to hold ancestors
        Stack<Node> st = new Stack<>();
         
        // Traverse the complete tree in postorder way till we find the key
        while(true)
        {
             
            // Traverse the left side. While traversing, push the nodes into
            // the stack so that their right subtrees can be traversed later
            while(root != null && root.data != key)
            {
                st.push(root);   // push current node
                root = root.left;   // move to next node
            }
             
            // If the node whose ancestors are to be printed is found,
            // then break the while loop.
            if(root != null && root.data == key)
                break;
             
            // Check if right sub-tree exists for the node at top
            // If not then pop that node because we don't need this
            // node any more.
            if(st.peek().right == null)
            {
                root =st.peek();
                st.pop();
                 
                // If the popped node is right child of top, then remove the top
                // as well. Left child of the top must have processed before.
                while( st.empty() == false && st.peek().right == root)
                {
                    root = st.peek();
                    st.pop();
                }
            }
             
            // if stack is not empty then simply set the root as right child
            // of top and start traversing right sub-tree.
            root = st.empty() ? null : st.peek().right;
        }
         
        // If stack is not empty, print contents of stack
        // Here assumption is that the key is there in tree
        while( !st.empty() )
        {
            System.out.print(st.peek().data+" ");
            st.pop();
        }
    }
     
    // Driver program to test above functions
    public static void main(String[] args)
    {
         // Let us construct a binary tree
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.left.left.left = new Node(8);
        root.left.right.right = new Node(9);
        root.right.right.left = new Node(10);
         
        System.out.println("Following are all keys and their ancestors");
        for(int key = 1;key <= 10;key++)
        {
            System.out.print(key+": ");
            printAncestors(root, key);
            System.out.println();
        }
    }
 
}
//This code is Contributed by Sumit Ghosh


Python3




# Python3 program to print all ancestors of a given key
 
# Class for a tree node
class Node:
 
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Iterative Function to print all ancestors of a given key
def printAncestors(root, key):
    if(root == None):
        return;
     
     # Create a stack to hold ancestors
    st = []
     
    # Traverse the complete tree in postorder way till we find the key
    while(True):
         
        # Traverse the left side. While traversing, append the nodes into
        # the stack so that their right subtrees can be traversed later
        while(root != None and root.data != key):
         
            st.append(root);   # append current node
            root = root.left;   # move to next node
         
        # If the node whose ancestors are to be printed is found,
        # then break the while loop.
        if(root != None and root.data == key):
            break;
         
        # Check if right sub-tree exists for the node at top
        # If not then pop that node because we don't need this
        # node any more.
        if(st[-1].right == None):
            root = st[-1];
            st.pop();
             
            # If the popped node is right child of top, then remove the top
            # as well. Left child of the top must have processed before.
            while(len(st) != 0 and st[-1].right == root):
                root = st[-1];
                st.pop();
         
        # if stack is not empty then simply set the root as right child
        # of top and start traversing right sub-tree.
        root = None if len(st) == 0 else st[-1].right;
     
    # If stack is not empty, print contents of stack
    # Here assumption is that the key is there in tree
    while(len(st) != 0):
        print(st[-1].data, end = " ")
        st.pop();
     
# Driver program to test above functions
if __name__=='__main__':
 
     # Let us construct a binary tree
    root = Node(1);
    root.left = Node(2);
    root.right = Node(3);
    root.left.left = Node(4);
    root.left.right = Node(5);
    root.right.left = Node(6);
    root.right.right = Node(7);
    root.left.left.left = Node(8);
    root.left.right.right = Node(9);
    root.right.right.left = Node(10);
     
    print("Following are all keys and their ancestors");
    for key in range(1, 11):
 
        print(key, end = ": ");
        printAncestors(root, key);
        print();
     
# This code is contributed by rutvik_56.


C#




// C# program to print all ancestors
// of a given key
using System;
using System.Collections.Generic;
 
class GFG
{
// Class for a tree node
public class Node
{
    public int data;
    public Node left, right;
 
    // constructor to create Node
    // left and right are by default null
    public Node(int data)
    {
        this.data = data;
    }
}
 
// Iterative Function to print
// all ancestors of a given key
public static void printAncestors(Node root,
                                  int key)
{
    if (root == null)
    {
        return;
    }
 
    // Create a stack to hold ancestors
    Stack<Node> st = new Stack<Node>();
 
    // Traverse the complete tree in
    // postorder way till we find the key
    while (true)
    {
 
        // Traverse the left side. While
        // traversing, push the nodes into
        // the stack so that their right
        // subtrees can be traversed later
        while (root != null && root.data != key)
        {
            st.Push(root); // push current node
            root = root.left; // move to next node
        }
 
        // If the node whose ancestors
        // are to be printed is found,
        // then break the while loop.
        if (root != null && root.data == key)
        {
            break;
        }
 
        // Check if right sub-tree exists for
        // the node at top. If not then pop
        // that node because we don't need
        // this node any more.
        if (st.Peek().right == null)
        {
            root = st.Peek();
            st.Pop();
 
            // If the popped node is right child
            // of top, then remove the top as well.
            // Left child of the top must have
            // processed before.
            while (st.Count > 0 &&
                   st.Peek().right == root)
            {
                root = st.Peek();
                st.Pop();
            }
        }
 
        // if stack is not empty then simply
        // set the root as right child of top
        // and start traversing right sub-tree.
        root = st.Count == 0 ?
                        null : st.Peek().right;
    }
 
    // If stack is not empty, print contents
    // of stack. Here assumption is that the
    // key is there in tree
    while (st.Count > 0)
    {
        Console.Write(st.Peek().data + " ");
        st.Pop();
    }
}
 
// Driver Code
public static void Main(string[] args)
{
    // Let us construct a binary tree
    Node root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    root.right.left = new Node(6);
    root.right.right = new Node(7);
    root.left.left.left = new Node(8);
    root.left.right.right = new Node(9);
    root.right.right.left = new Node(10);
 
    Console.WriteLine("Following are all keys " +
                          "and their ancestors");
    for (int key = 1; key <= 10; key++)
    {
        Console.Write(key + ": ");
        printAncestors(root, key);
        Console.WriteLine();
    }
}
}
 
// This code is contributed by Shrikant13


Javascript




<script>
    // Javascript program to print all ancestors of a given key
     
    // Class for a tree node
    class Node
    {
        // constructor to create Node
        // left and right are by default null
        constructor(data) {
           this.left = null;
           this.right = null;
           this.data = data;
        }
    }
     
    // Iterative Function to print
    // all ancestors of a given key
    function printAncestors(root, key)
    {
        if (root == null)
        {
            return;
        }
 
        // Create a stack to hold ancestors
        let st = [];
 
        // Traverse the complete tree in
        // postorder way till we find the key
        while (true)
        {
 
            // Traverse the left side. While
            // traversing, push the nodes into
            // the stack so that their right
            // subtrees can be traversed later
            while (root != null && root.data != key)
            {
                st.push(root); // push current node
                root = root.left; // move to next node
            }
 
            // If the node whose ancestors
            // are to be printed is found,
            // then break the while loop.
            if (root != null && root.data == key)
            {
                break;
            }
 
            // Check if right sub-tree exists for
            // the node at top. If not then pop
            // that node because we don't need
            // this node any more.
            if (st[st.length - 1].right == null)
            {
                root = st[st.length - 1];
                st.pop();
 
                // If the popped node is right child
                // of top, then remove the top as well.
                // Left child of the top must have
                // processed before.
                while (st.length > 0 &&
                       st[st.length - 1].right == root)
                {
                    root = st[st.length - 1];
                    st.pop();
                }
            }
 
            // if stack is not empty then simply
            // set the root as right child of top
            // and start traversing right sub-tree.
            root = st.length == 0 ?
                            null : st[st.length - 1].right;
        }
 
        // If stack is not empty, print contents
        // of stack. Here assumption is that the
        // key is there in tree
        while (st.length > 0)
        {
            document.write(st[st.length - 1].data + " ");
            st.pop();
        }
    }
     
    // Let us construct a binary tree
    let root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    root.right.left = new Node(6);
    root.right.right = new Node(7);
    root.left.left.left = new Node(8);
    root.left.right.right = new Node(9);
    root.right.right.left = new Node(10);
  
    document.write("Following are all keys " +
                          "and their ancestors" + "</br>");
    for (let key = 1; key <= 10; key++)
    {
        document.write(key + ": ");
        printAncestors(root, key);
        document.write("</br>");
    }
 
// This code is contributed by decode2207.
</script>


Output

Following are all keys and their ancestors
1: 
2: 1 
3: 1 
4: 2 1 
5: 2 1 
6: 3 1 
7: 3 1 
8: 4 2 1 
9: 5 2 1 
10: 7 3 1 

Time Complexity: O(N).
Space Complexity: O(N) for stack space.

Exercise 
Note that the above solution assumes that the given key is present in the given Binary Tree. It may go in an infinite loop if the key is not present. Extend the above solution to work even when the key is not present in the tree.



Previous Article
Next Article

Similar Reads

Print Ancestors of a given node in Binary Tree
Given a Binary Tree and a key, write a function that prints all the ancestors of the key in the given binary tree. For example, if the given tree is following Binary Tree and the key is 7, then your function should print 4, 2, and 1. 1 / \ 2 3 / \ 4 5 / 7Recommended PracticeAncestors in Binary TreeTry It!Thanks to Mike, Sambasiva and wgpshashank fo
13 min read
Count ancestors with smaller value for each node of a Binary Tree
Given a Binary Tree consisting of N nodes, valued from 1 to N, rooted at node 1, the task is for each node is to count the number of ancestors with a value smaller than that of the current node. Examples: Input: Below is the given Tree: 1 / \ 4 5 / /\ 6 3 2Output: 0 1 1 1 1 2Explanation: Since node 1 is the root node, it has no ancestors.Ancestors
9 min read
Postorder traversal of Binary Tree without recursion and without stack
Given a binary tree, perform postorder traversal. Prerequisite - Inorder/preorder/postorder traversal of tree We have discussed the below methods for postorder traversal. 1) Recursive Postorder Traversal. 2) Postorder traversal using Stack. 2) Postorder traversal using two Stacks. Approach 1 The approach used is based on using an unordered set to k
15 min read
Median of ancestors for each Node of a given tree
Given a tree with N vertices from 0 to N - 1 (0th node is root) and val[] where val[i] denotes the value of the ith vertex, the task is to find the array of integers ans[] of length N, where ans[i] denotes the median value of all its ancestors' values including ith vertex. Points to remember: If number of nodes are even: then median = ((n/2th node
10 min read
Find most frequent value of ancestors for each Node of given Tree
Given a tree with N vertices from 0 to N-1 (0th node is root) and val[] where val[i] denotes the value of the ith vertex. The task is to find the array of integers ans[] of length N, where ans[i] denotes the mode value of all its ancestors' values including ith vertex. Note: Mode is the value that has the highest frequency in a given set of values(
10 min read
Iterative method to find ancestors of a given binary tree
Given a binary tree, print all the ancestors of a particular key existing in the tree without using recursion.Here we will be discussing the implementation for the above problem. Examples: Input : 1 / \ 2 7 / \ / \ 3 5 8 9 / \ / 4 6 10 Key = 6 Output : 5 2 1 Ancestors of 6 are 5, 2 and 1. The idea is to use iterative postorder traversal of given bi
12 min read
Count of ancestors with smaller value for each node of an N-ary Tree
Given an N-ary tree consisting of N nodes with values from 1 to N rooted at 1, for all nodes, print the number of ancestors having a smaller value than the current node. Example: Input: Below is the given Tree: 1 / \ 4 5 / / | \ 6 3 2 7 Output: 0 1 1 1 1 2 2 Explanation: Since node 1 is the root node, it has no ancestors. Ancestors of node 2: {1, 5
9 min read
Inorder Tree Traversal without recursion and without stack!
Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree. 1. Initialize current as root 2. While current
9 min read
Find ancestors of each node in the given Graph
Given a graph in the form of an edge list and a directed graph, return all the ancestors of the nodes in any order. An ancestor is a node one step ahead in the hierarchy on the same path reachable to the current node.  Note: The graph has no cycle. Examples: Input: N = 5, Edges[][2] = {{0, 4}, {4, 1}, {4, 3}, {1, 2}}Output: Result[N][] = {{}, {0, 4
15 min read
Count the number of common ancestors of given K nodes in a N-ary Tree
Given an N-ary tree root and a list of K nodes, the task is to find the number of common ancestors of the given K nodes in the tree. Example: Input: root = 3 / \ 2 1 / \ / | \ 9 7 8 6 3K = {7, 2, 9}Output: 2 Explanation: The common ancestors of the nodes 7, 9 and 2 are 2 and 3 Input: root = 2 \ 1 \ 0---4 / | \ 9 3 8K = {9, 8, 3, 4, 0}Output: 3 Appr
10 min read
Article Tags :
Practice Tags :