Print all internal nodes of a binary tree using stack
Internal node of tree is a parent node that contain at least one child element. Tree traversal method (Inorder preorder and postorder) are visit each node of binary tree. So we can modified this algorithm to check internal node of binary tree.
Here given code implementation process.
/*
C Program
Print all Internal nodes of a binary tree
By using of stack
*/
#include <stdio.h>
#include <stdlib.h>
//structure of Binary Tree node
struct Node
{
int data;
struct Node *left, *right;
};
struct MyStack
{
struct Node *element;
struct MyStack *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 MyStack element and return this reference
struct MyStack *push(struct Node *tree_node, struct MyStack *top)
{
struct MyStack *node = (struct MyStack *) malloc(sizeof(struct MyStack));
if (node != NULL)
{
//set pointer values
node->element = tree_node;
node->next = top;
}
else
{
printf("Memory Overflow\n");
exit(0); //Terminate program execution
}
return node;
}
//Remove a top node of stack
void pop(struct MyStack **top)
{
if ( *top != NULL)
{
struct MyStack *remove = *top;*top = remove->next;
remove->element = NULL;
remove->next = NULL;
//free the allocated memory of node
free(remove);
remove = NULL;
}
}
//print internal nodes of binary tree
void print_internal(struct Node *root)
{
if (root != NULL)
{
//Make few MyStack pointer
struct MyStack *top = NULL, *head = NULL;
struct Node *temp = root;
while (top != NULL || temp != NULL)
{
if (temp != NULL)
{
//When current temp node of tree is not NULL
//Check that whether node is internal node or not
if (temp->left != NULL || temp->right != NULL)
{
//When get a internal node
printf("%d ", temp->data);
}
//add tree node into stack
top = push(temp, top);
//visit left subtree
temp = temp->left;
}
else
{
//When current tree node is NULL
//Fetch a top element of stack
temp = top->element;
//remove stack element
pop( & top);
//visit right-subtree
temp = temp->right;
}
}
}
else
{
printf("Empty Linked List\n");
}
}
int main()
{
struct Node *root = NULL;
/*Make A Binary Tree
-----------------------
17
/ \
11 21
/ \ / \
1 39 10 9
/ \
40 2
*/
//Insertion of binary tree nodes
root = insert(17);
root->left = insert(11);
root->right = insert(21);
root->right->right = insert(9);
root->right->left = insert(10);
root->left->left = insert(1);
root->left->right = insert(39);
root->left->right->left = insert(40);
root->right->right->right = insert(2);
printf("Internal node is : ");
//Display Tree elements
print_internal(root);
return 0;
}Output
Internal node is : 17 11 39 21 9/*
Java Program
Print all Internal nodes of a binary tree
By Using Stack
*/
//Structure of Binary Tree node
class Node
{
public int data;
public Node left, right;
//make a tree node
public Node(int data)
{
//Assign field values
this.data = data;
this.left = null;
this.right = null;
}
}
//structure of stack Class
class Stack
{
public Node element;
public Stack next;
public Stack(Node element)
{
this.element = element;
this.next = null;
}
}
class BinaryTree
{
public Node root;
private Stack top;
public BinaryTree()
{
//set initial tree root to null
this.root = null;
this.top = null;
}
//print internal nodes of binary tree
public void print_internal()
{
if (this.root != null)
{
Node temp = this.root;
while (this.top != null || temp != null)
{
if (temp != null)
{
//When current temp node of tree is not NULL
//Check that whether node is internal node or not
if (temp.left != null || temp.right != null)
{
System.out.print(" " + temp.data + " ");
}
//add tree node into stack
this.push(temp);
//visit left subtree
temp = temp.left;
}
else
{
//When current tree node is NULL
//Fetch a top element of stack
temp = this.top.element;
//remove stack element
this.pop();
//visit right-subtree
temp = temp.right;
}
}
}
else
{
System.out.print("Empty Linked List\n");
}
}
//remove top element of stack
public void push(Node node)
{
Stack new_node = new Stack(node);
new_node.next = top;
top = new_node;
}
//remove top element of the stack
public void pop()
{
if (top != null)
{
Stack remove = top;
top = top.next;
remove.next = null;
remove.element = null;
remove = null;
}
}
public static void main(String[] args)
{
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
17
/ \
11 21
/ \ / \
1 39 10 9
/ \
40 2
*/
//insertion of binary Tree nodes
obj.root = new Node(17);
obj.root.left = new Node(11);
obj.root.right = new Node(21);
obj.root.right.right = new Node(9);
obj.root.right.right.right = new Node(2);
obj.root.right.left = new Node(10);
obj.root.left.left = new Node(1);
obj.root.left.right = new Node(39);
obj.root.left.right.left = new Node(40);
System.out.print("Internal node is : ");
//Display Tree elements
obj.print_internal();
}
}Output
Internal node is : 17 11 39 21 9//Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Print all Internal nodes of a binary tree
By Using Stack
*/
//Structure of Binary Tree node
class Node
{
public: int data;
Node * left, * right;
//make a tree node
Node(int data)
{
//Assign field values
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
//structure of stack Class
class Stack
{
public: Node * element;
Stack * next;
Stack(Node * element)
{
this->element = element;
this->next = NULL;
}
};
class BinaryTree
{
public: Node * root;
Stack * top;
BinaryTree()
{
//set initial tree root to null
this->root = NULL;
this->top = NULL;
}
//print internal nodes of binary tree
void print_internal()
{
if (this->root != NULL)
{
Node * temp = this->root;
while (this->top != NULL || temp != NULL)
{
if (temp != NULL)
{
//When current temp node of tree is not NULL
//Check that whether node is internal node or not
if (temp->left != NULL || temp->right != NULL)
{
cout << " " << temp->data << " ";
}
//add tree node into stack
this->push(temp);
//visit left subtree
temp = temp->left;
}
else
{
//When current tree node is NULL
//Fetch a top element of stack
temp = this->top->element;
//remove stack element
this->pop();
//visit right-subtree
temp = temp->right;
}
}
}
else
{
cout << "Empty Linked List\n";
}
}
//remove top element of stack
void push(Node * node)
{
Stack * new_node = new Stack(node);
new_node->next = this->top;
this->top = new_node;
}
//remove top element of the stack
void pop()
{
if (this->top != NULL)
{
Stack * remove = this->top;
this->top = this->top->next;
remove->next = NULL;
remove->element = NULL;
remove = NULL;
}
}
};
int main()
{
//Make object of Binary Tree
BinaryTree obj = BinaryTree();
/* Make A Binary Tree
-----------------------
17
/ \
11 21
/ \ / \
1 39 10 9
/ \
40 2
*/
//insertion of binary Tree nodes
obj.root = new Node(17);
obj.root->left = new Node(11);
obj.root->right = new Node(21);
obj.root->right->right = new Node(9);
obj.root->right->right->right = new Node(2);
obj.root->right->left = new Node(10);
obj.root->left->left = new Node(1);
obj.root->left->right = new Node(39);
obj.root->left->right->left = new Node(40);
cout << "Internal node is : ";
//Display Tree elements
obj.print_internal();
return 0;
}Output
Internal node is : 17 11 39 21 9/*
C# Program
Print all Internal nodes of a binary tree
By Using Stack
*/
//Include namespace system
using System;
//Structure of Binary Tree node
class Node
{
public int data;
public Node left, right;
//make a tree node
public Node(int data)
{
//Assign field values
this.data = data;
this.left = null;
this.right = null;
}
}
//structure of stack Class
class Stack
{
public Node element;
public Stack next;
public Stack(Node element)
{
this.element = element;
this.next = null;
}
}
class BinaryTree
{
public Node root;
private Stack top;
public BinaryTree()
{
//set initial tree root to null
this.root = null;
this.top = null;
}
//print internal nodes of binary tree
public void print_internal()
{
if (this.root != null)
{
Node temp = this.root;
while (this.top != null || temp != null)
{
if (temp != null)
{
//When current temp node of tree is not NULL
//Check that whether node is internal node or not
if (temp.left != null || temp.right != null)
{
Console.Write(" " + temp.data + " ");
}
//add tree node into stack
this.push(temp);
//visit left subtree
temp = temp.left;
}
else
{
//When current tree node is NULL
//Fetch a top element of stack
temp = this.top.element;
//remove stack element
this.pop();
//visit right-subtree
temp = temp.right;
}
}
}
else
{
Console.Write("Empty Linked List\n");
}
}
//remove top element of stack
public void push(Node node)
{
Stack new_node = new Stack(node);
new_node.next = top;
top = new_node;
}
//remove top element of the stack
public void pop()
{
if (top != null)
{
Stack remove = top;
top = top.next;
remove.next = null;
remove.element = null;
remove = null;
}
}
public static void Main(String[] args)
{
//Make object of Binary Tree
BinaryTree obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
17
/ \
11 21
/ \ / \
1 39 10 9
/ \
40 2
*/
//insertion of binary Tree nodes
obj.root = new Node(17);
obj.root.left = new Node(11);
obj.root.right = new Node(21);
obj.root.right.right = new Node(9);
obj.root.right.right.right = new Node(2);
obj.root.right.left = new Node(10);
obj.root.left.left = new Node(1);
obj.root.left.right = new Node(39);
obj.root.left.right.left = new Node(40);
Console.Write("Internal node is : ");
//Display Tree elements
obj.print_internal();
}
}Output
Internal node is : 17 11 39 21 9<?php
/*
Php Program
Print all Internal nodes of a binary tree
By Using Stack
*/
//Structure of Binary Tree node
class Node
{
public $data;
public $left;
public $right;
//make a tree node
function __construct($data)
{
//Assign field values
$this->data = $data;
$this->left = null;
$this->right = null;
}
}
//structure of stack Class
class Stack
{
public $element;
public $next;
function __construct($element)
{
$this->element = $element;
$this->next = null;
}
}
class BinaryTree
{
public $root;
public $top;
function __construct()
{
//set initial tree root to null
$this->root = null;
$this->top = null;
}
//print internal nodes of binary tree
public function print_internal()
{
if ($this->root != null)
{
$temp = $this->root;
while ($this->top != null || $temp != null)
{
if ($temp != null)
{
//When current temp node of tree is not NULL
//Check that whether node is internal node or not
if ($temp->left != null || $temp->right != null)
{
echo " ". $temp->data ." ";
}
//add tree node into stack
$this->push($temp);
//visit left subtree
$temp = $temp->left;
}
else
{
//When current tree node is NULL
//Fetch a top element of stack
$temp = $this->top->element;
//remove stack element
$this->pop();
//visit right-subtree
$temp = $temp->right;
}
}
}
else
{
echo "Empty Linked List\n";
}
}
//remove top element of stack
public function push($node)
{
$new_node = new Stack($node);
$new_node->next = $this->top;
$this->top = $new_node;
}
//remove top element of the stack
public function pop()
{
if ($this->top != null)
{
$remove = $this->top;
$this->top = $this->top->next;
$remove->next = null;
$remove->element = null;
$remove = null;
}
}
}
function main()
{
//Make object of Binary Tree
$obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
17
/ \
11 21
/ \ / \
1 39 10 9
/ \
40 2
*/
//insertion of binary Tree nodes
$obj->root = new Node(17);
$obj->root->left = new Node(11);
$obj->root->right = new Node(21);
$obj->root->right->right = new Node(9);
$obj->root->right->right->right = new Node(2);
$obj->root->right->left = new Node(10);
$obj->root->left->left = new Node(1);
$obj->root->left->right = new Node(39);
$obj->root->left->right->left = new Node(40);
echo "Internal node is : ";
//Display Tree elements
$obj->print_internal();
}
main();Output
Internal node is : 17 11 39 21 9/*
Node Js Program
Print all Internal nodes of a binary tree
By Using Stack
*/
//Binary Tree node
class Node
{
;
//make a tree node
constructor(data)
{
//Assign field values
this.data = data;
this.left = null;
this.right = null;
}
}
//structure of stack Class
class Stack
{
constructor(element)
{
this.element = element;
this.next = null;
}
}
class BinaryTree
{
constructor()
{
//set initial tree root to null
this.root = null;
this.top = null;
}
//print internal nodes of binary tree
print_internal()
{
if (this.root != null)
{
var temp = this.root;
while (this.top != null || temp != null)
{
if (temp != null)
{
//When current temp node of tree is not NULL
//Check that whether node is internal node or not
if (temp.left != null || temp.right != null)
{
process.stdout.write(" " + temp.data + " ");
}
//add tree node into stack
this.push(temp);
//visit left subtree
temp = temp.left;
}
else
{
//When current tree node is NULL
//Fetch a top element of stack
temp = this.top.element;
//remove stack element
this.pop();
//visit right-subtree
temp = temp.right;
}
}
}
else
{
process.stdout.write("Empty Linked List\n");
}
}
//remove top element of stack
push(node)
{
var new_node = new Stack(node);
new_node.next = this.top;
this.top = new_node;
}
//remove top element of the stack
pop()
{
if (this.top != null)
{
var remove = this.top;
this.top = this.top.next;
remove.next = null;
remove.element = null;
remove = null;
}
}
}
function main()
{
//Make object of Binary Tree
var obj = new BinaryTree();
/* Make A Binary Tree
-----------------------
17
/ \
11 21
/ \ / \
1 39 10 9
/ \
40 2
*/
//insertion of binary Tree nodes
obj.root = new Node(17);
obj.root.left = new Node(11);
obj.root.right = new Node(21);
obj.root.right.right = new Node(9);
obj.root.right.right.right = new Node(2);
obj.root.right.left = new Node(10);
obj.root.left.left = new Node(1);
obj.root.left.right = new Node(39);
obj.root.left.right.left = new Node(40);
process.stdout.write("Internal node is : ");
//Display Tree elements
obj.print_internal();
}
main();Output
Internal node is : 17 11 39 21 9# Python 3 Program
# Print all Internal nodes of a binary tree
# By Using Stack
# Binary Tree node
class Node :
# make a tree node
def __init__(self, data) :
# Assign field values
self.data = data
self.left = None
self.right = None
# structure of stack Class
class Stack :
def __init__(self, element) :
self.element = element
self.next = None
class BinaryTree :
def __init__(self) :
# set initial tree root to null
self.root = None
self.top = None
# print internal nodes of binary tree
def print_internal(self) :
if (self.root != None) :
temp = self.root
while (self.top != None or temp != None) :
if (temp != None) :
# When current temp node of tree is not NULL
# Check that whether node is internal node or not
if (temp.left != None or temp.right != None) :
print(" ", temp.data ," ", end = "")
# add tree node into stack
self.push(temp)
# visit left subtree
temp = temp.left
else :
# When current tree node is NULL
# Fetch a top element of stack
temp = self.top.element
# remove stack element
self.pop()
# visit right-subtree
temp = temp.right
else :
print("Empty Linked List\n", end = "")
# remove top element of stack
def push(self, node) :
new_node = Stack(node)
new_node.next = self.top
self.top = new_node
# remove top element of the stack
def pop(self) :
if (self.top != None) :
remove = self.top
self.top = self.top.next
remove.next = None
remove.element = None
remove = None
def main() :
# Make object of Binary Tree
obj = BinaryTree()
# Make A Binary Tree
# -----------------------
# 17
# / \
# 11 21
# / \ / \
# 1 39 10 9
# / \
# 40 2
#
# insertion of binary Tree nodes
obj.root = Node(17)
obj.root.left = Node(11)
obj.root.right = Node(21)
obj.root.right.right = Node(9)
obj.root.right.right.right = Node(2)
obj.root.right.left = Node(10)
obj.root.left.left = Node(1)
obj.root.left.right = Node(39)
obj.root.left.right.left = Node(40)
print("Internal node is : ", end = "")
# Display Tree elements
obj.print_internal()
if __name__ == "__main__": main()Output
Internal node is : 17 11 39 21 9/*
Scala Program
Print all Internal nodes of a binary tree
By Using Stack
*/
//Binary Tree node
class Node(var data: Int,
var left: Node,
var right: Node)
{
//make a tree node
def this(data: Int)
{
//Assign field values
this(data,null,null);
}
}
//structure of stack Class
class Stack(var element: Node,
var next: Stack)
{
def this(element: Node)
{
this(element,null);
}
}
class BinaryTree(var root: Node,
var top: Stack)
{
def this()
{
//set initial tree root to null
this(null,null);
}
//print internal nodes of binary tree
def print_internal(): Unit = {
if (this.root != null)
{
var temp: Node = this.root;
while (this.top != null || temp != null)
{
if (temp != null)
{
//When current temp node of tree is not NULL
//Check that whether node is internal node or not
if (temp.left != null || temp.right != null)
{
print(" " + temp.data + " ");
}
//add tree node into stack
this.push(temp);
//visit left subtree
temp = temp.left;
}
else
{
//When current tree node is NULL
//Fetch a top element of stack
temp = this.top.element;
//remove stack element
this.pop();
//visit right-subtree
temp = temp.right;
}
}
}
else
{
print("Empty Linked List\n");
}
}
//remove top element of stack
def push(node: Node): Unit = {
var new_node: Stack = new Stack(node);
new_node.next = top;
top = new_node;
}
//remove top element of the stack
def pop(): Unit = {
if (top != null)
{
var remove: Stack = top;
top = top.next;
remove.next = null;
remove.element = null;
remove = null;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
//Make object of Binary Tree
var obj: BinaryTree = new BinaryTree();
/* Make A Binary Tree
-----------------------
17
/ \
11 21
/ \ / \
1 39 10 9
/ \
40 2
*/
//insertion of binary Tree nodes
obj.root = new Node(17);
obj.root.left = new Node(11);
obj.root.right = new Node(21);
obj.root.right.right = new Node(9);
obj.root.right.right.right = new Node(2);
obj.root.right.left = new Node(10);
obj.root.left.left = new Node(1);
obj.root.left.right = new Node(39);
obj.root.left.right.left = new Node(40);
print("Internal node is : ");
//Display Tree elements
obj.print_internal();
}
}Output
Internal node is : 17 11 39 21 9/*
Swift Program
Print all Internal nodes of a binary tree
By Using Stack
*/
//Binary Tree node
class Node
{
var data: Int;
var left: Node? ;
var right: Node? ;
//make a tree node
init(_ data: Int)
{
//Assign field values
self.data = data;
self.left = nil;
self.right = nil;
}
}
//stack Class
class Stack
{
var element: Node? ;
var next: Stack? ;
init(_ element: Node? )
{
self.element = element;
self.next = nil;
}
}
class BinaryTree
{
var root: Node? ;
var top: Stack? ;
init()
{
//set initial tree root to null
self.root = nil;
self.top = nil;
}
//print internal nodes of binary tree
func print_internal()
{
if (self.root != nil)
{
var temp: Node? = self.root;
while (self.top != nil || temp != nil)
{
if (temp != nil)
{
//When current temp node of tree is not NULL
//Check that whether node is internal node or not
if (temp!.left != nil || temp!.right != nil)
{
print(" ", temp!.data ," ", terminator: "");
}
//add tree node into stack
self.push(temp);
//visit left subtree
temp = temp!.left;
}
else
{
//When current tree node is NULL
//Fetch a top element of stack
temp = self.top!.element;
//remove stack element
self.pop();
//visit right-subtree
temp = temp!.right;
}
}
}
else
{
print("Empty Linked List\n", terminator: "");
}
}
//remove top element of stack
func push(_ node: Node? )
{
let new_node: Stack? = Stack(node);
new_node!.next = self.top;
self.top = new_node;
}
//remove top element of the stack
func pop()
{
if (self.top != nil)
{
var remove: Stack? = self.top;
self.top = self.top!.next;
remove!.next = nil;
remove!.element = nil;
remove = nil;
}
}
}
func main()
{
//Make object of Binary Tree
let obj: BinaryTree = BinaryTree();
/* Make A Binary Tree
-----------------------
17
/ \
11 21
/ \ / \
1 39 10 9
/ \
40 2
*/
//insertion of binary Tree nodes
obj.root = Node(17);
obj.root!.left = Node(11);
obj.root!.right = Node(21);
obj.root!.right!.right = Node(9);
obj.root!.right!.right!.right = Node(2);
obj.root!.right!.left = Node(10);
obj.root!.left!.left = Node(1);
obj.root!.left!.right = Node(39);
obj.root!.left!.right!.left = Node(40);
print("Internal node is : ", terminator: "");
//Display Tree elements
obj.print_internal();
}
main();Output
Internal node is : 17 11 39 21 9# Ruby Program
# Print all Internal nodes of a binary tree
# By Using Stack
# Binary Tree node
class Node
# Define the accessor and reader of class Node
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
# make a tree node
def initialize(data)
# Assign field values
self.data = data
self.left = nil
self.right = nil
end
end
# structure of stack Class
class Stack
# Define the accessor and reader of class Stack
attr_reader :element, :next
attr_accessor :element, :next
def initialize(element)
self.element = element
self.next = nil
end
end
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root, :top
attr_accessor :root, :top
def initialize()
# set initial tree root to null
self.root = nil
self.top = nil
end
# print internal nodes of binary tree
def print_internal()
if (self.root != nil)
temp = self.root
while (self.top != nil || temp != nil)
if (temp != nil)
# When current temp node of tree is not NULL
# Check that whether node is internal node or not
if (temp.left != nil || temp.right != nil)
print(" ", temp.data ," ")
end
# add tree node into stack
self.push(temp)
# visit left subtree
temp = temp.left
else
# When current tree node is NULL
# Fetch a top element of stack
temp = self.top.element
# remove stack element
self.pop()
# visit right-subtree
temp = temp.right
end
end
else
print("Empty Linked List\n")
end
end
# remove top element of stack
def push(node)
new_node = Stack.new(node)
new_node.next = @top
@top = new_node
end
# remove top element of the stack
def pop()
if (@top != nil)
remove = @top
@top = @top.next
remove.next = nil
remove.element = nil
remove = nil
end
end
end
def main()
# Make object of Binary Tree
obj = BinaryTree.new()
# Make A Binary Tree
# -----------------------
# 17
# / \
# 11 21
# / \ / \
# 1 39 10 9
# / \
# 40 2
#
# insertion of binary Tree nodes
obj.root = Node.new(17)
obj.root.left = Node.new(11)
obj.root.right = Node.new(21)
obj.root.right.right = Node.new(9)
obj.root.right.right.right = Node.new(2)
obj.root.right.left = Node.new(10)
obj.root.left.left = Node.new(1)
obj.root.left.right = Node.new(39)
obj.root.left.right.left = Node.new(40)
print("Internal node is : ")
# Display Tree elements
obj.print_internal()
end
main()Output
Internal node is : 17 11 39 21 9 
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