# Find ancestors of given node in a Binary Tree

Here given code implementation process.

``````/*
C Program
+ Find ancestors of given node in a Binary Tree

*/
#include <stdio.h>

#include <stdlib.h>
//structure of Binary Tree node
struct Node {
int data;
struct Node *left, *right;
};

struct Stack {
struct Node *element;
struct Stack *next;
};

//Create a binary tree nodes and node fields (data,pointer)
//And returning the reference of newly nodes
struct Node *insert(int data) {
//create dynamic memory to new binary tree node
struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
if (new_node != NULL) {
//set data and pointer values
new_node->data = data;
new_node->left = NULL; //Initially node left-pointer is NULL
new_node->right = NULL; //Initially node right-pointer is NULL
} else {
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}
//return reference
return new_node;

}
//Create a stack element and return this reference
struct Stack *push(struct Node *tree_node, struct Stack *head) {

struct Stack *stack_node = (struct Stack *) malloc(sizeof(struct Stack));
if (stack_node != NULL) {
//set pointer values
stack_node->element = tree_node;

} else {
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}
return stack_node;
}
//Remove stack elements
void pop(struct Stack **top) {
if ( *top != NULL) {
struct Stack *remove = *top;
*top = remove->next;
remove->element = NULL;
remove->next = NULL;
free(remove);
remove = NULL;
}
}
void showPath(struct Stack *temp) {

if (temp != NULL) {
showPath(temp->next);
printf("%3d", temp->element->data);
}
}
//Get all Ancestors of given node element
void getAncestors(struct Node *root, struct Stack **head, int *status, int node) {
if (root != NULL && *status == 0) {

if (root->data == node) {

if ( *head == NULL) {
//When no Ancestor
*status = -1;
return;
}

*status = 1;

return;
}

}
}

void findAncestors(struct Node *root, int node) {

int status = 0;

printf("\nAncestor of node %d are : ", node);

getAncestors(root, & head, & status, node);

if (status == 0) {
printf(" Node not exist");

} else if (status == -1) {

printf(" No Ancestor");
}
}
int main() {

struct Node *root = NULL;
/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
\       /
7     8
/     / \
11    9   10
*/
root = insert(1);
root->left = insert(2);
root->right = insert(3);
root->right->right = insert(6);
root->right->left = insert(5);
root->left->left = insert(4);
root->left->left->right = insert(7);
root->right->right->left = insert(8);

root->right->right->left->left = insert(9);
root->right->right->left->right = insert(10);
root->left->left->right->left = insert(11);
//Test case
findAncestors(root, 7);
findAncestors(root, 10);
findAncestors(root, 5);
findAncestors(root, 1);
findAncestors(root, 11);
findAncestors(root, 12);
return 0;
}```
```

#### Output

``````Ancestor of node 7 are :   1  2  4
Ancestor of node 10 are :   1  3  6  8
Ancestor of node 5 are :   1  3
Ancestor of node 1 are :  No Ancestor
Ancestor of node 11 are :   1  2  4  7
Ancestor of node 12 are :  Node not exist``````
``````/*
Java Program
Find ancestors of given node in a Binary Tree
*/

#include<iostream>

using namespace std;
class Node {
public:
int data;
Node *left, *right;
Node(int value) {
this->data = value;
this->left = this->right = NULL;
}
};
class MyStack {
public:
Node *element;
MyStack *next;
this->element = new_node;
}
};
class BinaryTree {
public:
Node *root;
MyStack *top;
int flag;

BinaryTree() {
this->root = NULL;
this->top = NULL;
this->flag = 0;
}
void push(Node *tree_node) {
this->top = new MyStack(tree_node, this->top);
}
void pop() {
if (this->top != NULL) {
MyStack *remove = this->top;
this->top = remove->next;
remove->element = NULL;
remove->next = NULL;
remove = NULL;
}
}
cout << "  " << head->element->data;
}
}
void getAncestors(Node *head, int node) {
if (head != NULL && this->flag == 0) {
if (this->top == NULL) {
this->flag = -1;
return;
}
this->flag = 1;
this->showPath(this->top);
return;
}
this->pop();
}
}
void findAncestors(int node) {
this->flag = 0;
cout << "\nAncestor of node "<< node <<" are : ";
this->getAncestors(this->root, node);
if (this->flag == 0) {
cout << " Node not exist";
} else
if (this->flag == -1) {
cout << " No Ancestor";
}
}
};

int main() {
BinaryTree obj ;

/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
\       /
7     8
/     / \
11    9   10
*/
obj.root = new Node(1);
obj.root->left = new Node(2);
obj.root->right = new Node(3);
obj.root->right->right = new Node(6);
obj.root->right->left = new Node(5);
obj.root->left->left = new Node(4);
obj.root->left->left->right = new Node(7);
obj.root->right->right->left = new Node(8);
obj.root->right->right->left->left = new Node(9);
obj.root->right->right->left->right = new Node(10);
obj.root->left->left->right->left = new Node(11);
obj.findAncestors(7);
obj.findAncestors(10);
obj.findAncestors(5);
obj.findAncestors(1);
obj.findAncestors(11);
obj.findAncestors(12);

return 0;
}```
```

#### Output

``````Ancestor of node 7 are :   1  2  4
Ancestor of node 10 are :   1  3  6  8
Ancestor of node 5 are :   1  3
Ancestor of node 1 are :  No Ancestor
Ancestor of node 11 are :   1  2  4  7
Ancestor of node 12 are :  Node not exist``````
``````/*
Java Program
Find ancestors of given node in a Binary Tree
*/

//Class of Binary Tree node
class Node {

public int data;
public Node left, right;
//Make a tree node
public Node(int value) {
//Assign field values
data = value;
left = right = null;
}
}

class MyStack {
public Node element;
public MyStack next;

public MyStack(Node new_node, MyStack head) {
element = new_node;
}
}
public class BinaryTree {

public Node root;

public MyStack top;

public int flag;

public BinaryTree() {
//Set initial initial values
root = null;
top = null;
flag = 0;
}

//Create a MyStack element and return this reference
public void push(Node tree_node) {

top = new MyStack(tree_node, top);

}

//Remove MyStack elements
public void pop() {
if (top != null) {
MyStack remove = top;
top = remove.next;
remove.element = null;
remove.next = null;
remove = null;
}
}

}
}

//Get all Ancestors of given node element
public void getAncestors(Node head, int node) {
if (head != null && this.flag == 0) {

if (top == null) {
//When no Ancestor
this.flag = -1;
return;
}

this.flag = 1;
showPath(top);

return;
}

pop();

}
}

public void findAncestors(int node) {

this.flag = 0;

System.out.print("\nAncestor of node " + node + " are : ");

getAncestors(root, node);

if (this.flag == 0) {
System.out.print(" Node not exist");

} else if (this.flag == -1) {

System.out.print(" No Ancestor");
}
}
public static void main(String[] args) {
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();

/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
\       /
7     8
/     / \
11    9   10
*/
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.right = new Node(3);
obj.root.right.right = new Node(6);
obj.root.right.left = new Node(5);
obj.root.left.left = new Node(4);
obj.root.left.left.right = new Node(7);
obj.root.right.right.left = new Node(8);

obj.root.right.right.left.left = new Node(9);
obj.root.right.right.left.right = new Node(10);
obj.root.left.left.right.left = new Node(11);
//Test case
obj.findAncestors(7);
obj.findAncestors(10);
obj.findAncestors(5);
obj.findAncestors(1);
obj.findAncestors(11);
obj.findAncestors(12);

}
}```
```

#### Output

``````Ancestor of node 7 are :   1  2  4
Ancestor of node 10 are :   1  3  6  8
Ancestor of node 5 are :   1  3
Ancestor of node 1 are :  No Ancestor
Ancestor of node 11 are :   1  2  4  7
Ancestor of node 12 are :  Node not exist``````
``````/*
C# Program
Find ancestors of given node in a Binary Tree
*/
using System;
//Class of Binary Tree node
public class Node {

public int data;
public Node left, right;
//Make a tree node
public Node(int value) {
//Assign field values
data = value;
left = right = null;
}
}

public class MyStack {
public Node element;
public MyStack next;

public MyStack(Node new_node, MyStack head) {
element = new_node;
}
}
public class BinaryTree {

public Node root;

public MyStack top;

public int flag;

public BinaryTree() {
//Set initial initial values
root = null;
top = null;
flag = 0;
}

//Create a MyStack element and return this reference
public void push(Node tree_node) {

top = new MyStack(tree_node, top);

}

//Remove MyStack elements
public void pop() {
if (top != null) {
MyStack remove = top;
top = remove.next;
remove.element = null;
remove.next = null;
remove = null;
}
}

}
}

//Get all Ancestors of given node element
public void getAncestors(Node head, int node) {
if (head != null && this.flag == 0) {

if (top == null) {
//When no Ancestor
this.flag = -1;
return;
}

this.flag = 1;
showPath(top);

return;
}

pop();

}
}

public void findAncestors(int node) {

this.flag = 0;

Console.Write("\nAncestor of node " + node + " are : ");

getAncestors(root, node);

if (this.flag == 0) {
Console.Write(" Node not exist");

} else if (this.flag == -1) {

Console.Write(" No Ancestor");
}
}
public static void Main(String[] args) {
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();

/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
\       /
7     8
/     / \
11    9   10
*/
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.right = new Node(3);
obj.root.right.right = new Node(6);
obj.root.right.left = new Node(5);
obj.root.left.left = new Node(4);
obj.root.left.left.right = new Node(7);
obj.root.right.right.left = new Node(8);

obj.root.right.right.left.left = new Node(9);
obj.root.right.right.left.right = new Node(10);
obj.root.left.left.right.left = new Node(11);
//Test case
obj.findAncestors(7);
obj.findAncestors(10);
obj.findAncestors(5);
obj.findAncestors(1);
obj.findAncestors(11);
obj.findAncestors(12);

}
}```
```

#### Output

``````Ancestor of node 7 are :   1  2  4
Ancestor of node 10 are :   1  3  6  8
Ancestor of node 5 are :   1  3
Ancestor of node 1 are :  No Ancestor
Ancestor of node 11 are :   1  2  4  7
Ancestor of node 12 are :  Node not exist``````
``````#Python3 Program
#Find ancestors of given node in a Binary Tree

class Node :

def __init__(self, value) :
self.data = value;
self.left = self.right = None;

class MyStack :

self.element = new_node;

class BinaryTree :
def __init__(self) :
self.root = None;
self.top = None;
self.flag = 0;

def push(self, tree_node) :
self.top = MyStack(tree_node, self.top);

def pop(self) :
if (self.top != None) :
remove = self.top;
self.top = remove.next;
remove.element = None;
remove.next = None;
remove = None;

if (head != None and self.flag == 0) :
if (self.top == None) :
self.flag = -1;
return;

self.flag = 1;
self.showPath(self.top);
return;

self.pop();

def findAncestors(self, node) :
self.flag = 0;
print("\nAncestor of node ", node ," are : ",end=" ");
self.getAncestors(self.root, node);
if (self.flag == 0) :
print(" Node not exist",end=" ");
elif (self.flag == -1) :
print(" No Ancestor",end=" ");

def main() :
obj = BinaryTree();

# Make A Binary Tree
#        1
#       /  \
#      2    3
#     /    /  \
#    4    5    6
#     \       /
#      7     8
#     /     / \
#    11    9   10
#
obj.root = Node(1);
obj.root.left = Node(2);
obj.root.right = Node(3);
obj.root.right.right = Node(6);
obj.root.right.left = Node(5);
obj.root.left.left = Node(4);
obj.root.left.left.right = Node(7);
obj.root.right.right.left = Node(8);
obj.root.right.right.left.left = Node(9);
obj.root.right.right.left.right = Node(10);
obj.root.left.left.right.left = Node(11);
obj.findAncestors(7);
obj.findAncestors(10);
obj.findAncestors(5);
obj.findAncestors(1);
obj.findAncestors(11);
obj.findAncestors(12);

if __name__ == "__main__":
main()```
```

#### Output

``````Ancestor of node  7  are :  1 2 4
Ancestor of node  10  are :  1 3 6 8
Ancestor of node  5  are :  1 3
Ancestor of node  1  are :   No Ancestor
Ancestor of node  11  are :  1 2 4 7
Ancestor of node  12  are :   Node not exist ``````
``````#Ruby Program
#Find ancestors of given node in a Binary Tree
class Node
attr_accessor :data, :left, :right
def initialize(value)
@data = value
@left = @right = nil
end
end

class MyStack
attr_accessor :element, :next
@element = new_node
end
end

class BinaryTree
attr_accessor :root, :top, :flag
def initialize()
@root = nil
@top = nil
@flag = 0
end
def push(tree_node)
@top = MyStack.new(tree_node, @top)
end
def pop()
if (@top != nil)
remove = @top
@top = remove.next
remove.element = nil
remove.next = nil
remove = nil
end
end
end
end
if (head != nil and self.flag == 0)
if (@top == nil)
self.flag = -1
return
end
self.flag = 1
self.showPath(@top)
return
end
self.pop()
end
end
def findAncestors(node)
self.flag = 0
print("\nAncestor of node ", node , " are  :")
self.getAncestors(@root, node)
if (self.flag == 0)
print(" Node not exist")
elsif (self.flag == -1)
print(" No Ancestor")
end
end

end

def main()
obj = BinaryTree.new()
# Make A Binary Tree
#        1
#       /  \
#      2    3
#     /    /  \
#    4    5    6
#     \       /
#      7     8
#     /     / \
#    11    9   10
#
obj.root = Node.new(1)
obj.root.left = Node.new(2)
obj.root.right = Node.new(3)
obj.root.right.right = Node.new(6)
obj.root.right.left = Node.new(5)
obj.root.left.left = Node.new(4)
obj.root.left.left.right = Node.new(7)
obj.root.right.right.left = Node.new(8)
obj.root.right.right.left.left = Node.new(9)
obj.root.right.right.left.right = Node.new(10)
obj.root.left.left.right.left = Node.new(11)
obj.findAncestors(7)
obj.findAncestors(10)
obj.findAncestors(5)
obj.findAncestors(1)
obj.findAncestors(11)
obj.findAncestors(12)
end
main()```
```

#### Output

``````Ancestor of node 7 are  :  1  2  4
Ancestor of node 10 are  :  1  3  6  8
Ancestor of node 5 are  :  1  3
Ancestor of node 1 are  : No Ancestor
Ancestor of node 11 are  :  1  2  4  7
Ancestor of node 12 are  : Node not exist``````
``````<?php
/*
Php Program
Find ancestors of given node in a Binary Tree
*/
class Node {
public \$data;
public \$left;
public \$right;

function __construct(\$value) {
\$this->data = \$value;
\$this->left = \$this->right = null;
}
}
class MyStack {
public \$element;
public \$next;

\$this->element = \$new_node;
}
}
class BinaryTree {
public \$root;
public \$top;
public \$flag;

function __construct() {
\$this->root = null;
\$this->top = null;
\$this->flag = 0;
}
public  function push(\$tree_node) {
\$this->top = new MyStack(\$tree_node, \$this->top);
}
public  function pop() {
if (\$this->top != null) {
\$remove = \$this->top;
\$this->top = \$remove->next;
\$remove->element = null;
\$remove->next = null;
\$remove = null;
}
}
}
}
if (\$head != null && \$this->flag == 0) {
if (\$this->top == null) {
\$this->flag = -1;
return;
}
\$this->flag = 1;
\$this->showPath(\$this->top);
return;
}
\$this->pop();
}
}
public  function findAncestors(\$node) {
\$this->flag = 0;
echo("\nAncestor of node ". \$node ." are : ");
\$this->getAncestors(\$this->root, \$node);
if (\$this->flag == 0) {
echo(" Node not exist");
} else
if (\$this->flag == -1) {
echo(" No Ancestor");
}
}
}
function main() {
\$obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
\       /
7     8
/     / \
11    9   10
*/
\$obj->root = new Node(1);
\$obj->root->left = new Node(2);
\$obj->root->right = new Node(3);
\$obj->root->right->right = new Node(6);
\$obj->root->right->left = new Node(5);
\$obj->root->left->left = new Node(4);
\$obj->root->left->left->right = new Node(7);
\$obj->root->right->right->left = new Node(8);
\$obj->root->right->right->left->left = new Node(9);
\$obj->root->right->right->left->right = new Node(10);
\$obj->root->left->left->right->left = new Node(11);
\$obj->findAncestors(7);
\$obj->findAncestors(10);
\$obj->findAncestors(5);
\$obj->findAncestors(1);
\$obj->findAncestors(11);
\$obj->findAncestors(12);
}
main();```
```

#### Output

``````Ancestor of node 7 are  :  1  2  4
Ancestor of node 10 are  :  1  3  6  8
Ancestor of node 5 are  :  1  3
Ancestor of node 1 are  : No Ancestor
Ancestor of node 11 are  :  1  2  4  7
Ancestor of node 12 are  : Node not exist``````
``````/*
Node JS Program
Find ancestors of given node in a Binary Tree
*/
class Node {

constructor(value) {
this.data = value;
this.left = this.right = null;
}
}
class MyStack {

this.element = new_node;
}
}
class BinaryTree {

constructor() {
this.root = null;
this.top = null;
this.flag = 0;
}
push(tree_node) {
this.top = new MyStack(tree_node, this.top);
}
pop() {
if (this.top != null) {
var remove = this.top;
this.top = remove.next;
remove.element = null;
remove.next = null;
remove = null;
}
}
}
}
if (head != null && this.flag == 0) {
if (this.top == null) {
this.flag = -1;
return;
}
this.flag = 1;
this.showPath(this.top);
return;
}
this.pop();
}
}
findAncestors(node) {
this.flag = 0;
process.stdout.write("\nAncestor of node " + node + " are : ");
this.getAncestors(this.root, node);
if (this.flag == 0) {
process.stdout.write(" Node not exist");
} else
if (this.flag == -1) {
process.stdout.write(" No Ancestor");
}
}
}

function main() {
var obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
\       /
7     8
/     / \
11    9   10
*/
obj.root = new Node(1);
obj.root.left = new Node(2);
obj.root.right = new Node(3);
obj.root.right.right = new Node(6);
obj.root.right.left = new Node(5);
obj.root.left.left = new Node(4);
obj.root.left.left.right = new Node(7);
obj.root.right.right.left = new Node(8);
obj.root.right.right.left.left = new Node(9);
obj.root.right.right.left.right = new Node(10);
obj.root.left.left.right.left = new Node(11);
obj.findAncestors(7);
obj.findAncestors(10);
obj.findAncestors(5);
obj.findAncestors(1);
obj.findAncestors(11);
obj.findAncestors(12);
}
main();```
```

#### Output

``````Ancestor of node 7 are  :  1  2  4
Ancestor of node 10 are  :  1  3  6  8
Ancestor of node 5 are  :  1  3
Ancestor of node 1 are  : No Ancestor
Ancestor of node 11 are  :  1  2  4  7
Ancestor of node 12 are  : Node not exist``````
``````/*
Swift 4 Program
Find ancestors of given node in a Binary Tree
*/
class Node {
var data: Int;
var left: Node? ;
var right: Node? ;

init(_ value: Int) {
self.data = value;
self.left = nil;
self.right = nil;
}
}
class MyStack {
var element: Node? ;
var next: MyStack? ;
init(_ new_node: Node? , _ head : MyStack? ) {
self.element = new_node;
}
}
class BinaryTree {
var root: Node? ;
var top: MyStack? ;
var flag: Int;
init() {
self.root = nil;
self.top = nil;
self.flag = 0;
}
func push(_ tree_node: Node? ) {
self.top = MyStack(tree_node, self.top);
}
func pop() {
if (self.top != nil) {
var remove: MyStack? = self.top;
self.top = remove!.next;
remove!.element = nil;
remove!.next = nil;
remove = nil;
}
}
func showPath(_ head: MyStack? ) {
print(temp!.data, terminator : " ");
}
}
func getAncestors(_ head: Node? , _ node : Int) {
if (head != nil && self.flag == 0) {
if (self.top == nil) {
self.flag = -1;
return;
}
self.flag = 1;
self.showPath(self.top);
return;
}
self.pop();
}
}
func findAncestors(_ node: Int) {
self.flag = 0;
print("\nAncestor of node ", node , " are : ", terminator : " ");
self.getAncestors(self.root, node);
if (self.flag == 0) {
print(" Node not exist", terminator : " ");
} else
if (self.flag == -1) {
print(" No Ancestor", terminator : " ");
}
}
}
func main() {
let obj: BinaryTree = BinaryTree();

/* Make A Binary Tree
-----------------------
1
/  \
2    3
/    /  \
4    5    6
\       /
7     8
/     / \
11    9   10
*/
obj.root = Node(1);
obj.root!.left = Node(2);
obj.root!.right = Node(3);
obj.root!.right!.right = Node(6);
obj.root!.right!.left = Node(5);
obj.root!.left!.left = Node(4);
obj.root!.left!.left!.right = Node(7);
obj.root!.right!.right!.left = Node(8);
obj.root!.right!.right!.left!.left = Node(9);
obj.root!.right!.right!.left!.right = Node(10);
obj.root!.left!.left!.right!.left = Node(11);
obj.findAncestors(7);
obj.findAncestors(10);
obj.findAncestors(5);
obj.findAncestors(1);
obj.findAncestors(11);
obj.findAncestors(12);
}
main();```
```

#### Output

``````Ancestor of node 7 are  :  1  2  4
Ancestor of node 10 are  :  1  3  6  8
Ancestor of node 5 are  :  1  3
Ancestor of node 1 are  : No Ancestor
Ancestor of node 11 are  :  1  2  4  7
Ancestor of node 12 are  : Node not exist``````

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.