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 binary tree.
Algorithm:
Step 1: Start
Step 2: create a function of void return type called “printAncestors” which takes a root node and an integer value as input parameter.
a. set the base condition as if root == null then return.
b. create a stack of node types to hold ancestors
c. start a while loop with condition 1==1 which means it will always be true.
1. Move each node into the stack by moving them up and along the left side of the tree starting at the root until we reach the node that matches the key.
2. End the while loop if the node with the specified key is located.
3. Remove the node from the stack and assign it to the root if the right subtree of the node at the top of the stack, st, is null.
4. Pop that node as well if it is the right child of the node at the top of the stack, st.
5. Set root as the right child of the node at the top of the stack st if it is not empty and carry on exploring the right subtree.
Step 3: If the stack st is not empty when we have located the node with the specified key, print the data of each node in the stack st starting at the top and continuing until the stack is empty.
Step 4: End
Implementation:
C++
#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()
{
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
import java.util.*;
class GfG
{
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( 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);
}
}
|
Python3
class newNode:
def __init__( self , data):
self .data = data
self .left = self .right = None
def printAncestors(root, key):
if (root = = None ):
return
st = []
while ( 1 ):
while (root and root.data ! = key):
st.append(root)
root = root.left
if (root and root.data = = key):
break
if (st[ - 1 ].right = = None ):
root = st[ - 1 ]
st.pop()
while ( len (st) ! = 0 and st[ - 1 ].right = = root):
root = st[ - 1 ]
st.pop()
root = None if len (st) = = 0 else st[ - 1 ].right
while ( len (st) ! = 0 ):
print (st[ - 1 ].data,end = " " )
st.pop()
if __name__ = = '__main__' :
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)
|
C#
using System;
using System.Collections.Generic;
class GfG
{
public class Node
{
public int data;
public 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.Count != 0 && st.Peek().right == root)
{
root = st.Peek();
st.Pop();
}
}
root = st.Count == 0 ? null : st.Peek().right;
}
while (st.Count != 0)
{
Console.Write(st.Peek().data + " " );
st.Pop();
}
}
public static void Main(String[] args)
{
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);
}
}
|
Javascript
<script>
class Node
{
constructor(data)
{
this .left = null ;
this .right = null ;
this .data = data;
}
}
function newNode(data)
{
let node = new Node(data);
return node;
}
function printAncestors(root, key)
{
if (root == null )
return ;
let st = [];
while (1 == 1)
{
while (root != null && root.data != key)
{
st.push(root);
root = root.left;
}
if (root != null && root.data == key)
break ;
if (st[st.length - 1].right == null )
{
root = st[st.length - 1];
st.pop();
while (st.length != 0 &&
st[st.length - 1].right == root)
{
root = st[st.length - 1];
st.pop();
}
}
root = st.length == 0 ? null :
st[st.length - 1].right;
}
while (st.length != 0)
{
document.write(st[st.length - 1].data + " " );
st.pop();
}
}
let 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);
let key = 6;
printAncestors(root, key);
</script>
|
Complexity Analysis:
- Time Complexity: O(n)
- Space Complexity: O(n)
If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!