Skip to main content

Print all internal nodes of a binary tree using stack

The problem is to print all the internal nodes of a binary tree using a stack-based approach. In a binary tree, an internal node is a node that has at least one child (either left or right child). The internal nodes are those nodes that are not leaf nodes.

Example

Consider the binary tree:

print internal nodes in binary tree

The internal nodes in this tree are: 17, 11, 39, 21, and 9.

Idea to Solve the Problem

To print all the internal nodes of the binary tree using a stack, we will perform an iterative in-order traversal of the tree. During the traversal, we will check if the current node has at least one child. If it does, it is an internal node, and we will print its value.

Algorithm

  1. Start with the root of the binary tree.
  2. Create an empty stack top to hold the nodes during the traversal.
  3. Initialize a temporary node temp with the root of the tree.
  4. Repeat the following steps until temp becomes null and the stack is empty: a. If temp is not null, push temp into the stack, and set temp to its left child. b. If temp is null, pop the top node from the stack, print its value if it has at least one child (internal node), and set temp to its right child.
  5. Finish the traversal when temp becomes null and the stack is empty.

Pseudocode

FUNCTION print_internal():
    IF the root of the binary tree is not null:
        INITIALIZE a temporary node temp to the root of the binary tree
        WHILE temp is not null OR the stack top is not null:
            IF temp is not null:
                IF temp has at least one child (internal node):
                    PRINT temp.data
                PUSH temp into the stack
                SET temp to its left child
            ELSE:
                SET temp to the right child of the top node in the stack
                POP the top node from the stack

FUNCTION push(node):
    CREATE a new Stack node with the given node
    SET new Stack node's next to the current top of the stack
    SET top to the new Stack node

FUNCTION pop():
    IF the top of the stack is not null:
        SET remove to the top of the stack
        SET top to the next node of the top
        SET remove's next and element to null
        SET remove to null

FUNCTION main():
    CREATE a new BinaryTree object obj
    CONSTRUCT the binary tree as shown in the example
    CALL obj.print_internal()

Code Solution

/*
 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

Time Complexity Analysis

The time complexity of the print_internal function is O(n), where n is the number of nodes in the binary tree. The reason for this is that each node is visited once during the traversal.

Output Explanation

The output shows the internal nodes of the binary tree. For the example tree provided in the code, the output is "Internal node is: 17 11 39 21 9", indicating that these nodes are the internal nodes of the binary tree.

Last updated on by Kalkicode




Comment

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