Skip to main content

Middle to top down level order traversal in binary tree

Middle to top down manner level order traversal

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




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