{"id":9970,"date":"2022-09-26T11:44:22","date_gmt":"2022-09-26T11:44:22","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=9970"},"modified":"2022-10-10T09:14:49","modified_gmt":"2022-10-10T09:14:49","slug":"print-ancestors-of-a-given-binary-tree-node-without-recursion","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/print-ancestors-of-a-given-binary-tree-node-without-recursion\/","title":{"rendered":"Print Ancestors of a Given Binary Tree Node without Recursion"},"content":{"rendered":"

\"\"<\/p>\n

Problem statement<\/h3>\n

You are given a binary tree<\/a> and a key node. Your task is to print all the ancestors of the given key node.<\/p>\n

Input<\/strong>: Root of the binary tree and the key node.
\nOutput<\/strong>: List of all the ancestors of the key node.<\/p>\n

Test cases:<\/h3>\n

Input<\/strong>:<\/p>\n

\"\"<\/p>\n

Key<\/strong> – 8<\/p>\n

Output<\/strong>:
\n[6, 2, 0]]<\/p>\n

Explanation<\/strong>:
\n8 is the child node of 6.
\n6 is the child node of 2.
\n2 is the child node of 0.
\nHence, the ancestors of 8 are 6, 2, 0.<\/p>\n

What are ancestors?<\/h3>\n

Ancestor is a node in a tree data structure which is connected to the lower nodes in the subtree rooted at this node. All the lower nodes are called descendants of this node.<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n
Node<\/th>\nAncestors<\/th>\n<\/tr>\n<\/thead>\n
0<\/td>\n<\/td>\n<\/tr>\n
1<\/td>\n0<\/td>\n<\/tr>\n
2<\/td>\n0<\/td>\n<\/tr>\n
3<\/td>\n1, 0<\/td>\n<\/tr>\n
4<\/td>\n1, 0<\/td>\n<\/tr>\n
5<\/td>\n2, 0<\/td>\n<\/tr>\n
6<\/td>\n2, 0<\/td>\n<\/tr>\n
7<\/td>\n3, 1, 0<\/td>\n<\/tr>\n
8<\/td>\n5, 2, 0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Efficient Approach – Using Stack<\/h3>\n

The idea is to iterate the tree in a postorder traversal because during a recursive postorder traversal of a tree, if we call the postorder function on any node we observe that all its ancestors are already present in the recursive stack. So, we use this observation to solve this problem. We use a stack to store all the ancestors of any node.
\nFirst we traverse all the left nodes of the root until we find the key. If we didn\u2019t find the key then we set the root as the right child of the top of the stack and traverse the left nodes of the root. If the top does not have any right child then, while the root is the right child of the top of the stack, we will set root as top of the stack and pop the top. Here, we will assume that the key is always present in the given binary tree.<\/p>\n

Algorithm<\/h3>\n
    \n
  1. Initialize an empty stack and an array.<\/li>\n
  2. Traverse the tree in postorder till we find the root:
    \na. While root is not null and we haven\u2019t found the key:<\/p>\n
      \n
    • Push the root to the stack and traverse its right subtree.
      \nb. If we found the key, break.
      \nc. If the current top doesn\u2019t have a right child:<\/li>\n
    • Set Root as top of the stack and pop the top.<\/li>\n
    • While the root is the right child of the top of the stack
      \ni. Set Root as top of the stack and pop the top.<\/li>\n
    • Set the root as the right child of the top.<\/li>\n<\/ul>\n<\/li>\n
    • Print the contents of the stack.<\/li>\n<\/ol>\n

      Dry Run:<\/h3>\n

      \"\"<\/p>\n

      \"\"<\/p>\n

      \"\"<\/p>\n

      \"\"<\/p>\n

      \"\"<\/p>\n

      \"\"<\/p>\n

      Code Implementation:<\/h3>\n\t\t\t\t\t\t