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;
stack_node->next = head;
} 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;
showPath( *head);
return;
}
//Add element into stack
*head = push(root, *head);
getAncestors(root->left, head, status, node);
getAncestors(root->right, head, status, node);
pop(head);
}
}
void findAncestors(struct Node *root, int node) {
struct Stack *head = NULL;
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
*/
//Add element
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;
MyStack(Node *new_node, MyStack *head) {
this->element = new_node;
this->next = head;
}
};
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;
}
}
void showPath(MyStack *head) {
if (head != NULL) {
this->showPath(head->next);
cout << " " << head->element->data;
}
}
void getAncestors(Node *head, int node) {
if (head != NULL && this->flag == 0) {
if (head->data == node) {
if (this->top == NULL) {
this->flag = -1;
return;
}
this->flag = 1;
this->showPath(this->top);
return;
}
this->push(head);
this->getAncestors(head->left, node);
this->getAncestors(head->right, node);
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;
next = head;
}
}
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;
}
}
public void showPath(MyStack head) {
if (head != null) {
showPath(head.next);
System.out.print(" " + head.element.data);
}
}
//Get all Ancestors of given node element
public void getAncestors(Node head, int node) {
if (head != null && this.flag == 0) {
if (head.data == node) {
if (top == null) {
//When no Ancestor
this.flag = -1;
return;
}
this.flag = 1;
showPath(top);
return;
}
//Add element into MyStack
push(head);
getAncestors(head.left, node);
getAncestors(head.right, node);
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
*/
//Add element
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;
next = head;
}
}
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;
}
}
public void showPath(MyStack head) {
if (head != null) {
showPath(head.next);
Console.Write(" " + head.element.data);
}
}
//Get all Ancestors of given node element
public void getAncestors(Node head, int node) {
if (head != null && this.flag == 0) {
if (head.data == node) {
if (top == null) {
//When no Ancestor
this.flag = -1;
return;
}
this.flag = 1;
showPath(top);
return;
}
//Add element into MyStack
push(head);
getAncestors(head.left, node);
getAncestors(head.right, node);
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
*/
//Add element
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 :
def __init__(self, new_node, head) :
self.element = new_node;
self.next = head;
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;
def showPath(self, head) :
if (head != None) :
self.showPath(head.next);
print(head.element.data,end=" ");
def getAncestors(self, head, node) :
if (head != None and self.flag == 0) :
if (head.data == node) :
if (self.top == None) :
self.flag = -1;
return;
self.flag = 1;
self.showPath(self.top);
return;
self.push(head);
self.getAncestors(head.left, node);
self.getAncestors(head.right, node);
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_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(value)
@data = value
@left = @right = nil
end
end
class MyStack
attr_reader :element, :next
attr_accessor :element, :next
def initialize(new_node, head)
@element = new_node
@next = head
end
end
class BinaryTree
attr_reader :root, :top, :flag
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
def showPath(head)
if (head != nil)
self.showPath(head.next)
print(" ", head.element.data)
end
end
def getAncestors(head, node)
if (head != nil and self.flag == 0)
if (head.data == node)
if (@top == nil)
self.flag = -1
return
end
self.flag = 1
self.showPath(@top)
return
end
self.push(head)
self.getAncestors(head.left, node)
self.getAncestors(head.right, node)
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;
function __construct($new_node, $head) {
$this->element = $new_node;
$this->next = $head;
}
}
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;
}
}
public function showPath($head) {
if ($head != null) {
$this->showPath($head->next);
echo(" ". $head->element->data);
}
}
public function getAncestors($head, $node) {
if ($head != null && $this->flag == 0) {
if ($head->data == $node) {
if ($this->top == null) {
$this->flag = -1;
return;
}
$this->flag = 1;
$this->showPath($this->top);
return;
}
$this->push($head);
$this->getAncestors($head->left, $node);
$this->getAncestors($head->right, $node);
$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 {
constructor(new_node, head) {
this.element = new_node;
this.next = head;
}
}
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;
}
}
showPath(head) {
if (head != null) {
this.showPath(head.next);
process.stdout.write(" " + head.element.data);
}
}
getAncestors(head, node) {
if (head != null && this.flag == 0) {
if (head.data == node) {
if (this.top == null) {
this.flag = -1;
return;
}
this.flag = 1;
this.showPath(this.top);
return;
}
this.push(head);
this.getAncestors(head.left, node);
this.getAncestors(head.right, node);
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;
self.next = head;
}
}
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? ) {
if (head != nil) {
self.showPath(head!.next);
let temp: Node? = head!.element;
print(temp!.data, terminator : " ");
}
}
func getAncestors(_ head: Node? , _ node : Int) {
if (head != nil && self.flag == 0) {
if (head!.data == node) {
if (self.top == nil) {
self.flag = -1;
return;
}
self.flag = 1;
self.showPath(self.top);
return;
}
self.push(head);
self.getAncestors(head!.left, node);
self.getAncestors(head!.right, node);
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.
New Comment