Middle to top down level order traversal in binary tree

Here given code implementation process.
/*
C Program
Middle to top down level order traversal in binary tree
*/
#include <stdio.h>
#include <stdlib.h>
// Tree Node
struct TreeNode
{
int data;
struct TreeNode *left;
struct TreeNode *right;
};
// Binary Tree
struct BinaryTree
{
struct TreeNode *root;
};
// Used to collect resultant node
struct LevelNode
{
int element;
struct LevelNode *next;
};
struct LevelRecord
{
struct LevelNode *record;
};
// Create new tree
struct BinaryTree *newTree()
{
// Create dynamic node
struct BinaryTree *tree = (struct BinaryTree *) malloc(sizeof(struct BinaryTree));
if (tree != NULL)
{
tree->root = NULL;
}
else
{
printf("Memory Overflow to Create tree Tree\n");
}
//return new tree
return tree;
}
// returns a new node of tree
struct TreeNode *newNode(int data)
{
// Create dynamic node
struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
if (node != NULL)
{
//Set data and pointer values
node->data = data;
node->left = NULL;
node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
return node;
}
//Find height of given binary tree
int height(struct TreeNode *node)
{
if (node != NULL)
{
int a = height(node->left);
int b = height(node->right);
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
// Add a node element in a given level
void addLevelElement(struct LevelRecord data[], int level, int element)
{
struct LevelNode *node = (struct LevelNode *) malloc(sizeof(struct LevelNode));
if (node != NULL)
{
// Add level node
node->element = element;
// connect new node to other elements
node->next = data[level].record;
// Add new node at beginning of level
data[level].record = node;
}
else
{
printf("\n Memory Overflow When Create LevelNode\n");
}
}
// Collect the elements of each level
void getLevelNodes(struct TreeNode *node, struct LevelRecord data[], int level)
{
if (node != NULL)
{
// Add level node
addLevelElement(data, level, node->data);
// Visit right subtree
getLevelNodes(node->right, data, level + 1);
// Visit left subtree
getLevelNodes(node->left, data, level + 1);
}
}
// Print the elements of given level
void printLevel(struct LevelNode *node)
{
struct LevelNode *temp = node;
struct LevelNode *auxiliary = NULL;
// Print the level elements
while (temp != NULL)
{
printf(" %d", temp->element);
auxiliary = temp;
// visit next node of level
temp = auxiliary->next;
// Remove current node of given level
free(auxiliary);
auxiliary = NULL;
}
printf("\n");
}
// Print the resulting level
// Starting from middle
// And up-down manner
void printLevelNodes(struct LevelRecord data[], int level)
{
int middle = level / 2;
for (int i = 0; i <= level / 2; ++i)
{
if (i == 0)
{
// Middle level
printLevel(data[middle].record);
data[middle].record = NULL;
}
else
{
if (middle - i >= 0)
{
// Middle top layer
printLevel(data[middle - i].record);
data[middle - i].record = NULL;
}
if (middle + i < level)
{
// Middle bottom layer
printLevel(data[middle + i].record);
data[middle + i].record = NULL;
}
}
}
}
// Handles the request of printing resultant element in binary tree levels
void levelNodes(struct TreeNode *node)
{
// Find the height
int level = height(node);
if (level != 0)
{
// This is used to store starting node of each level
struct LevelRecord data[level];
// Set initial value of each level
for (int i = 0; i < level; ++i)
{
data[i].record = NULL;
}
// Get all level elements
getLevelNodes(node, data, 0);
// Print the level nodes
printLevelNodes(data, level);
}
else
{
printf("\n Empty Tree \n");
}
}
int main()
{
// Define trees
struct BinaryTree *tree = newTree();
/*
1
/ \
2 3
/ \ / \
3 4 6 5
/ \ \
-7 4 2
/ / \
9 1 -2
-----------------------
Binary Tree
-----------------------
*/
tree->root = newNode(1);
tree->root->left = newNode(2);
tree->root->right = newNode(3);
tree->root->left->left = newNode(3);
tree->root->left->right = newNode(4);
tree->root->left->right->left = newNode(-7);
tree->root->left->right->left->left = newNode(9);
tree->root->right->left = newNode(6);
tree->root->right->right = newNode(5);
tree->root->right->left->right = newNode(4);
tree->root->right->right->right = newNode(2);
tree->root->right->left->right->left = newNode(1);
tree->root->right->left->right->right = newNode(-2);
levelNodes(tree->root);
return 0;
}
Output
3 4 6 5
2 3
-7 4 2
1
9 1 -2
/*
Java Program for
Middle to top down level order traversal in binary tree
*/
// Tree Node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// Used to collect resultant node
class LevelNode
{
public int element;
public LevelNode next;
public LevelNode(int element, LevelNode nodes)
{
this.element = element;
this.next = nodes;
}
};
class LevelRecord
{
public LevelNode record;
public LevelRecord()
{
this.record = null;
}
};
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
this.root = null;
}
//Find height of given binary tree
public int height(TreeNode node)
{
if (node != null)
{
int a = height(node.left);
int b = height(node.right);
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
// Add a node element in a given level
public void addLevelElement(LevelRecord[] data, int level, int element)
{
LevelNode node = new LevelNode(element, data[level].record);
if (node != null)
{
// Add new node at beginning of level
data[level].record = node;
}
}
// Collect the elements of each level
public void getLevelNodes(TreeNode node, LevelRecord[] data, int level)
{
if (node != null)
{
// Add level node
addLevelElement(data, level, node.data);
// Visit right subtree
getLevelNodes(node.right, data, level + 1);
// Visit left subtree
getLevelNodes(node.left, data, level + 1);
}
}
// Print the elements of given level
public void printLevel(LevelNode node)
{
LevelNode temp = node;
LevelNode auxiliary = null;
// Print the level elements
while (temp != null)
{
System.out.print(" " + temp.element);
auxiliary = temp;
// visit next node of level
temp = auxiliary.next;
// Remove current node of given level
auxiliary = null;
}
System.out.print("\n");
}
// Print the resulting level
// Starting from middle
// And up-down manner
public void printLevelNodes(LevelRecord[] data, int level)
{
int middle = level / 2;
for (int i = 0; i <= level / 2; ++i)
{
if (i == 0)
{
// Middle level
printLevel(data[middle].record);
data[middle].record = null;
}
else
{
if (middle - i >= 0)
{
// Middle top layer
printLevel(data[middle - i].record);
data[middle - i].record = null;
}
if (middle + i < level)
{
// Middle bottom layer
printLevel(data[middle + i].record);
data[middle + i].record = null;
}
}
}
}
// Handles the request of printing resultant element in binary tree levels
public void levelNodes()
{
// Find the height
int level = height(this.root);
if (level != 0)
{
// This is used to store starting node of each level
LevelRecord[] data = new LevelRecord[level];
// Set initial value of each level
for (int i = 0; i < level; ++i)
{
data[i] = new LevelRecord();
}
// Get all level elements
getLevelNodes(this.root, data, 0);
// Print the level nodes
printLevelNodes(data, level);
}
else
{
System.out.print("\n Empty Tree \n");
}
}
public static void main(String[] args)
{
// Define trees
BinaryTree tree = new BinaryTree();
/*
1
/ \
2 3
/ \ / \
3 4 6 5
/ \ \
-7 4 2
/ / \
9 1 -2
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(4);
tree.root.left.right.left = new TreeNode(-7);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.right.left = new TreeNode(6);
tree.root.right.right = new TreeNode(5);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(2);
tree.root.right.left.right.left = new TreeNode(1);
tree.root.right.left.right.right = new TreeNode(-2);
tree.levelNodes();
}
}
Output
3 4 6 5
2 3
-7 4 2
1
9 1 -2
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program for
Middle to top down level order traversal in binary tree
*/
// Tree Node
class TreeNode
{
public:
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// Used to collect resultant node
class LevelNode
{
public: int element;
LevelNode *next;
LevelNode(int element, LevelNode *nodes)
{
this->element = element;
this->next = nodes;
}
};;
class LevelRecord
{
public: LevelNode *record;
LevelRecord()
{
this->record = NULL;
}
};;
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
this->root = NULL;
}
//Find height of given binary tree
int height(TreeNode *node)
{
if (node != NULL)
{
int a = this->height(node->left);
int b = this->height(node->right);
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
// Add a node element in a given level
void addLevelElement(LevelRecord data[], int level, int element)
{
LevelNode *node = new LevelNode(element, data[level].record);
if (node != NULL)
{
// Add new node at beginning of level
data[level].record = node;
}
}
// Collect the elements of each level
void getLevelNodes(TreeNode *node, LevelRecord data[], int level)
{
if (node != NULL)
{
// Add level node
this->addLevelElement(data, level, node->data);
// Visit right subtree
this->getLevelNodes(node->right, data, level + 1);
// Visit left subtree
this->getLevelNodes(node->left, data, level + 1);
}
}
// Print the elements of given level
void printLevel(LevelNode *node)
{
LevelNode *temp = node;
LevelNode *auxiliary = NULL;
// Print the level elements
while (temp != NULL)
{
cout << " " << temp->element;
auxiliary = temp;
// visit next node of level
temp = auxiliary->next;
// Remove current node of given level
delete auxiliary;
auxiliary = NULL;
}
cout << "\n";
}
// Print the resulting level
// Starting from middle
// And up-down manner
void printLevelNodes(LevelRecord data[], int level)
{
int middle = level / 2;
for (int i = 0; i <= level / 2; ++i)
{
if (i == 0)
{
// Middle level
this->printLevel(data[middle].record);
data[middle].record = NULL;
}
else
{
if (middle - i >= 0)
{
// Middle top layer
this->printLevel(data[middle - i].record);
data[middle - i].record = NULL;
}
if (middle + i < level)
{
// Middle bottom layer
this->printLevel(data[middle + i].record);
data[middle + i].record = NULL;
}
}
}
}
// Handles the request of printing resultant element in binary tree levels
void levelNodes()
{
// Find the height
int level = this->height(this->root);
if (level != 0)
{
// This is used to store starting node of each level
LevelRecord data[level];
// Set initial value of each level
for (int i = 0; i < level; ++i)
{
data[i].record = NULL;
}
// Get all level elements
this->getLevelNodes(this->root, data, 0);
// Print the level nodes
this->printLevelNodes(data, level);
}
else
{
cout << "\n Empty Tree \n";
}
}
};
int main()
{
// Define trees
BinaryTree tree = BinaryTree();
/*
1
/ \
2 3
/ \ / \
3 4 6 5
/ \ \
-7 4 2
/ / \
9 1 -2
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root->left = new TreeNode(2);
tree.root->right = new TreeNode(3);
tree.root->left->left = new TreeNode(3);
tree.root->left->right = new TreeNode(4);
tree.root->left->right->left = new TreeNode(-7);
tree.root->left->right->left->left = new TreeNode(9);
tree.root->right->left = new TreeNode(6);
tree.root->right->right = new TreeNode(5);
tree.root->right->left->right = new TreeNode(4);
tree.root->right->right->right = new TreeNode(2);
tree.root->right->left->right->left = new TreeNode(1);
tree.root->right->left->right->right = new TreeNode(-2);
tree.levelNodes();
return 0;
}
Output
3 4 6 5
2 3
-7 4 2
1
9 1 -2
// Include namespace system
using System;
/*
C# Program for
Middle to top down level order traversal in binary tree
*/
// Tree Node
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// Used to collect resultant node
public class LevelNode
{
public int element;
public LevelNode next;
public LevelNode(int element, LevelNode nodes)
{
this.element = element;
this.next = nodes;
}
};
public class LevelRecord
{
public LevelNode record;
public LevelRecord()
{
this.record = null;
}
};
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
this.root = null;
}
//Find height of given binary tree
public int height(TreeNode node)
{
if (node != null)
{
int a = height(node.left);
int b = height(node.right);
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
// Add a node element in a given level
public void addLevelElement(LevelRecord[] data, int level, int element)
{
LevelNode node = new LevelNode(element, data[level].record);
if (node != null)
{
// Add new node at beginning of level
data[level].record = node;
}
}
// Collect the elements of each level
public void getLevelNodes(TreeNode node, LevelRecord[] data, int level)
{
if (node != null)
{
// Add level node
addLevelElement(data, level, node.data);
// Visit right subtree
getLevelNodes(node.right, data, level + 1);
// Visit left subtree
getLevelNodes(node.left, data, level + 1);
}
}
// Print the elements of given level
public void printLevel(LevelNode node)
{
LevelNode temp = node;
LevelNode auxiliary = null;
// Print the level elements
while (temp != null)
{
Console.Write(" " + temp.element);
auxiliary = temp;
// visit next node of level
temp = auxiliary.next;
// Remove current node of given level
auxiliary = null;
}
Console.Write("\n");
}
// Print the resulting level
// Starting from middle
// And up-down manner
public void printLevelNodes(LevelRecord[] data, int level)
{
int middle = level / 2;
for (int i = 0; i <= level / 2; ++i)
{
if (i == 0)
{
// Middle level
printLevel(data[middle].record);
data[middle].record = null;
}
else
{
if (middle - i >= 0)
{
// Middle top layer
printLevel(data[middle - i].record);
data[middle - i].record = null;
}
if (middle + i < level)
{
// Middle bottom layer
printLevel(data[middle + i].record);
data[middle + i].record = null;
}
}
}
}
// Handles the request of printing resultant element in binary tree levels
public void levelNodes()
{
// Find the height
int level = height(this.root);
if (level != 0)
{
// This is used to store starting node of each level
LevelRecord[] data = new LevelRecord[level];
// Set initial value of each level
for (int i = 0; i < level; ++i)
{
data[i] = new LevelRecord();
}
// Get all level elements
getLevelNodes(this.root, data, 0);
// Print the level nodes
printLevelNodes(data, level);
}
else
{
Console.Write("\n Empty Tree \n");
}
}
public static void Main(String[] args)
{
// Define trees
BinaryTree tree = new BinaryTree();
/*
1
/ \
2 3
/ \ / \
3 4 6 5
/ \ \
-7 4 2
/ / \
9 1 -2
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(4);
tree.root.left.right.left = new TreeNode(-7);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.right.left = new TreeNode(6);
tree.root.right.right = new TreeNode(5);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(2);
tree.root.right.left.right.left = new TreeNode(1);
tree.root.right.left.right.right = new TreeNode(-2);
tree.levelNodes();
}
}
Output
3 4 6 5
2 3
-7 4 2
1
9 1 -2
<?php
/*
Php Program for
Middle to top down level order traversal in binary tree
*/
// Tree Node
class TreeNode
{
public $data;
public $left;
public $right;
function __construct($data)
{
$this->data = $data;
$this->left = null;
$this->right = null;
}
}
// Used to collect resultant node
class LevelNode
{
public $element;
public $next;
function __construct($element, $nodes)
{
$this->element = $element;
$this->next = $nodes;
}
};
class LevelRecord
{
public $record;
function __construct()
{
$this->record = null;
}
};
class BinaryTree
{
public $root;
function __construct()
{
$this->root = null;
}
//Find height of given binary tree
public function height($node)
{
if ($node != null)
{
$a = $this->height($node->left);
$b = $this->height($node->right);
if ($a > $b)
{
return $a + 1;
}
else
{
return $b + 1;
}
}
else
{
return 0;
}
}
// Add a node element in a given level
public function addLevelElement( & $data, $level, $element)
{
$node = new LevelNode($element, $data[$level]->record);
if ($node != null)
{
// Add new node at beginning of level
$data[$level]->record = $node;
}
}
// Collect the elements of each level
public function getLevelNodes($node, & $data, $level)
{
if ($node != null)
{
// Add level node
$this->addLevelElement($data, $level, $node->data);
// Visit right subtree
$this->getLevelNodes($node->right, $data, $level + 1);
// Visit left subtree
$this->getLevelNodes($node->left, $data, $level + 1);
}
}
// Print the elements of given level
public function printLevel($node)
{
$temp = $node;
$auxiliary = null;
// Print the level elements
while ($temp != null)
{
echo " ". $temp->element;
$auxiliary = $temp;
// visit next node of level
$temp = $auxiliary->next;
// Remove current node of given level
$auxiliary = null;
}
echo "\n";
}
// Print the resulting level
// Starting from middle
// And up-down manner
public function printLevelNodes( & $data, $level)
{
$middle = intval($level / 2);
for ($i = 0; $i <= intval($level / 2); ++$i)
{
if ($i == 0)
{
// Middle level
$this->printLevel($data[$middle]->record);
$data[$middle]->record = null;
}
else
{
if ($middle - $i >= 0)
{
// Middle top layer
$this->printLevel($data[$middle - $i]->record);
$data[$middle - $i]->record = null;
}
if ($middle + $i < $level)
{
// Middle bottom layer
$this->printLevel($data[$middle + $i]->record);
$data[$middle + $i]->record = null;
}
}
}
}
// Handles the request of printing resultant element in binary tree levels
public function levelNodes()
{
// Find the height
$level = $this->height($this->root);
if ($level != 0)
{
// This is used to store starting node of each level
$data = array_fill(0, $level, null);
// Set initial value of each level
for ($i = 0; $i < $level; ++$i)
{
$data[$i] = new LevelRecord();
}
// Get all level elements
$this->getLevelNodes($this->root, $data, 0);
// Print the level nodes
$this->printLevelNodes($data, $level);
}
else
{
echo "\n Empty Tree \n";
}
}
}
function main()
{
// Define trees
$tree = new BinaryTree();
/*
1
/ \
2 3
/ \ / \
3 4 6 5
/ \ \
-7 4 2
/ / \
9 1 -2
-----------------------
Binary Tree
-----------------------
*/
$tree->root = new TreeNode(1);
$tree->root->left = new TreeNode(2);
$tree->root->right = new TreeNode(3);
$tree->root->left->left = new TreeNode(3);
$tree->root->left->right = new TreeNode(4);
$tree->root->left->right->left = new TreeNode(-7);
$tree->root->left->right->left->left = new TreeNode(9);
$tree->root->right->left = new TreeNode(6);
$tree->root->right->right = new TreeNode(5);
$tree->root->right->left->right = new TreeNode(4);
$tree->root->right->right->right = new TreeNode(2);
$tree->root->right->left->right->left = new TreeNode(1);
$tree->root->right->left->right->right = new TreeNode(-2);
$tree->levelNodes();
}
main();
Output
3 4 6 5
2 3
-7 4 2
1
9 1 -2
/*
Node Js Program for
Middle to top down level order traversal in binary tree
*/
// Tree Node
class TreeNode
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// Used to collect resultant node
class LevelNode
{
constructor(element, nodes)
{
this.element = element;
this.next = nodes;
}
};
class LevelRecord
{
constructor()
{
this.record = null;
}
};
class BinaryTree
{
constructor()
{
this.root = null;
}
//Find height of given binary tree
height(node)
{
if (node != null)
{
var a = this.height(node.left);
var b = this.height(node.right);
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
// Add a node element in a given level
addLevelElement(data, level, element)
{
var node = new LevelNode(element, data[level].record);
if (node != null)
{
// Add new node at beginning of level
data[level].record = node;
}
}
// Collect the elements of each level
getLevelNodes(node, data, level)
{
if (node != null)
{
// Add level node
this.addLevelElement(data, level, node.data);
// Visit right subtree
this.getLevelNodes(node.right, data, level + 1);
// Visit left subtree
this.getLevelNodes(node.left, data, level + 1);
}
}
// Print the elements of given level
printLevel(node)
{
var temp = node;
var auxiliary = null;
// Print the level elements
while (temp != null)
{
process.stdout.write(" " + temp.element);
auxiliary = temp;
// visit next node of level
temp = auxiliary.next;
// Remove current node of given level
auxiliary = null;
}
process.stdout.write("\n");
}
// Print the resulting level
// Starting from middle
// And up-down manner
printLevelNodes(data, level)
{
var middle = parseInt(level / 2);
for (var i = 0; i <= parseInt(level / 2); ++i)
{
if (i == 0)
{
// Middle level
this.printLevel(data[middle].record);
data[middle].record = null;
}
else
{
if (middle - i >= 0)
{
// Middle top layer
this.printLevel(data[middle - i].record);
data[middle - i].record = null;
}
if (middle + i < level)
{
// Middle bottom layer
this.printLevel(data[middle + i].record);
data[middle + i].record = null;
}
}
}
}
// Handles the request of printing resultant element in binary tree levels
levelNodes()
{
// Find the height
var level = this.height(this.root);
if (level != 0)
{
// This is used to store starting node of each level
var data = Array(level).fill(null);
// Set initial value of each level
for (var i = 0; i < level; ++i)
{
data[i] = new LevelRecord();
}
// Get all level elements
this.getLevelNodes(this.root, data, 0);
// Print the level nodes
this.printLevelNodes(data, level);
}
else
{
process.stdout.write("\n Empty Tree \n");
}
}
}
function main()
{
// Define trees
var tree = new BinaryTree();
/*
1
/ \
2 3
/ \ / \
3 4 6 5
/ \ \
-7 4 2
/ / \
9 1 -2
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(4);
tree.root.left.right.left = new TreeNode(-7);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.right.left = new TreeNode(6);
tree.root.right.right = new TreeNode(5);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(2);
tree.root.right.left.right.left = new TreeNode(1);
tree.root.right.left.right.right = new TreeNode(-2);
tree.levelNodes();
}
main();
Output
3 4 6 5
2 3
-7 4 2
1
9 1 -2
# Python 3 Program for
# Middle to top down level order traversal in binary tree
# Tree Node
class TreeNode :
def __init__(self, data) :
self.data = data
self.left = None
self.right = None
# Used to collect resultant node
class LevelNode :
def __init__(self, element, nodes) :
self.element = element
self.next = nodes
class LevelRecord :
def __init__(self) :
self.record = None
class BinaryTree :
def __init__(self) :
self.root = None
# Find height of given binary tree
def height(self, node) :
if (node != None) :
a = self.height(node.left)
b = self.height(node.right)
if (a > b) :
return a + 1
else :
return b + 1
else :
return 0
# Add a node element in a given level
def addLevelElement(self, data, level, element) :
node = LevelNode(element, data[level].record)
if (node != None) :
# Add new node at beginning of level
data[level].record = node
# Collect the elements of each level
def getLevelNodes(self, node, data, level) :
if (node != None) :
# Add level node
self.addLevelElement(data, level, node.data)
# Visit right subtree
self.getLevelNodes(node.right, data, level + 1)
# Visit left subtree
self.getLevelNodes(node.left, data, level + 1)
# Print the elements of given level
def printLevel(self, node) :
temp = node
auxiliary = None
# Print the level elements
while (temp != None) :
print(" ", temp.element, end = "")
auxiliary = temp
# visit next node of level
temp = auxiliary.next
# Remove current node of given level
auxiliary = None
print(end = "\n")
# Print the resulting level
# Starting from middle
# And up-down manner
def printLevelNodes(self, data, level) :
middle = int(level / 2)
i = 0
while (i <= int(level / 2)) :
if (i == 0) :
# Middle level
self.printLevel(data[middle].record)
data[middle].record = None
else :
if (middle - i >= 0) :
# Middle top layer
self.printLevel(data[middle - i].record)
data[middle - i].record = None
if (middle + i < level) :
# Middle bottom layer
self.printLevel(data[middle + i].record)
data[middle + i].record = None
i += 1
# Handles the request of printing resultant element in binary tree levels
def levelNodes(self) :
# Find the height
level = self.height(self.root)
if (level != 0) :
# This is used to store starting node of each level
data = [None] * (level)
# Set initial value of each level
i = 0
while (i < level) :
data[i] = LevelRecord()
i += 1
# Get all level elements
self.getLevelNodes(self.root, data, 0)
# Print the level nodes
self.printLevelNodes(data, level)
else :
print("\n Empty Tree ")
def main() :
# Define trees
tree = BinaryTree()
#
# 1
# / \
# 2 3
# / \ / \
# 3 4 6 5
# / \ \
# -7 4 2
# / / \
# 9 1 -2
# -----------------------
# Binary Tree
# -----------------------
tree.root = TreeNode(1)
tree.root.left = TreeNode(2)
tree.root.right = TreeNode(3)
tree.root.left.left = TreeNode(3)
tree.root.left.right = TreeNode(4)
tree.root.left.right.left = TreeNode(-7)
tree.root.left.right.left.left = TreeNode(9)
tree.root.right.left = TreeNode(6)
tree.root.right.right = TreeNode(5)
tree.root.right.left.right = TreeNode(4)
tree.root.right.right.right = TreeNode(2)
tree.root.right.left.right.left = TreeNode(1)
tree.root.right.left.right.right = TreeNode(-2)
tree.levelNodes()
if __name__ == "__main__": main()
Output
3 4 6 5
2 3
-7 4 2
1
9 1 -2
# Ruby Program for
# Middle to top down level order traversal in binary tree
# Tree Node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(data)
self.data = data
self.left = nil
self.right = nil
end
end
# Used to collect resultant node
class LevelNode
# Define the accessor and reader of class LevelNode
attr_reader :element, :next
attr_accessor :element, :next
def initialize(element, nodes)
self.element = element
self.next = nodes
end
end
class LevelRecord
# Define the accessor and reader of class LevelRecord
attr_reader :record
attr_accessor :record
def initialize()
self.record = nil
end
end
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root
attr_accessor :root
def initialize()
self.root = nil
end
# Find height of given binary tree
def height(node)
if (node != nil)
a = self.height(node.left)
b = self.height(node.right)
if (a > b)
return a + 1
else
return b + 1
end
else
return 0
end
end
# Add a node element in a given level
def addLevelElement(data, level, element)
node = LevelNode.new(element, data[level].record)
if (node != nil)
# Add new node at beginning of level
data[level].record = node
end
end
# Collect the elements of each level
def getLevelNodes(node, data, level)
if (node != nil)
# Add level node
self.addLevelElement(data, level, node.data)
# Visit right subtree
self.getLevelNodes(node.right, data, level + 1)
# Visit left subtree
self.getLevelNodes(node.left, data, level + 1)
end
end
# Print the elements of given level
def printLevel(node)
temp = node
auxiliary = nil
# Print the level elements
while (temp != nil)
print(" ", temp.element)
auxiliary = temp
# visit next node of level
temp = auxiliary.next
# Remove current node of given level
auxiliary = nil
end
print("\n")
end
# Print the resulting level
# Starting from middle
# And up-down manner
def printLevelNodes(data, level)
middle = level / 2
i = 0
while (i <= level / 2)
if (i == 0)
# Middle level
self.printLevel(data[middle].record)
data[middle].record = nil
else
if (middle - i >= 0)
# Middle top layer
self.printLevel(data[middle - i].record)
data[middle - i].record = nil
end
if (middle + i < level)
# Middle bottom layer
self.printLevel(data[middle + i].record)
data[middle + i].record = nil
end
end
i += 1
end
end
# Handles the request of printing resultant element in binary tree levels
def levelNodes()
# Find the height
level = self.height(self.root)
if (level != 0)
# This is used to store starting node of each level
data = Array.new(level) {nil}
# Set initial value of each level
i = 0
while (i < level)
data[i] = LevelRecord.new()
i += 1
end
# Get all level elements
self.getLevelNodes(self.root, data, 0)
# Print the level nodes
self.printLevelNodes(data, level)
else
print("\n Empty Tree \n")
end
end
end
def main()
# Define trees
tree = BinaryTree.new()
#
# 1
# / \
# 2 3
# / \ / \
# 3 4 6 5
# / \ \
# -7 4 2
# / / \
# 9 1 -2
# -----------------------
# Binary Tree
# -----------------------
tree.root = TreeNode.new(1)
tree.root.left = TreeNode.new(2)
tree.root.right = TreeNode.new(3)
tree.root.left.left = TreeNode.new(3)
tree.root.left.right = TreeNode.new(4)
tree.root.left.right.left = TreeNode.new(-7)
tree.root.left.right.left.left = TreeNode.new(9)
tree.root.right.left = TreeNode.new(6)
tree.root.right.right = TreeNode.new(5)
tree.root.right.left.right = TreeNode.new(4)
tree.root.right.right.right = TreeNode.new(2)
tree.root.right.left.right.left = TreeNode.new(1)
tree.root.right.left.right.right = TreeNode.new(-2)
tree.levelNodes()
end
main()
Output
3 4 6 5
2 3
-7 4 2
1
9 1 -2
/*
Scala Program for
Middle to top down level order traversal in binary tree
*/
// Tree Node
class TreeNode(var data: Int , var left: TreeNode , var right: TreeNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
// Used to collect resultant node
class LevelNode(var element: Int , var next: LevelNode);
class LevelRecord(var record: LevelNode)
{
def this()
{
this(null);
}
};
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
//Find height of given binary tree
def height(node: TreeNode): Int = {
if (node != null)
{
var a: Int = this.height(node.left);
var b: Int = this.height(node.right);
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
// Add a node element in a given level
def addLevelElement(data: Array[LevelRecord], level: Int, element: Int): Unit = {
var node: LevelNode = new LevelNode(element, data(level).record);
if (node != null)
{
// Add new node at beginning of level
data(level).record = node;
}
}
// Collect the elements of each level
def getLevelNodes(node: TreeNode, data: Array[LevelRecord], level: Int): Unit = {
if (node != null)
{
// Add level node
this.addLevelElement(data, level, node.data);
// Visit right subtree
this.getLevelNodes(node.right, data, level + 1);
// Visit left subtree
this.getLevelNodes(node.left, data, level + 1);
}
}
// Print the elements of given level
def printLevel(node: LevelNode): Unit = {
var temp: LevelNode = node;
var auxiliary: LevelNode = null;
// Print the level elements
while (temp != null)
{
print(" " + temp.element);
auxiliary = temp;
// visit next node of level
temp = auxiliary.next;
// Remove current node of given level
auxiliary = null;
}
print("\n");
}
// Print the resulting level
// Starting from middle
// And up-down manner
def printLevelNodes(data: Array[LevelRecord], level: Int): Unit = {
var middle: Int = (level / 2).toInt;
var i: Int = 0;
while (i <= (level / 2).toInt)
{
if (i == 0)
{
// Middle level
this.printLevel(data(middle).record);
data(middle).record = null;
}
else
{
if (middle - i >= 0)
{
// Middle top layer
this.printLevel(data(middle - i).record);
data(middle - i).record = null;
}
if (middle + i < level)
{
// Middle bottom layer
this.printLevel(data(middle + i).record);
data(middle + i).record = null;
}
}
i += 1;
}
}
// Handles the request of printing resultant element in binary tree levels
def levelNodes(): Unit = {
// Find the height
var level: Int = this.height(this.root);
if (level != 0)
{
// This is used to store starting node of each level
var data: Array[LevelRecord] = Array.fill[LevelRecord](level)(null);
// Set initial value of each level
var i: Int = 0;
while (i < level)
{
data(i) = new LevelRecord();
i += 1;
}
// Get all level elements
this.getLevelNodes(this.root, data, 0);
// Print the level nodes
this.printLevelNodes(data, level);
}
else
{
print("\n Empty Tree \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Define trees
var tree: BinaryTree = new BinaryTree();
/*
1
/ \
2 3
/ \ / \
3 4 6 5
/ \ \
-7 4 2
/ / \
9 1 -2
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(3);
tree.root.left.right = new TreeNode(4);
tree.root.left.right.left = new TreeNode(-7);
tree.root.left.right.left.left = new TreeNode(9);
tree.root.right.left = new TreeNode(6);
tree.root.right.right = new TreeNode(5);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.right.right = new TreeNode(2);
tree.root.right.left.right.left = new TreeNode(1);
tree.root.right.left.right.right = new TreeNode(-2);
tree.levelNodes();
}
}
Output
3 4 6 5
2 3
-7 4 2
1
9 1 -2
/*
Swift 4 Program for
Middle to top down level order traversal in binary tree
*/
// Tree Node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
self.data = data;
self.left = nil;
self.right = nil;
}
}
// Used to collect resultant node
class LevelNode
{
var element: Int;
var next: LevelNode? ;
init(_ element: Int, _ nodes: LevelNode? )
{
self.element = element;
self.next = nodes;
}
};
class LevelRecord
{
var record: LevelNode? ;
init()
{
self.record = nil;
}
};
class BinaryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
//Find height of given binary tree
func height(_ node: TreeNode? )->Int
{
if (node != nil)
{
let a: Int = self.height(node!.left);
let b: Int = self.height(node!.right);
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
// Add a node element in a given level
func addLevelElement(_ data: [LevelRecord? ], _ level: Int, _ element: Int)
{
let node: LevelNode? = LevelNode(element, data[level]?.record);
if (node != nil)
{
// Add new node at beginning of level
data[level]?.record = node;
}
}
// Collect the elements of each level
func getLevelNodes(_ node: TreeNode? , _ data : [LevelRecord? ], _ level: Int)
{
if (node != nil)
{
// Add level node
self.addLevelElement(data, level, node!.data);
// Visit right subtree
self.getLevelNodes(node!.right, data, level + 1);
// Visit left subtree
self.getLevelNodes(node!.left, data, level + 1);
}
}
// Print the elements of given level
func printLevel(_ node: LevelNode? )
{
var temp: LevelNode? = node;
var auxiliary: LevelNode? = nil;
// Print the level elements
while (temp != nil)
{
print(" ", temp!.element, terminator: "");
auxiliary = temp;
// visit next node of level
temp = auxiliary!.next;
// Remove current node of given level
auxiliary = nil;
}
print(terminator: "\n");
}
// Print the resulting level
// Starting from middle
// And up-down manner
func printLevelNodes(_ data: [LevelRecord? ], _ level: Int)
{
let middle: Int = level / 2;
var i: Int = 0;
while (i <= level / 2)
{
if (i == 0)
{
// Middle level
self.printLevel(data[middle]?.record);
data[middle]?.record = nil;
}
else
{
if (middle - i >= 0)
{
// Middle top layer
self.printLevel(data[middle - i]?.record);
data[middle - i]?.record = nil;
}
if (middle + i < level)
{
// Middle bottom layer
self.printLevel(data[middle + i]?.record);
data[middle + i]?.record = nil;
}
}
i += 1;
}
}
// Handles the request of printing resultant element in binary tree levels
func levelNodes()
{
// Find the height
let level: Int = self.height(self.root);
if (level != 0)
{
// This is used to store starting node of each level
var data: [LevelRecord? ] = Array(repeating: nil, count: level);
// Set initial value of each level
var i: Int = 0;
while (i < level)
{
data[i] = LevelRecord();
i += 1;
}
// Get all level elements
self.getLevelNodes(self.root, data, 0);
// Print the level nodes
self.printLevelNodes(data, level);
}
else
{
print("\n Empty Tree ");
}
}
}
func main()
{
// Define trees
let tree: BinaryTree = BinaryTree();
/*
1
/ \
2 3
/ \ / \
3 4 6 5
/ \ \
-7 4 2
/ / \
9 1 -2
-----------------------
Binary Tree
-----------------------
*/
tree.root = TreeNode(1);
tree.root!.left = TreeNode(2);
tree.root!.right = TreeNode(3);
tree.root!.left!.left = TreeNode(3);
tree.root!.left!.right = TreeNode(4);
tree.root!.left!.right!.left = TreeNode(-7);
tree.root!.left!.right!.left!.left = TreeNode(9);
tree.root!.right!.left = TreeNode(6);
tree.root!.right!.right = TreeNode(5);
tree.root!.right!.left!.right = TreeNode(4);
tree.root!.right!.right!.right = TreeNode(2);
tree.root!.right!.left!.right!.left = TreeNode(1);
tree.root!.right!.left!.right!.right = TreeNode(-2);
tree.levelNodes();
}
main();
Output
3 4 6 5
2 3
-7 4 2
1
9 1 -2
/*
Kotlin Program for
Middle to top down level order traversal in binary tree
*/
// Tree Node
class TreeNode
{
var data: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// Used to collect resultant node
class LevelNode
{
var element: Int;
var next: LevelNode ? ;
constructor(element: Int, nodes: LevelNode ? )
{
this.element = element;
this.next = nodes;
}
};
class LevelRecord
{
var record: LevelNode ? ;
constructor()
{
this.record = null;
}
};
class BinaryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
//Find height of given binary tree
fun height(node: TreeNode ? ): Int
{
if (node != null)
{
var a: Int = this.height(node.left);
var b: Int = this.height(node.right);
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
// Add a node element in a given level
fun addLevelElement(data: Array < LevelRecord ? > , level : Int, element: Int): Unit
{
var node: LevelNode ? = LevelNode(element, data[level]?.record);
if (node != null)
{
// Add new node at beginning of level
data[level]?.record = node;
}
}
// Collect the elements of each level
fun getLevelNodes(node: TreeNode ? , data : Array < LevelRecord ? > , level : Int): Unit
{
if (node != null)
{
// Add level node
this.addLevelElement(data, level, node.data);
// Visit right subtree
this.getLevelNodes(node.right, data, level + 1);
// Visit left subtree
this.getLevelNodes(node.left, data, level + 1);
}
}
// Print the elements of given level
fun printLevel(node: LevelNode ? ): Unit
{
var temp: LevelNode ? = node;
var auxiliary: LevelNode?;
// Print the level elements
while (temp != null)
{
print(" " + temp.element);
auxiliary = temp;
// visit next node of level
temp = auxiliary.next;
}
print("\n");
}
// Print the resulting level
// Starting from middle
// And up-down manner
fun printLevelNodes(data: Array<LevelRecord?> , level : Int): Unit
{
var middle: Int = level / 2;
var i: Int = 0;
while (i <= level / 2)
{
if (i == 0)
{
// Middle level
this.printLevel(data[middle]?.record);
data[middle]?.record = null;
}
else
{
if (middle - i >= 0)
{
// Middle top layer
this.printLevel(data[middle - i]?.record);
data[middle - i]?.record = null;
}
if (middle + i < level)
{
// Middle bottom layer
this.printLevel(data[middle + i]?.record);
data[middle + i]?.record = null;
}
}
i += 1;
}
}
// Handles the request of printing resultant element in binary tree levels
fun levelNodes(): Unit
{
// Find the height
var level: Int = this.height(this.root);
if (level != 0)
{
// This is used to store starting node of each level
var data: Array <LevelRecord?> = Array(level)
{
null
};
// Set initial value of each level
var i: Int = 0;
while (i < level)
{
data[i] = LevelRecord();
i += 1;
}
// Get all level elements
this.getLevelNodes(this.root, data, 0);
// Print the level nodes
this.printLevelNodes(data, level);
}
else
{
print("\n Empty Tree \n");
}
}
}
fun main(args: Array < String > ): Unit
{
// Define trees
var tree: BinaryTree = BinaryTree();
/*
1
/ \
2 3
/ \ / \
3 4 6 5
/ \ \
-7 4 2
/ / \
9 1 -2
-----------------------
Binary Tree
-----------------------
*/
tree.root = TreeNode(1);
tree.root?.left = TreeNode(2);
tree.root?.right = TreeNode(3);
tree.root?.left?.left = TreeNode(3);
tree.root?.left?.right = TreeNode(4);
tree.root?.left?.right?.left = TreeNode(-7);
tree.root?.left?.right?.left?.left = TreeNode(9);
tree.root?.right?.left = TreeNode(6);
tree.root?.right?.right = TreeNode(5);
tree.root?.right?.left?.right = TreeNode(4);
tree.root?.right?.right?.right = TreeNode(2);
tree.root?.right?.left?.right?.left = TreeNode(1);
tree.root?.right?.left?.right?.right = TreeNode(-2);
tree.levelNodes();
}
Output
3 4 6 5
2 3
-7 4 2
1
9 1 -2
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