Print the boundary nodes in each level of the binary tree using queue
Here given code implementation process.
// C program
// Print the boundary nodes in each level of the binary tree using queue
#include <stdio.h>
#include <stdlib.h>
// Node of binary tree
struct TreeNode
{
int data;
struct TreeNode *left, *right;
};
struct MyQueue
{
int level;
struct TreeNode *element;
struct MyQueue *next;
};
// Create a binary tree nodes and node fields (data,pointer)
// And returning the reference of newly nodes
struct TreeNode *insert(int data)
{
// Create dynamic memory of tree node
struct TreeNode *new_node =
(struct TreeNode *) malloc(sizeof(struct TreeNode));
if (new_node != NULL)
{
// Set node value
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
}
else
{
printf("Memory Overflow\n");
}
// return reference
return new_node;
}
// Create a queue node and returns this node
struct MyQueue *enqueue(struct TreeNode *tree_node)
{
// Make a new Queue node
struct MyQueue *new_node =
(struct MyQueue *) malloc(sizeof(struct MyQueue));
if (new_node != NULL)
{
// Set node values
new_node->element = tree_node;
new_node->next = NULL;
}
else
{
printf("Memory Overflow\n");
}
return new_node;
}
// Remove a queue elements
void dequeue(struct MyQueue **front)
{
if ( *front != NULL)
{
struct MyQueue *remove = *front;
//Visit to next node
*front = remove->next;
remove->element = NULL;
remove->next = NULL;
//free node
free(remove);
remove = NULL;
}
}
void findBoundaryLevelNode(struct TreeNode *root)
{
if (root != NULL)
{
// make a queue pointers
struct MyQueue *front = NULL, *tail = NULL;
// Get first node of tree
front = enqueue(root);
// Assume first node level is zero
// Start level of first node is zero
front->level = 0;
//Set tail node to first node
tail = front;
// Define tree variables
struct TreeNode *node = NULL;
struct TreeNode *first = NULL;
struct TreeNode *last = NULL;
int level = -1;
// Traversal tree elements in level order
while (front != NULL)
{
// Tree node
node = front->element;
if (node->left != NULL)
{
// Add new left child node
tail->next = enqueue(node->left);
tail->next->level = front->level + 1;
tail = tail->next;
}
if (node->right != NULL)
{
// Add new right child node
tail->next = enqueue(node->right);
tail->next->level = front->level + 1;
tail = tail->next;
}
if (front->level != level)
{
level = front->level;
if (last != NULL && last != first)
{
// Print the last node in the above level
printf(" %d", last->data);
}
first = node;
// Print first node in current level
printf("\n %d", node->data);
}
last = node;
// Remove queue node
dequeue( & front);
}
if (last != NULL && last != first)
{
// Print the last node in the above level
printf(" %d\n", last->data);
}
tail = NULL;
}
else
{
printf("\nEmpty Tree\n");
}
}
int main()
{
struct TreeNode *root = NULL;
/*
Binary Tree
-----------------------
10
/ \
2 13
/ / \ -
4 9 5
/ \ \ \ -
7 3 6 11
/ \ / \ - -
2 8 -3 12
/ \
-1 9
-
------------------------
*/
//Add node
root = insert(10);
root->left = insert(2);
root->right = insert(13);
root->right->right = insert(5);
root->right->left = insert(9);
root->left->left = insert(4);
root->left->left->left = insert(7);
root->left->left->right = insert(3);
root->right->left->right = insert(6);
root->right->right->right = insert(11);
root->right->right->right->right = insert(12);
root->right->right->right->left = insert(-3);
root->left->left->right->left = insert(2);
root->left->left->right->right = insert(8);
root->left->left->right->right->left = insert(-1);
root->left->left->right->right->right = insert(9);
/*
Boundary Nodes
------------------------------
↓
10
/ \
→ 2 13 ←
/ / \ -
→ 4 9 5 ←
/ \ \ \ -
→ 7 3 6 11 ←
/ \ / \ - -
→ 2 8 -3 12 ←
/ \
→ -1 9 ←
-
---------------------------------
*/
findBoundaryLevelNode(root);
return 0;
}
Output
10
2 13
4 5
7 11
2 12
-1 9
/*
Java Program
Print the boundary nodes in each level of the binary tree using queue
*/
class TreeNode
{
// Data value
public int data;
// Indicates left and right subtree
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class QNode
{
public TreeNode k;
public QNode next;
public int level;
public QNode(TreeNode k)
{
this.k = k;
this.next = null;
this.level = 0;
}
}
// Define custom queue class
class MyQueue
{
public QNode front;
public QNode rear;
public int size;
public MyQueue()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a new node at last of queue
public void enqueue(TreeNode data)
{
QNode node = new QNode(data);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last level
this.rear.next = node;
}
this.size++;
this.rear = node;
}
// Delete front node of queue
public void dequeue()
{
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
this.size--;
}
}
public int isSize()
{
return this.size;
}
public boolean isEmpty()
{
if (this.isSize() == 0)
{
return true;
}
return false;
}
public QNode peek()
{
if (this.isSize() == 0)
{
return null;
}
else
{
return this.front;
}
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial value
this.root = null;
}
public void findBoundaryLevelNode()
{
if (this.root != null)
{
MyQueue q = new MyQueue();
// Add first node
q.enqueue(this.root);
// Define tree variables
TreeNode node = null;
TreeNode first = null;
TreeNode last = null;
int level = -1;
// Traversal tree elements in level order
while (q.isEmpty() == false)
{
// Tree node
node = q.peek().k;
if (node.left != null)
{
// Add new left child node
q.enqueue(node.left);
q.rear.level = q.front.level + 1;
}
if (node.right != null)
{
// Add new right child node
q.enqueue(node.right);
q.rear.level = q.front.level + 1;
}
if (q.front.level != level)
{
level = q.front.level;
if (last != null && last != first)
{
// Print the last node in the above level
System.out.print(" " + last.data );
}
first = node;
// Print first node in current level
System.out.print("\n " + node.data );
}
last = node;
// Remove queue node
q.dequeue();
}
if (last != null && last != first)
{
// Print the last node in the above level
System.out.println(" " + last.data );
}
}
else
{
System.out.print("\nEmpty Tree\n");
}
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
Binary Tree
-----------------------
10
/ \
2 13
/ / \
4 9 5
/ \ \ \
7 3 6 11
/ \ / \
2 8 -3 12
/ \
-1 9
--------------------
*/
//Add node
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(13);
tree.root.right.right = new TreeNode(5);
tree.root.right.left = new TreeNode(9);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(7);
tree.root.left.left.right = new TreeNode(3);
tree.root.right.left.right = new TreeNode(6);
tree.root.right.right.right = new TreeNode(11);
tree.root.right.right.right.right = new TreeNode(12);
tree.root.right.right.right.left = new TreeNode(-3);
tree.root.left.left.right.left = new TreeNode(2);
tree.root.left.left.right.right = new TreeNode(8);
tree.root.left.left.right.right.left = new TreeNode(-1);
tree.root.left.left.right.right.right = new TreeNode(9);
/*
Boundary Nodes
--------------------------
↓
10
/ \
→ 2 13 ←
/ / \
→ 4 9 5 ←
/ \ \ \
→ 7 3 6 11 ←
/ \ / \
→ 2 8 -3 12 ←
/ \
→ -1 9 ←
---------------------------
*/
tree.findBoundaryLevelNode();
}
}
Output
10
2 13
4 5
7 11
2 12
-1 9
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Print the boundary nodes in each level of the binary tree using queue
*/
class TreeNode
{
public:
// Data value
int data;
// Indicates left and right subtree
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class QNode
{
public:
TreeNode *k;
QNode *next;
int level;
QNode(TreeNode *k)
{
this->k = k;
this->next = NULL;
this->level = 0;
}
};
// Define custom queue class
class MyQueue
{
public:
QNode *front;
QNode *rear;
int size;
MyQueue()
{
this->front = NULL;
this->rear = NULL;
this->size = 0;
}
// Add a new node at last of queue
void enqueue(TreeNode *data)
{
QNode *node = new QNode(data);
if (this->front == NULL)
{
// When first node of queue
this->front = node;
}
else
{
// Add node at last level
this->rear->next = node;
}
this->size++;
this->rear = node;
}
// Delete front node of queue
void dequeue()
{
if (this->front != NULL)
{
QNode *temp = this->front;
if (this->rear == this->front)
{
this->rear = NULL;
this->front = NULL;
}
else
{
this->front = this->front->next;
}
delete temp;
temp = NULL;
this->size--;
}
}
int isSize()
{
return this->size;
}
bool isEmpty()
{
if (this->isSize() == 0)
{
return true;
}
return false;
}
QNode *peek()
{
if (this->isSize() == 0)
{
return NULL;
}
else
{
return this->front;
}
}
};
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
this->root = NULL;
}
void findBoundaryLevelNode()
{
if (this->root != NULL)
{
MyQueue *q = new MyQueue();
// Add first node
q->enqueue(this->root);
// Define tree variables
TreeNode *node = NULL;
TreeNode *first = NULL;
TreeNode *last = NULL;
int level = -1;
// Traversal tree elements in level order
while (q->isEmpty() == false)
{
// Tree node
node = q->peek()->k;
if (node->left != NULL)
{
// Add new left child node
q->enqueue(node->left);
q->rear->level = q->front->level + 1;
}
if (node->right != NULL)
{
// Add new right child node
q->enqueue(node->right);
q->rear->level = q->front->level + 1;
}
if (q->front->level != level)
{
level = q->front->level;
if (last != NULL && last != first)
{
// Print the last node in the above level
cout << " " << last->data;
}
first = node;
// Print first node in current level
cout << "\n " << node->data;
}
last = node;
// Remove queue node
q->dequeue();
}
if (last != NULL && last != first)
{
// Print the last node in the above level
cout << " " << last->data << endl;
}
}
else
{
cout << "\nEmpty Tree\n";
}
}
};
int main()
{
BinaryTree *tree = new BinaryTree();
/*
Binary Tree
-----------------------
10
/ \
2 13
/ / \
4 9 5
/ \ \ \
7 3 6 11
/ \ / \
2 8 -3 12
/ \
-1 9
--------------------
*/
//Add node
tree->root = new TreeNode(10);
tree->root->left = new TreeNode(2);
tree->root->right = new TreeNode(13);
tree->root->right->right = new TreeNode(5);
tree->root->right->left = new TreeNode(9);
tree->root->left->left = new TreeNode(4);
tree->root->left->left->left = new TreeNode(7);
tree->root->left->left->right = new TreeNode(3);
tree->root->right->left->right = new TreeNode(6);
tree->root->right->right->right = new TreeNode(11);
tree->root->right->right->right->right = new TreeNode(12);
tree->root->right->right->right->left = new TreeNode(-3);
tree->root->left->left->right->left = new TreeNode(2);
tree->root->left->left->right->right = new TreeNode(8);
tree->root->left->left->right->right->left = new TreeNode(-1);
tree->root->left->left->right->right->right = new TreeNode(9);
/*
Boundary Nodes
--------------------------
↓
10
/ \
→ 2 13 ←
/ / \
→ 4 9 5 ←
/ \ \ \
→ 7 3 6 11 ←
/ \ / \
→ 2 8 -3 12 ←
/ \
→ -1 9 ←
---------------------------
*/
tree->findBoundaryLevelNode();
return 0;
}
Output
10
2 13
4 5
7 11
2 12
-1 9
package main
import "fmt"
/*
Go Program
Print the boundary nodes in each level of the binary tree using queue
*/
type TreeNode struct {
// Data value
data int
// Indicates left and right subtree
left * TreeNode
right * TreeNode
}
func getTreeNode(data int) * TreeNode {
var me *TreeNode = &TreeNode {}
me.data = data
me.left = nil
me.right = nil
return me
}
type QNode struct {
k * TreeNode
next * QNode
level int
}
func getQNode(k * TreeNode) * QNode {
var me *QNode = &QNode {}
me.k = k
me.next = nil
me.level = 0
return me
}
// Define custom queue class
type MyQueue struct {
front * QNode
rear * QNode
size int
}
func getMyQueue() * MyQueue {
var me *MyQueue = &MyQueue {}
me.front = nil
me.rear = nil
me.size = 0
return me
}
// Add a new node at last of queue
func(this *MyQueue) enqueue(data * TreeNode) {
var node * QNode = getQNode(data)
if this.front == nil {
// When first node of queue
this.front = node
} else {
// Add node at last level
this.rear.next = node
}
this.size++
this.rear = node
}
// Delete front node of queue
func(this *MyQueue) dequeue() {
if this.front != nil {
if this.rear == this.front {
this.rear = nil
this.front = nil
} else {
this.front = this.front.next
}
this.size--
}
}
func(this MyQueue) isSize() int {
return this.size
}
func(this MyQueue) isEmpty() bool {
if this.isSize() == 0 {
return true
}
return false
}
func(this MyQueue) peek() * QNode {
if this.isSize() == 0 {
return nil
} else {
return this.front
}
}
type BinaryTree struct {
root * TreeNode
}
func getBinaryTree() * BinaryTree {
var me *BinaryTree = &BinaryTree {}
// Set initial value
me.root = nil
return me
}
func(this BinaryTree) findBoundaryLevelNode() {
if this.root != nil {
var q * MyQueue = getMyQueue()
// Add first node
q.enqueue(this.root)
// Define tree variables
var node * TreeNode = nil
var first * TreeNode = nil
var last * TreeNode = nil
var level int = -1
// Traversal tree elements in level order
for (q.isEmpty() == false) {
// Tree node
node = q.peek().k
if node.left != nil {
// Add new left child node
q.enqueue(node.left)
q.rear.level = q.front.level + 1
}
if node.right != nil {
// Add new right child node
q.enqueue(node.right)
q.rear.level = q.front.level + 1
}
if q.front.level != level {
level = q.front.level
if last != nil && last != first {
// Print the last node in the above level
fmt.Print(" ", last.data)
}
first = node
// Print first node in current level
fmt.Print("\n ", node.data)
}
last = node
// Remove queue node
q.dequeue()
}
if last != nil && last != first {
// Print the last node in the above level
fmt.Println(" ", last.data)
}
} else {
fmt.Print("\nEmpty Tree\n")
}
}
func main() {
var tree * BinaryTree = getBinaryTree()
/*
Binary Tree
-----------------------
10
/ \
2 13
/ / \
4 9 5
/ \ \ \
7 3 6 11
/ \ / \
2 8 -3 12
/ \
-1 9
--------------------
*/
//Add node
tree.root = getTreeNode(10)
tree.root.left = getTreeNode(2)
tree.root.right = getTreeNode(13)
tree.root.right.right = getTreeNode(5)
tree.root.right.left = getTreeNode(9)
tree.root.left.left = getTreeNode(4)
tree.root.left.left.left = getTreeNode(7)
tree.root.left.left.right = getTreeNode(3)
tree.root.right.left.right = getTreeNode(6)
tree.root.right.right.right = getTreeNode(11)
tree.root.right.right.right.right = getTreeNode(12)
tree.root.right.right.right.left = getTreeNode(-3)
tree.root.left.left.right.left = getTreeNode(2)
tree.root.left.left.right.right = getTreeNode(8)
tree.root.left.left.right.right.left = getTreeNode(-1)
tree.root.left.left.right.right.right = getTreeNode(9)
/*
Boundary Nodes
--------------------------
↓
10
/ \
→ 2 13 ←
/ / \
→ 4 9 5 ←
/ \ \ \
→ 7 3 6 11 ←
/ \ / \
→ 2 8 -3 12 ←
/ \
→ -1 9 ←
---------------------------
*/
tree.findBoundaryLevelNode()
}
Output
10
2 13
4 5
7 11
2 12
-1 9
// Include namespace system
using System;
/*
Csharp Program
Print the boundary nodes in each level of the binary tree using queue
*/
public class TreeNode
{
// Data value
public int data;
// Indicates left and right subtree
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
public class QNode
{
public TreeNode k;
public QNode next;
public int level;
public QNode(TreeNode k)
{
this.k = k;
this.next = null;
this.level = 0;
}
}
// Define custom queue class
public class MyQueue
{
public QNode front;
public QNode rear;
public int size;
public MyQueue()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a new node at last of queue
public void enqueue(TreeNode data)
{
QNode node = new QNode(data);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last level
this.rear.next = node;
}
this.size++;
this.rear = node;
}
// Delete front node of queue
public void dequeue()
{
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
this.size--;
}
}
public int isSize()
{
return this.size;
}
public Boolean isEmpty()
{
if (this.isSize() == 0)
{
return true;
}
return false;
}
public QNode peek()
{
if (this.isSize() == 0)
{
return null;
}
else
{
return this.front;
}
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial value
this.root = null;
}
public void findBoundaryLevelNode()
{
if (this.root != null)
{
MyQueue q = new MyQueue();
// Add first node
q.enqueue(this.root);
// Define tree variables
TreeNode node = null;
TreeNode first = null;
TreeNode last = null;
int level = -1;
// Traversal tree elements in level order
while (q.isEmpty() == false)
{
// Tree node
node = q.peek().k;
if (node.left != null)
{
// Add new left child node
q.enqueue(node.left);
q.rear.level = q.front.level + 1;
}
if (node.right != null)
{
// Add new right child node
q.enqueue(node.right);
q.rear.level = q.front.level + 1;
}
if (q.front.level != level)
{
level = q.front.level;
if (last != null && last != first)
{
// Print the last node in the above level
Console.Write(" " + last.data);
}
first = node;
// Print first node in current level
Console.Write("\n " + node.data);
}
last = node;
// Remove queue node
q.dequeue();
}
if (last != null && last != first)
{
// Print the last node in the above level
Console.WriteLine(" " + last.data);
}
}
else
{
Console.Write("\nEmpty Tree\n");
}
}
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
Binary Tree
-----------------------
10
/ \
2 13
/ / \
4 9 5
/ \ \ \
7 3 6 11
/ \ / \
2 8 -3 12
/ \
-1 9
--------------------
*/
//Add node
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(13);
tree.root.right.right = new TreeNode(5);
tree.root.right.left = new TreeNode(9);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(7);
tree.root.left.left.right = new TreeNode(3);
tree.root.right.left.right = new TreeNode(6);
tree.root.right.right.right = new TreeNode(11);
tree.root.right.right.right.right = new TreeNode(12);
tree.root.right.right.right.left = new TreeNode(-3);
tree.root.left.left.right.left = new TreeNode(2);
tree.root.left.left.right.right = new TreeNode(8);
tree.root.left.left.right.right.left = new TreeNode(-1);
tree.root.left.left.right.right.right = new TreeNode(9);
/*
Boundary Nodes
--------------------------
↓
10
/ \
→ 2 13 ←
/ / \
→ 4 9 5 ←
/ \ \ \
→ 7 3 6 11 ←
/ \ / \
→ 2 8 -3 12 ←
/ \
→ -1 9 ←
---------------------------
*/
tree.findBoundaryLevelNode();
}
}
Output
10
2 13
4 5
7 11
2 12
-1 9
<?php
/*
Php Program
Print the boundary nodes in each level of the binary tree using queue
*/
class TreeNode
{
// Data value
public $data;
// Indicates left and right subtree
public $left;
public $right;
public function __construct($data)
{
$this->data = $data;
$this->left = NULL;
$this->right = NULL;
}
}
class QNode
{
public $k;
public $next;
public $level;
public function __construct($k)
{
$this->k = $k;
$this->next = NULL;
$this->level = 0;
}
}
// Define custom queue class
class MyQueue
{
public $front;
public $rear;
public $size;
public function __construct()
{
$this->front = NULL;
$this->rear = NULL;
$this->size = 0;
}
// Add a new node at last of queue
public function enqueue($data)
{
$node = new QNode($data);
if ($this->front == NULL)
{
// When first node of queue
$this->front = $node;
}
else
{
// Add node at last level
$this->rear->next = $node;
}
$this->size++;
$this->rear = $node;
}
// Delete front node of queue
public function dequeue()
{
if ($this->front != NULL)
{
if ($this->rear == $this->front)
{
$this->rear = NULL;
$this->front = NULL;
}
else
{
$this->front = $this->front->next;
}
$this->size--;
}
}
public function isSize()
{
return $this->size;
}
public function isEmpty()
{
if ($this->isSize() == 0)
{
return true;
}
return false;
}
public function peek()
{
if ($this->isSize() == 0)
{
return NULL;
}
else
{
return $this->front;
}
}
}
class BinaryTree
{
public $root;
public function __construct()
{
$this->root = NULL;
}
public function findBoundaryLevelNode()
{
if ($this->root != NULL)
{
$q = new MyQueue();
// Add first node
$q->enqueue($this->root);
// Define tree variables
$node = NULL;
$first = NULL;
$last = NULL;
$level = -1;
// Traversal tree elements in level order
while ($q->isEmpty() == false)
{
// Tree node
$node = $q->peek()->k;
if ($node->left != NULL)
{
// Add new left child node
$q->enqueue($node->left);
$q->rear->level = $q->front->level + 1;
}
if ($node->right != NULL)
{
// Add new right child node
$q->enqueue($node->right);
$q->rear->level = $q->front->level + 1;
}
if ($q->front->level != $level)
{
$level = $q->front->level;
if ($last != NULL && $last != $first)
{
// Print the last node in the above level
echo(" ".$last->data);
}
$first = $node;
// Print first node in current level
echo("\n ".$node->data);
}
$last = $node;
// Remove queue node
$q->dequeue();
}
if ($last != NULL && $last != $first)
{
// Print the last node in the above level
echo(" ".$last->data.
"\n");
}
}
else
{
echo("\nEmpty Tree\n");
}
}
}
function main()
{
$tree = new BinaryTree();
/*
Binary Tree
-----------------------
10
/ \
2 13
/ / \
4 9 5
/ \ \ \
7 3 6 11
/ \ / \
2 8 -3 12
/ \
-1 9
--------------------
*/
//Add node
$tree->root = new TreeNode(10);
$tree->root->left = new TreeNode(2);
$tree->root->right = new TreeNode(13);
$tree->root->right->right = new TreeNode(5);
$tree->root->right->left = new TreeNode(9);
$tree->root->left->left = new TreeNode(4);
$tree->root->left->left->left = new TreeNode(7);
$tree->root->left->left->right = new TreeNode(3);
$tree->root->right->left->right = new TreeNode(6);
$tree->root->right->right->right = new TreeNode(11);
$tree->root->right->right->right->right = new TreeNode(12);
$tree->root->right->right->right->left = new TreeNode(-3);
$tree->root->left->left->right->left = new TreeNode(2);
$tree->root->left->left->right->right = new TreeNode(8);
$tree->root->left->left->right->right->left = new TreeNode(-1);
$tree->root->left->left->right->right->right = new TreeNode(9);
/*
Boundary Nodes
--------------------------
↓
10
/ \
→ 2 13 ←
/ / \
→ 4 9 5 ←
/ \ \ \
→ 7 3 6 11 ←
/ \ / \
→ 2 8 -3 12 ←
/ \
→ -1 9 ←
---------------------------
*/
$tree->findBoundaryLevelNode();
}
main();
Output
10
2 13
4 5
7 11
2 12
-1 9
/*
Node JS Program
Print the boundary nodes in each level of the binary tree using queue
*/
class TreeNode
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class QNode
{
constructor(k)
{
this.k = k;
this.next = null;
this.level = 0;
}
}
// Define custom queue class
class MyQueue
{
constructor()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a new node at last of queue
enqueue(data)
{
var node = new QNode(data);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last level
this.rear.next = node;
}
this.size++;
this.rear = node;
}
// Delete front node of queue
dequeue()
{
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
this.size--;
}
}
isSize()
{
return this.size;
}
isEmpty()
{
if (this.isSize() == 0)
{
return true;
}
return false;
}
peek()
{
if (this.isSize() == 0)
{
return null;
}
else
{
return this.front;
}
}
}
class BinaryTree
{
constructor()
{
this.root = null;
}
findBoundaryLevelNode()
{
if (this.root != null)
{
var q = new MyQueue();
// Add first node
q.enqueue(this.root);
// Define tree variables
var node = null;
var first = null;
var last = null;
var level = -1;
// Traversal tree elements in level order
while (q.isEmpty() == false)
{
// Tree node
node = q.peek().k;
if (node.left != null)
{
// Add new left child node
q.enqueue(node.left);
q.rear.level = q.front.level + 1;
}
if (node.right != null)
{
// Add new right child node
q.enqueue(node.right);
q.rear.level = q.front.level + 1;
}
if (q.front.level != level)
{
level = q.front.level;
if (last != null && last != first)
{
// Print the last node in the above level
process.stdout.write(" " + last.data);
}
first = node;
// Print first node in current level
process.stdout.write("\n " + node.data);
}
last = node;
// Remove queue node
q.dequeue();
}
if (last != null && last != first)
{
// Print the last node in the above level
console.log(" " + last.data);
}
}
else
{
process.stdout.write("\nEmpty Tree\n");
}
}
}
function main()
{
var tree = new BinaryTree();
/*
Binary Tree
-----------------------
10
/ \
2 13
/ / \
4 9 5
/ \ \ \
7 3 6 11
/ \ / \
2 8 -3 12
/ \
-1 9
--------------------
*/
//Add node
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(13);
tree.root.right.right = new TreeNode(5);
tree.root.right.left = new TreeNode(9);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(7);
tree.root.left.left.right = new TreeNode(3);
tree.root.right.left.right = new TreeNode(6);
tree.root.right.right.right = new TreeNode(11);
tree.root.right.right.right.right = new TreeNode(12);
tree.root.right.right.right.left = new TreeNode(-3);
tree.root.left.left.right.left = new TreeNode(2);
tree.root.left.left.right.right = new TreeNode(8);
tree.root.left.left.right.right.left = new TreeNode(-1);
tree.root.left.left.right.right.right = new TreeNode(9);
/*
Boundary Nodes
--------------------------
↓
10
/ \
→ 2 13 ←
/ / \
→ 4 9 5 ←
/ \ \ \
→ 7 3 6 11 ←
/ \ / \
→ 2 8 -3 12 ←
/ \
→ -1 9 ←
---------------------------
*/
tree.findBoundaryLevelNode();
}
main();
Output
10
2 13
4 5
7 11
2 12
-1 9
# Python 3 Program
# Print the boundary nodes in each level of the binary tree using queue
class TreeNode :
# Data value
# Indicates left and right subtree
def __init__(self, data) :
self.data = data
self.left = None
self.right = None
class QNode :
def __init__(self, k) :
self.k = k
self.next = None
self.level = 0
# Define custom queue class
class MyQueue :
def __init__(self) :
self.front = None
self.rear = None
self.size = 0
# Add a new node at last of queue
def enqueue(self, data) :
node = QNode(data)
if (self.front == None) :
# When first node of queue
self.front = node
else :
# Add node at last level
self.rear.next = node
self.size += 1
self.rear = node
# Delete front node of queue
def dequeue(self) :
if (self.front != None) :
if (self.rear == self.front) :
self.rear = None
self.front = None
else :
self.front = self.front.next
self.size -= 1
def isSize(self) :
return self.size
def isEmpty(self) :
if (self.isSize() == 0) :
return True
return False
def peek(self) :
if (self.isSize() == 0) :
return None
else :
return self.front
class BinaryTree :
def __init__(self) :
self.root = None
def findBoundaryLevelNode(self) :
if (self.root != None) :
q = MyQueue()
# Add first node
q.enqueue(self.root)
# Define tree variables
node = None
first = None
last = None
level = -1
# Traversal tree elements in level order
while (q.isEmpty() == False) :
# Tree node
node = q.peek().k
if (node.left != None) :
# Add new left child node
q.enqueue(node.left)
q.rear.level = q.front.level + 1
if (node.right != None) :
# Add new right child node
q.enqueue(node.right)
q.rear.level = q.front.level + 1
if (q.front.level != level) :
level = q.front.level
if (last != None and last != first) :
# Print the last node in the above level
print(" ", last.data, end = "")
first = node
# Print first node in current level
print("\n ", node.data, end = "")
last = node
# Remove queue node
q.dequeue()
if (last != None and last != first) :
# Print the last node in the above level
print(" ", last.data)
else :
print("\nEmpty Tree")
def main() :
tree = BinaryTree()
# Binary Tree
# -----------------------
# 10
# / \
# 2 13
# / / \
# 4 9 5
# / \ \ \
# 7 3 6 11
# / \ / \
# 2 8 -3 12
# / \
# -1 9
# --------------------
# Add node
tree.root = TreeNode(10)
tree.root.left = TreeNode(2)
tree.root.right = TreeNode(13)
tree.root.right.right = TreeNode(5)
tree.root.right.left = TreeNode(9)
tree.root.left.left = TreeNode(4)
tree.root.left.left.left = TreeNode(7)
tree.root.left.left.right = TreeNode(3)
tree.root.right.left.right = TreeNode(6)
tree.root.right.right.right = TreeNode(11)
tree.root.right.right.right.right = TreeNode(12)
tree.root.right.right.right.left = TreeNode(-3)
tree.root.left.left.right.left = TreeNode(2)
tree.root.left.left.right.right = TreeNode(8)
tree.root.left.left.right.right.left = TreeNode(-1)
tree.root.left.left.right.right.right = TreeNode(9)
# Boundary Nodes
# --------------------------
# ↓
# 10
# / \
# → 2 13 ←
# / / \
# → 4 9 5 ←
# / \ \ \
# → 7 3 6 11 ←
# / \ / \
# → 2 8 -3 12 ←
# / \
# → -1 9 ←
# ---------------------------
tree.findBoundaryLevelNode()
if __name__ == "__main__": main()
Output
10
2 13
4 5
7 11
2 12
-1 9
# Ruby Program
# Print the boundary nodes in each level of the binary tree using queue
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
# Data value
# Indicates left and right subtree
def initialize(data)
self.data = data
self.left = nil
self.right = nil
end
end
class QNode
# Define the accessor and reader of class QNode
attr_reader :k, :next, :level
attr_accessor :k, :next, :level
def initialize(k)
self.k = k
self.next = nil
self.level = 0
end
end
# Define custom queue class
class MyQueue
# Define the accessor and reader of class MyQueue
attr_reader :front, :rear, :size
attr_accessor :front, :rear, :size
def initialize()
self.front = nil
self.rear = nil
self.size = 0
end
# Add a new node at last of queue
def enqueue(data)
node = QNode.new(data)
if (self.front == nil)
# When first node of queue
self.front = node
else
# Add node at last level
self.rear.next = node
end
self.size += 1
self.rear = node
end
# Delete front node of queue
def dequeue()
if (self.front != nil)
if (self.rear == self.front)
self.rear = nil
self.front = nil
else
self.front = self.front.next
end
self.size -= 1
end
end
def isSize()
return self.size
end
def isEmpty()
if (self.isSize() == 0)
return true
end
return false
end
def peek()
if (self.isSize() == 0)
return nil
else
return self.front
end
end
end
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root
attr_accessor :root
def initialize()
self.root = nil
end
def findBoundaryLevelNode()
if (self.root != nil)
q = MyQueue.new()
# Add first node
q.enqueue(self.root)
# Define tree variables
node = nil
first = nil
last = nil
level = -1
# Traversal tree elements in level order
while (q.isEmpty() == false)
# Tree node
node = q.peek().k
if (node.left != nil)
# Add new left child node
q.enqueue(node.left)
q.rear.level = q.front.level + 1
end
if (node.right != nil)
# Add new right child node
q.enqueue(node.right)
q.rear.level = q.front.level + 1
end
if (q.front.level != level)
level = q.front.level
if (last != nil && last != first)
# Print the last node in the above level
print(" ", last.data)
end
first = node
# Print first node in current level
print("\n ", node.data)
end
last = node
# Remove queue node
q.dequeue()
end
if (last != nil && last != first)
# Print the last node in the above level
print(" ", last.data, "\n")
end
else
print("\nEmpty Tree\n")
end
end
end
def main()
tree = BinaryTree.new()
# Binary Tree
# -----------------------
# 10
# / \
# 2 13
# / / \
# 4 9 5
# / \ \ \
# 7 3 6 11
# / \ / \
# 2 8 -3 12
# / \
# -1 9
# --------------------
# Add node
tree.root = TreeNode.new(10)
tree.root.left = TreeNode.new(2)
tree.root.right = TreeNode.new(13)
tree.root.right.right = TreeNode.new(5)
tree.root.right.left = TreeNode.new(9)
tree.root.left.left = TreeNode.new(4)
tree.root.left.left.left = TreeNode.new(7)
tree.root.left.left.right = TreeNode.new(3)
tree.root.right.left.right = TreeNode.new(6)
tree.root.right.right.right = TreeNode.new(11)
tree.root.right.right.right.right = TreeNode.new(12)
tree.root.right.right.right.left = TreeNode.new(-3)
tree.root.left.left.right.left = TreeNode.new(2)
tree.root.left.left.right.right = TreeNode.new(8)
tree.root.left.left.right.right.left = TreeNode.new(-1)
tree.root.left.left.right.right.right = TreeNode.new(9)
# Boundary Nodes
# --------------------------
# ↓
# 10
# / \
# → 2 13 ←
# / / \
# → 4 9 5 ←
# / \ \ \
# → 7 3 6 11 ←
# / \ / \
# → 2 8 -3 12 ←
# / \
# → -1 9 ←
# ---------------------------
tree.findBoundaryLevelNode()
end
main()
Output
10
2 13
4 5
7 11
2 12
-1 9
/*
Scala Program
Print the boundary nodes in each level of the binary tree using queue
*/
class TreeNode(
// Data value
var data: Int,
// Indicates left and right subtree
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
class QNode(var k: TreeNode,
var next: QNode,
var level: Int)
{
def this(k: TreeNode)
{
this(k, null, 0);
}
}
// Define custom queue class
class MyQueue(var front: QNode,
var rear: QNode,
var size: Int)
{
def this()
{
this(null, null, 0);
}
// Add a new node at last of queue
def enqueue(data: TreeNode): Unit = {
var node: QNode = new QNode(data);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last level
this.rear.next = node;
}
this.size += 1;
this.rear = node;
}
// Delete front node of queue
def dequeue(): Unit = {
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
this.size -= 1;
}
}
def isSize(): Int = {
return this.size;
}
def isEmpty(): Boolean = {
if (this.isSize() == 0)
{
return true;
}
return false;
}
def peek(): QNode = {
if (this.isSize() == 0)
{
return null;
}
else
{
return this.front;
}
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
def findBoundaryLevelNode(): Unit = {
if (this.root != null)
{
var q: MyQueue = new MyQueue();
// Add first node
q.enqueue(this.root);
// Define tree variables
var node: TreeNode = null;
var first: TreeNode = null;
var last: TreeNode = null;
var level: Int = -1;
// Traversal tree elements in level order
while (q.isEmpty() == false)
{
// Tree node
node = q.peek().k;
if (node.left != null)
{
// Add new left child node
q.enqueue(node.left);
q.rear.level = q.front.level + 1;
}
if (node.right != null)
{
// Add new right child node
q.enqueue(node.right);
q.rear.level = q.front.level + 1;
}
if (q.front.level != level)
{
level = q.front.level;
if (last != null && last != first)
{
// Print the last node in the above level
print(" " + last.data);
}
first = node;
// Print first node in current level
print("\n " + node.data);
}
last = node;
// Remove queue node
q.dequeue();
}
if (last != null && last != first)
{
// Print the last node in the above level
println(" " + last.data);
}
}
else
{
print("\nEmpty Tree\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinaryTree = new BinaryTree();
/*
Binary Tree
-----------------------
10
/ \
2 13
/ / \
4 9 5
/ \ \ \
7 3 6 11
/ \ / \
2 8 -3 12
/ \
-1 9
--------------------
*/
//Add node
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(13);
tree.root.right.right = new TreeNode(5);
tree.root.right.left = new TreeNode(9);
tree.root.left.left = new TreeNode(4);
tree.root.left.left.left = new TreeNode(7);
tree.root.left.left.right = new TreeNode(3);
tree.root.right.left.right = new TreeNode(6);
tree.root.right.right.right = new TreeNode(11);
tree.root.right.right.right.right = new TreeNode(12);
tree.root.right.right.right.left = new TreeNode(-3);
tree.root.left.left.right.left = new TreeNode(2);
tree.root.left.left.right.right = new TreeNode(8);
tree.root.left.left.right.right.left = new TreeNode(-1);
tree.root.left.left.right.right.right = new TreeNode(9);
/*
Boundary Nodes
--------------------------
↓
10
/ \
→ 2 13 ←
/ / \
→ 4 9 5 ←
/ \ \ \
→ 7 3 6 11 ←
/ \ / \
→ 2 8 -3 12 ←
/ \
→ -1 9 ←
---------------------------
*/
tree.findBoundaryLevelNode();
}
}
Output
10
2 13
4 5
7 11
2 12
-1 9
/*
Swift 4 Program
Print the boundary nodes in each level of the binary tree using queue
*/
class TreeNode
{
// Data value
var data: Int;
// Indicates left and right subtree
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
self.data = data;
self.left = nil;
self.right = nil;
}
}
class QNode
{
var k: TreeNode? ;
var next: QNode? ;
var level: Int;
init(_ k: TreeNode? )
{
self.k = k;
self.next = nil;
self.level = 0;
}
}
// Define custom queue class
class MyQueue
{
var front: QNode? ;
var rear: QNode? ;
var size: Int;
init()
{
self.front = nil;
self.rear = nil;
self.size = 0;
}
// Add a new node at last of queue
func enqueue(_ data: TreeNode? )
{
let node: QNode = QNode(data);
if (self.front == nil)
{
// When first node of queue
self.front = node;
}
else
{
// Add node at last level
self.rear!.next = node;
}
self.size += 1;
self.rear = node;
}
// Delete front node of queue
func dequeue()
{
if (self.front != nil)
{
if (self.rear === self.front)
{
self.rear = nil;
self.front = nil;
}
else
{
self.front = self.front!.next;
}
self.size -= 1;
}
}
func isSize() -> Int
{
return self.size;
}
func isEmpty() -> Bool
{
if (self.isSize() == 0)
{
return true;
}
return false;
}
func peek() -> QNode?
{
if (self.isSize() == 0)
{
return nil;
}
else
{
return self.front;
}
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
func findBoundaryLevelNode()
{
if (self.root != nil)
{
let q: MyQueue = MyQueue();
// Add first node
q.enqueue(self.root);
// Define tree variables
var node: TreeNode? = nil;
var first: TreeNode? = nil;
var last: TreeNode? = nil;
var level: Int = -1;
// Traversal tree elements in level order
while (q.isEmpty() == false)
{
// Tree node
node = q.peek()!.k;
if (node!.left != nil)
{
// Add new left child node
q.enqueue(node!.left);
q.rear!.level = q.front!.level + 1;
}
if (node!.right != nil)
{
// Add new right child node
q.enqueue(node!.right);
q.rear!.level = q.front!.level + 1;
}
if (q.front!.level != level)
{
level = q.front!.level;
if (last != nil && !(last === first))
{
// Print the last node in the above level
print(" ", last!.data, terminator: "");
}
first = node;
// Print first node in current level
print("\n ", node!.data, terminator: "");
}
last = node;
// Remove queue node
q.dequeue();
}
if (last != nil && !(last === first))
{
// Print the last node in the above level
print(" ", last!.data);
}
}
else
{
print("\nEmpty Tree");
}
}
}
func main()
{
let tree: BinaryTree = BinaryTree();
/*
Binary Tree
-----------------------
10
/ \
2 13
/ / \
4 9 5
/ \ \ \
7 3 6 11
/ \ / \
2 8 -3 12
/ \
-1 9
--------------------
*/
//Add node
tree.root = TreeNode(10);
tree.root!.left = TreeNode(2);
tree.root!.right = TreeNode(13);
tree.root!.right!.right = TreeNode(5);
tree.root!.right!.left = TreeNode(9);
tree.root!.left!.left = TreeNode(4);
tree.root!.left!.left!.left = TreeNode(7);
tree.root!.left!.left!.right = TreeNode(3);
tree.root!.right!.left!.right = TreeNode(6);
tree.root!.right!.right!.right = TreeNode(11);
tree.root!.right!.right!.right!.right = TreeNode(12);
tree.root!.right!.right!.right!.left = TreeNode(-3);
tree.root!.left!.left!.right!.left = TreeNode(2);
tree.root!.left!.left!.right!.right = TreeNode(8);
tree.root!.left!.left!.right!.right!.left = TreeNode(-1);
tree.root!.left!.left!.right!.right!.right = TreeNode(9);
/*
Boundary Nodes
--------------------------
↓
10
/ \
→ 2 13 ←
/ / \
→ 4 9 5 ←
/ \ \ \
→ 7 3 6 11 ←
/ \ / \
→ 2 8 -3 12 ←
/ \
→ -1 9 ←
---------------------------
*/
tree.findBoundaryLevelNode();
}
main();
Output
10
2 13
4 5
7 11
2 12
-1 9
/*
Kotlin Program
Print the boundary nodes in each level of the binary tree using queue
*/
class TreeNode
{
// Data value
var data: Int;
// Indicates left and right subtree
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class QNode
{
var k: TreeNode ? ;
var next: QNode ? ;
var level: Int;
constructor(k: TreeNode ? )
{
this.k = k;
this.next = null;
this.level = 0;
}
}
// Define custom queue class
class MyQueue
{
var front: QNode ? ;
var rear: QNode ? ;
var size: Int;
constructor()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a new node at last of queue
fun enqueue(data: TreeNode ? ): Unit
{
val node: QNode = QNode(data);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last level
this.rear?.next = node;
}
this.size += 1;
this.rear = node;
}
// Delete front node of queue
fun dequeue(): Unit
{
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front?.next;
}
this.size -= 1;
}
}
fun isSize(): Int
{
return this.size;
}
fun isEmpty(): Boolean
{
if (this.isSize() == 0)
{
return true;
}
return false;
}
fun peek(): QNode ?
{
if (this.isSize() == 0)
{
return null;
}
else
{
return this.front;
}
}
}
class BinaryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
fun findBoundaryLevelNode(): Unit
{
if (this.root != null)
{
val q: MyQueue = MyQueue();
// Add first node
q.enqueue(this.root);
// Define tree variables
var node: TreeNode ?;
var first: TreeNode ? = null;
var last: TreeNode ? = null;
var level: Int = -1;
// Traversal tree elements in level order
while (q.isEmpty() == false)
{
// Tree node
node = q.peek()?.k;
if (node?.left != null)
{
// Add new left child node
q.enqueue(node.left);
q.rear?.level = q.front!!.level + 1;
}
if (node?.right != null)
{
// Add new right child node
q.enqueue(node.right);
q.rear?.level = q.front!!.level + 1;
}
if (q.front!!.level != level)
{
level = q.front!!.level;
if (last != null && last != first)
{
// Print the last node in the above level
print(" " + last.data);
}
first = node;
// Print first node in current level
print("\n " + node!!.data);
}
last = node;
// Remove queue node
q.dequeue();
}
if (last != null && last != first)
{
// Print the last node in the above level
println(" " + last.data);
}
}
else
{
print("\nEmpty Tree\n");
}
}
}
fun main(args: Array < String > ): Unit
{
val tree: BinaryTree = BinaryTree();
/*
Binary Tree
-----------------------
10
/ \
2 13
/ / \
4 9 5
/ \ \ \
7 3 6 11
/ \ / \
2 8 -3 12
/ \
-1 9
--------------------
*/
//Add node
tree.root = TreeNode(10);
tree.root?.left = TreeNode(2);
tree.root?.right = TreeNode(13);
tree.root?.right?.right = TreeNode(5);
tree.root?.right?.left = TreeNode(9);
tree.root?.left?.left = TreeNode(4);
tree.root?.left?.left?.left = TreeNode(7);
tree.root?.left?.left?.right = TreeNode(3);
tree.root?.right?.left?.right = TreeNode(6);
tree.root?.right?.right?.right = TreeNode(11);
tree.root?.right?.right?.right?.right = TreeNode(12);
tree.root?.right?.right?.right?.left = TreeNode(-3);
tree.root?.left?.left?.right?.left = TreeNode(2);
tree.root?.left?.left?.right?.right = TreeNode(8);
tree.root?.left?.left?.right?.right?.left = TreeNode(-1);
tree.root?.left?.left?.right?.right?.right = TreeNode(9);
/*
Boundary Nodes
--------------------------
↓
10
/ \
→ 2 13 ←
/ / \
→ 4 9 5 ←
/ \ \ \
→ 7 3 6 11 ←
/ \ / \
→ 2 8 -3 12 ←
/ \
→ -1 9 ←
---------------------------
*/
tree.findBoundaryLevelNode();
}
Output
10
2 13
4 5
7 11
2 12
-1 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