Print Ancestors of a Given Binary Tree Node without Recursion

Last Updated on October 10, 2022 by Gokul Kannan

Problem statement

You are given a binary tree and a key node. Your task is to print all the ancestors of the given key node.

Input: Root of the binary tree and the key node.
Output: List of all the ancestors of the key node.

Test cases:

Input:

Key – 8

Output:
[6, 2, 0]]

Explanation:
8 is the child node of 6.
6 is the child node of 2.
2 is the child node of 0.
Hence, the ancestors of 8 are 6, 2, 0.

What are ancestors?

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.

Efficient Approach – Using Stack

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.
First we traverse all the left nodes of the root until we find the key. If we didn’t 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.

Algorithm

1. Initialize an empty stack and an array.
2. Traverse the tree in postorder till we find the root:
   a. While root is not null and we haven’t found the key:
   • Push the root to the stack and traverse its right subtree.
     b. If we found the key, break.
     c. If the current top doesn’t have a right child:
   • Set Root as top of the stack and pop the top.
   • While the root is the right child of the top of the stack
     i. Set Root as top of the stack and pop the top.
   • Set the root as the right child of the top.
3. Print the contents of the stack.

Dry Run:

Code Implementation:

import java.util.Stack;

public class Main
{
	// Node structure
	static class Node
	{
		int val;
		Node left,right;
		
		// Constructor to create node objects
		Node(int val)
		{
			this.val = val;
		}
	}
	
	// This function will print all the ancestors of the given key.
	static void printAllAncestors(Node root, int key)
	{
		if(root == null)
			return;
		
		// Create a empty stack
		Stack<Node> st = new Stack<>();
		
		// Traverse the complete tree in postorder way till we find the key
		while(true)
		{
			
			// Traverse the left boundary and push all nodes into the stack.
			while(root != null && root.val != key)
			{
				st.push(root); 
				root = root.left; 
			}
			
			// If we found the key node, then break.
			if(root != null && root.val == key)
				break;
			
			// If the node at the top of the stack doesn't contains a right sub-tree
			// Pop the top of the stack.
			if(st.peek().right == null)
			{
				root = st.peek();
				st.pop();
				
				// If the node we just just popped was the right child of the top of the stack 
				// Then pop the top as well because all its left must have already been processed.
				while( !st.empty() && st.peek().right == root)
				{
					root = st.peek();
					st.pop();
				}
			}
			
			// Set the root as right child of the top
			root = st.empty() ? null : st.peek().right;
		}
		
		// While stack is not empty, print its contents
		while(!st.empty() )
		{
			System.out.print(st.pop().val+" ");
		}
	}
	
	public static void main(String[] args)
	{
		// Construct the binary tree.
		Node root = new Node(0);
		root.left = new Node(1);
		root.right = new Node(2);
		root.left.left = new Node(3);
		root.left.right = new Node(4);
		root.right.left = new Node(5);
		root.right.right = new Node(6);
		root.left.left.left = new Node(7);
		root.right.left.left = new Node(8);
		
        int key = 8;
        printAllAncestors(root, key);
	}
}

Output:
5 2 0

Time complexity: O(n). Each node is added and removed from the stack at most once.

Space Complexity: O(n). The stack may have to store all the nodes of the binary tree.

We tried to discuss Print Ancestors of a Given Binary Tree Node without Recursion. We hope this article gives you a better understanding of Print Ancestors of a Given Binary Tree Node without Recursion. Prepbytes also provides a good collection of Foundation Courses that can help you enhance your coding skills. Want to make sure you ace the interview in one go? Join our Placement Program that will help you get prepared and land your dream job at MNCs. Mentors of Prepbytes are highly experienced and can provide you with basic, in-depth subject knowledge for better understanding.