Iterative Postorder Traversal

Last Updated on October 10, 2022 by Gokul Kannan

Problem Statement:

Given a Binary Tree, you need to find all the ancestors of a particular node of that binary tree. You will be given the value that is stored in a particular node.

Constraint: You cannot use recursion.

Example:

As shown in the image above, we have the key 80 and the ancestors of 80 are 10,20, and 50. So, we have printed a list containing the ancestors of the given key node.

Approach

The idea is to use the iterative postorder traversal. While traversing the tree in postorder iteratively, we stop the traversal when we find the key value and we will have the ancestors of the key already in the stack that we used for iterative postorder traversal. So, we will print the elements of the stack.

Now, we just need to recall how to traverse the tree in postorder iteratively.

We know that the postorder traversal is “left-right root”. This means that we have to try to go to the left of the given tree till it is possible. Then, we have to traverse the right of the tree till it is possible. After traversing both left and right, we have to print. So, the algorithm that we are going to use depends highly on our attempts to maintain the “left-right root” order.

Let us see what the algorithm is.

Algorithm:

Assign a variable current to the root of the tree and initialize a stack of nodes (initially empty).
While current does not become null OR the stack is not empty
- If the current is not equal to null
  - Push current into the stack.
  - Move current to its left.
- Else
  - Assign a variable temp to the right child at the top of the stack.
  - So, the top of the stack might or might not have the right child. So, if the temp is null
    - temp = stack.top()
    - stack.pop()
    - Add temp to the postorder
    - While the stack is not empty AND the temp variable is equal to the right child of the top of the stack,
      - temp = stack.top()
      - stack.pop()
      - Add temp to the postorder
  - Else, current = temp.

So, this algorithm helps maintain the postorder i.e. “left-right root”. Let us see an example dry run for the above algorithm.

Dry Run

Consider the following tree shown below.

So, we will start by having the variable curr (current) at the root of the tree.

So, according to the first step of the algorithm, since current is not equal to null, we add it to the stack and move it to its left.

We keep on repeating this step as shown below.

So, the value of current is now null as after pushing 30 into the stack, it moved to its left child which is null. Now, we follow the else condition in the algorithm. So, we will take a variable temp that will be the right child at the top of the stack. Since the top of the stack is 30, temp = right child of 30 i.e. 40.

Since a temp is not equal to null, current will now move to temp.

Since the current is now not null, we add it to the stack and move to its left child.

So, we see that again, the steps will be repeated. This means that every time, we try to go to the left child of every node and if the left is null, we move to its right. This will keep happening till we reach Node 60.

Now, the temp will be the right of the top of the stack. This means the temp will be the right of 60. So, temp = null.

Since temp = null, we pop a value from the stack and it becomes temp and we also add it to the postorder.

Now, while the stack is not empty AND temp is equal to the right child of the top of the stack, we have to keep popping from the stack and adding the node to the post order.

So, 50 was popped and added to the postorder. Now, we will pop 40 since the right child of 40 is equal to temp.

This will continue as shown below.

Now the right child of the top of the stack is null but temp = 30 (Node 30 not value). So, again, we see that curr = null and we follow the above-discussed steps.
You can complete the rest of the traversal yourself and you will find that we end up having the postorder of the tree correctly.

So, now that we have understood the procedure, let us write the code for the same.

#include <bits/stdc++.h>
using namespace std;

struct Node {
	int data;
	struct Node* left, *right;
};

struct Node* newNode(int data)
{
	struct Node* node = (struct Node*)malloc(sizeof(struct Node));
	node->data = data;
	node->left = node->right = NULL;
	return node;
}

void printAncestors(struct Node* root, int key)
{
	if (root == NULL)
		return;

	stack<struct Node*> st;

	while (1) {

		while (root && root->data != key) {
			st.push(root); 
			root = root->left; 
		}

		if (root && root->data == key)
			break;

		if (st.top()->right == NULL) {
			root = st.top();
			st.pop();

			while (!st.empty() && st.top()->right == root) {
				root = st.top();
				st.pop();
			}
		}

		root = st.empty() ? NULL : st.top()->right;
	}

	while (!st.empty()) {
		cout << st.top()->data << " ";
		st.pop();
	}
}

int main()
{
	// Let us construct a binary tree
	struct Node* root = newNode(10);
	root->left = newNode(20);
	root->right = newNode(30);
	root->left->left = newNode(40);
	root->left->right = newNode(50);
	root->right->left = newNode(60);
	root->right->right = newNode(70);
	root->left->right->left = newNode(80);
	root->right->left->left = newNode(90);

    
	int key = 80;
	printAncestors(root, key);

	return 0;
}

import java.util.*;

class Main
{
static class Node
{
	int data;
	Node left, right;
}

static Node newNode(int data)
{
	Node node = new Node();
	node.data = data;
	node.left = null;
	node.right = null;
	return node;
}

static void printAncestors(Node root, int key)
{
	if (root == null)
		return;

	Stack<Node> st = new Stack<Node> ();

	while (1 == 1)
	{

		while (root != null && root.data != key)
		{
			st.push(root);
			root = root.left;
		}

		if (root != null && root.data == key)
			break;

		if (st.peek().right == null)
		{
			root = st.peek();
			st.pop();

			while (!st.isEmpty() && st.peek().right == root)
			{
				root = st.peek();
				st.pop();
			}
		}

		root = st.isEmpty() ? null : st.peek().right;
	}

	while (!st.isEmpty())
	{
		System.out.print(st.peek().data + " ");
		st.pop();
	}
}

public static void main(String[] args)
{
	Node root = newNode(10);
	root.left = newNode(20);
	root.right = newNode(30);
	root.left.left = newNode(40);
	root.left.right = newNode(50);
	root.right.left = newNode(60);
	root.right.right = newNode(70);
	root.left.right.left = newNode(80);
	root.right.left.right = newNode(90);

	int key = 80;
	printAncestors(root, key);
}
}

Time Complexity: The time complexity of the above algorithm is O(N) as we might have to traverse the entire tree in the worst case.

Space Complexity (Auxiliary Space): The auxiliary space is O(N) as we have used a stack to traverse in post order iteratively.

We tried to discuss Iterative Method to find Ancestors of a Given Binary Tree. We hope this article gives you a better understanding of Iterative Method to find Ancestors of a Given Binary Tree, 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 which 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.

Iterative Method to find Ancestors of a Given Binary Tree

Problem Statement:

Example:

Approach