Table of Contents
Problem Statement
“Iterative method to find ancestors of a given binary tree” problem states that you are given a binary tree and an integer representing a key. Create a function to print all the ancestors of the given key using iteration.
Example
Input
key = 6
5 2 1
Explanation: The path from the root to the node having value 6 is 1 2 5 6. thus the parent sequence from 6 to root is 5 2 1.
Input :
key = 10
9 7 1
Algorithm
1. Create a structure Node which contains an integer variable to hold data and two pointers left and right of type Node. 2. After that, create the parameterized constructor of the structure which accepts an integer value as it's parameter. Store the integer value in the data variable of Node and initialize left and right pointers as null. 3. Create a function to print the tree path which accepts an unordered map and an integer variable key as it's a parameter. While the key variable is equal to the map[key], print the key. 4. Similarly, create another function to set the parents for all the nodes in the given binary tree which accepts a pointer to the root node and an unordered map as it's parameter. 5. Create a stack data structure of Node* type. Push/insert the root in the stack. 6. After that, traverse while the size of the stack is not 0. Create a pointer curr of type Node and store the element at the top of the stack in it and pop/delete it from the stack. 7. If the right of the curr is present, update the map at index data of right of curr as the data of curr. Push/insert the right of curr in the stack. 8. If the left of the curr is present, update the map at index data of the left of curr as the data of curr. Push/insert the left of curr in the stack. 9. Similarly, create another function to print the ancestors. Check if the root is equal to null, return. 10. Create an unordered map and set the data of its root as 0. 11. Call the function to set the parents of all nodes. 12. Finally, call the function to print the tree path.
Here for this problem, we are given a binary tree and we need to print ancestors of a node. Just like we have children of a node, we have its ancestor except the root of the tree. If you consider the leaves of a tree, they don’t have children. Similarly, the root node does not have an ancestor. Here we store the parent of each node. So that when we need to print its ancestors. We will use the parents to find their ancestors. We have used an unordered_map/HashSet to perform this operation. Since the HashSet allows the insertion/searching/deletion in O(1). We are able to solve this problem in linear time complexity. In the solution below, we are using a graph searching like an approach to traverse the whole tree. And while traversing we are storing the parent of each node. Then we have created a function, while traverse over our map (which stores the parents) to print the ancestors. the whole solution runs in linear time complexity of O(N).
Code
C++ Program for Iterative method to find ancestors of a given binary tree
#include <bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node *left, *right;
Node(int data){
this->data = data;
this->left = this->right = nullptr;
}
};
void printTopToBottomPath(unordered_map<int, int> parent, int key){
while(key = parent[key]){
cout << key << " ";
}
cout << endl;
}
void setParent(Node* root, unordered_map<int, int> &parent){
stack<Node*> stack;
stack.push(root);
while(!stack.empty()){
Node* curr = stack.top();
stack.pop();
if(curr->right){
parent[curr->right->data] = curr->data;
stack.push(curr->right);
}
if(curr->left){
parent[curr->left->data] = curr->data;
stack.push(curr->left);
}
}
}
void printAncestors(Node* root, int node){
if(root == nullptr){
return;
}
unordered_map<int, int> parent;
parent[root->data] = 0;
setParent(root, parent);
printTopToBottomPath(parent, node);
}
int main(){
Node* root = nullptr;
root = new Node(1);
root->left = new Node(2);
root->right = new Node(7);
root->left->left = new Node(3);
root->left->right = new Node(5);
root->right->left = new Node(8);
root->right->right = new Node(9);
root->left->left->left = new Node(4);
root->left->right->right = new Node(6);
root->right->right->left = new Node(10);
int key = 6;
printAncestors(root, key);
return 0;
}5 2 1
Java Program for Iterative method to find ancestors of a given binary tree
import java.util.*;
class Node{
int data;
Node left = null, right = null;
Node(int data){
this.data = data;
}
}
class Main{
public static void printTopToBottomPath(Map<Integer, Integer> parent, int key){
while((key = parent.get(key)) != 0){
System.out.print(key + " ");
}
}
public static void setParent(Node root, Map<Integer, Integer> parent){
Deque<Node> stack = new ArrayDeque<>();
stack.add(root);
while(!stack.isEmpty()){
Node curr = stack.pollLast();
if(curr.right != null){
parent.put(curr.right.data, curr.data);
stack.add(curr.right);
}
if(curr.left != null){
parent.put(curr.left.data, curr.data);
stack.add(curr.left);
}
}
}
public static void printAncestors(Node root, int node){
if(root == null){
return;
}
Map<Integer, Integer> parent = new HashMap<>();
parent.put(root.data, 0);
setParent(root, parent);
printTopToBottomPath(parent, node);
}
public static void main(String[] args){
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(7);
root.left.left = new Node(3);
root.left.right = new Node(5);
root.right.left = new Node(8);
root.right.right = new Node(9);
root.left.left.left = new Node(4);
root.left.right.right = new Node(6);
root.right.right.left = new Node(10);
int key = 6;
printAncestors(root, key);
}
}5 2 1
Complexity Analysis
Time Complexity
O(N), where N is the number of nodes in the given tree. We have just traversed over the whole tree and once we have traversed over the map to print ancestors.
Space Complexity
O(N) because we used extra space in unordered_map and stack.