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.

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The idea is to use iterative postorder traversal of given binary tree.

C++

 // C++ program to print all ancestors of a given key #include 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 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(7);     root->left->left = newNode(3);     root->left->right = newNode(5);     root->right->left = newNode(8);     root->right->right = newNode(9);     root->left->left->left = newNode(4);     root->left->right->right = newNode(6);     root->right->right->left = newNode(10);        int key = 6;     printAncestors(root, key);        return 0; }

Java

 // Java program to print all  // ancestors of a given key  import java.util.*;    class GfG  {    // Structure for a tree node  static class Node {      int data;      Node left, right;  }    // A utility function to  // create a new tree node  static Node newNode(int data)  {      Node node = new Node();      node.data = data;      node.left = null;     node.right = null;      return node;  }     // 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 st = new Stack ();         // Traverse the complete tree in      // postorder way till we find the key      while (1 == 1)      {             // 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.isEmpty() && 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.isEmpty() ? 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.isEmpty())     {          System.out.print(st.peek().data + " ");          st.pop();      }  }     // Driver code  public static void main(String[] args)  {      // Let us construct a binary tree      Node root = newNode(1);      root.left = newNode(2);      root.right = newNode(7);      root.left.left = newNode(3);      root.left.right = newNode(5);      root.right.left = newNode(8);      root.right.right = newNode(9);      root.left.left.left = newNode(4);      root.left.right.right = newNode(6);      root.right.right.left = newNode(10);         int key = 6;      printAncestors(root, key);  } }    // This code is contributed  // by prerna saini

Python3

 # Python program to print all ancestors of a given key    # A class to create a new tree node  class newNode:     def __init__(self, data):         self.data = data          self.left = 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 (1):            # Traverse the left side. While traversing, push          # the nodes into the stack so that their right          # subtrees can be traversed later          while (root and root.data != key):              st.append(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 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 code if __name__ == '__main__':        # Let us construct a binary tree      root = newNode(1)      root.left = newNode(2)      root.right = newNode(7)      root.left.left = newNode(3)      root.left.right = newNode(5)      root.right.left = newNode(8)      root.right.right = newNode(9)      root.left.left.left = newNode(4)      root.left.right.right = newNode(6)      root.right.right.left = newNode(10)         key = 6     printAncestors(root, key)        # This code is contributed by PranchalK.

/div>

C#

 // C# program to print all  // ancestors of a given key  using System; using System.Collections.Generic;    class GfG  {    // Structure for a tree node  public class Node {      public int data;      public Node left, right;  }    // A utility function to  // create a new tree node  static Node newNode(int data)  {      Node node = new Node();      node.data = data;      node.left = null;     node.right = null;      return node;  }     // 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 st = new Stack ();         // Traverse the complete tree in      // postorder way till we find the key      while (1 == 1)      {             // 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 = newNode(1);      root.left = newNode(2);      root.right = newNode(7);      root.left.left = newNode(3);      root.left.right = newNode(5);      root.right.left = newNode(8);      root.right.right = newNode(9);      root.left.left.left = newNode(4);      root.left.right.right = newNode(6);      root.right.right.left = newNode(10);         int key = 6;      printAncestors(root, key);  } }    // This code has been contributed by 29AjayKumar

Output:

5 2 1

tags:

Stack Tree Stack Tree