Posted on by Kalkicode
Code Queue

Print the middle nodes of each level of a binary tree

The problem at hand involves printing the middle nodes of each level in a binary tree. The middle node of a level is the node that is located in the center of that level when traversed from left to right. The task is to print these middle nodes for each level in the tree.

Problem Statement

Given a binary tree, the goal is to print the middle nodes of each level in separate lines.

Example

Consider the following binary tree:


     -6
    /   \
   4    -7
  / \     \
 2   3     12
    / \   /  \
   10 -4 5    9
  /     \      \
 1       7      8

The output for this tree would be:

-6
4 -7
3
-4 5
7

Note more than 2 middle node when levels are number of nodes are even number of counting.

Idea to Solve

To solve this problem, we can perform a level order traversal of the tree using two queues. One queue is used to store the nodes of the current level, and the other queue is used to store the nodes of the next level. While traversing each level, we extract the middle node from the current level's queue and print it.

Pseudocode

middleLevelNode():
  if root is null:
      return
  
  Create two empty queues, q1 and q2
  Create an empty ArrayList called record
  Set level = 1
  
  Enqueue the root into q1
  
  while q1 is not empty or q2 is not empty:
      while q1 is not empty:
          Dequeue a node from q1
          Add its data to record
          Enqueue its left and right children into q2
      
      Print the middle node from record
      Clear the record
      Increment level
      
      while q2 is not empty:
          Dequeue a node from q2
          Add its data to record
          Enqueue its left and right children into q1
      
      Print the middle node from record
      Clear the record
      Increment level

Algorithm Explanation

  1. We start by initializing two queues, q1 and q2, and an empty ArrayList called record. We also initialize the level counter to 1.
  2. We enqueue the root node into q1 to start the level order traversal.
  3. During each iteration, we extract nodes from q1 while enqueueing their left and right children into q2. We also add the data of these nodes to the record.
  4. After processing the nodes in q1, we calculate the middle index in the record and print the middle node's data. We then clear the record and increment the level.
  5. We repeat the same process with q2, enqueuing nodes into q1, adding data to the record, calculating the middle node, and printing it.
  6. This process continues until both q1 and q2 are empty.

Code Solution

import java.util.ArrayList;
// Java program for
// Print the middle nodes of each level of a binary tree

// Binary Tree node
class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Queue Node
class QNode
{
	public TreeNode n;
	public QNode next;
	public QNode(TreeNode n)
	{
		this.n = n;
		this.next = null;
	}
}
//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 n)
	{
		QNode node = new QNode(n);
		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 TreeNode peek()
	{
		if (this.isSize() == 0)
		{
			return null;
		}
		else
		{
			return this.front.n;
		}
	}
}
// Define Binary Tree 
public class BinaryTree
{
	public TreeNode root;
	public BinaryTree()
	{
		this.root = null;
	}
	// Print the middle element of given level
	public void printMiddleNode(ArrayList < Integer > level)
	{
		if (level.size() > 0)
		{
			int middle = level.size() / 2;
			if ((level.size() % 2) == 0)
			{
				// When two middle element possible
				System.out.print("\n " + level.get(middle - 1));
				System.out.print(" " + level.get(middle));
			}
			else
			{
				System.out.print("\n " + level.get(middle));
			}
		}
	}
	// This is display middle node of each level in binary tree
	public void middleLevelNode()
	{
		if (this.root == null)
		{
			// When tree is empty
			return;
		}
		// Auxiliary queue which is capable to contain a tree level nodes
		MyQueue q1 = new MyQueue();
		MyQueue q2 = new MyQueue();
		// Auxiliary temp variable
		TreeNode temp = null;
		int level = 1;
		// It will be use assemble a level node.
		ArrayList < Integer > record = new ArrayList < Integer > ();
		// Add first node in q1
		q1.enqueue(this.root);
		// This loop execute until auxiliary queue q1 and q2 are not empty
		while (!q1.isEmpty() || !q2.isEmpty())
		{
			// Execute loop until q1 queue are not empty
			// And store the next level node in q2 queue
			while (!q1.isEmpty())
			{
				// Get top node of q1 queue
				temp = q1.peek();
				// Add node value
				record.add(temp.data);
				if (temp.left != null)
				{
					q2.enqueue(temp.left);
				}
				if (temp.right != null)
				{
					q2.enqueue(temp.right);
				}
				// Remove top element of q1 queue
				q1.dequeue();
			}
			printMiddleNode(record);
			record.clear();
			level++;
			// Execute loop until q2 queue are not empty
			// And store the next level node in q1 queue
			while (!q2.isEmpty())
			{
				// Get top node of q2 queue
				temp = q2.peek();
				// Add node value
				record.add(temp.data);
				if (temp.left != null)
				{
					q1.enqueue(temp.left);
				}
				if (temp.right != null)
				{
					q1.enqueue(temp.right);
				}
				// Remove top element of q2 queue
				q2.dequeue();
			}
			printMiddleNode(record);
			record.clear();
			level++;
		}
	}
	public static void main(String[] args)
	{
		BinaryTree tree = new BinaryTree();
		/*
		    Create Binary Tree
		    -----------------
		         -6                            
		       /   \    
		      4    -7    
		     / \     \               
		    2   3     12
		       / \   /  \
		      10 -4 5    9
		     /     \      \
		    1      7      8

		*/
		tree.root = new TreeNode(-6);
		tree.root.left = new TreeNode(4);
		tree.root.left.right = new TreeNode(3);
		tree.root.left.right.left = new TreeNode(10);
		tree.root.left.right.left.left = new TreeNode(1);
		tree.root.left.right.right = new TreeNode(-4);
		tree.root.left.right.right.right = new TreeNode(7);
		tree.root.left.left = new TreeNode(2);
		tree.root.right = new TreeNode(-7);
		tree.root.right.right = new TreeNode(12);
		tree.root.right.right.left = new TreeNode(5);
		tree.root.right.right.right = new TreeNode(9);
		tree.root.right.right.right.right = new TreeNode(8);
		tree.middleLevelNode();
	}
}

input

 -6
 4 -7
 3
 -4 5
 7
// Include header file
#include <iostream>
#include <vector>
using namespace std;

// C++ program for
// Print the middle nodes of each level of a binary tree

// Binary Tree node
class TreeNode
{
	public: 
    int data;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data)
	{
		// Set node value
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
// Queue Node
class QNode
{
	public: 
    TreeNode *n;
	QNode *next;
	QNode(TreeNode *n)
	{
		this->n = n;
		this->next = NULL;
	}
};
//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 *n)
	{
		QNode *node = new QNode(n);
		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;
			}
			this->size--;
          	// Free memory
          	delete temp;
		}
	}
	int isSize()
	{
		return this->size;
	}
	bool isEmpty()
	{
		if (this->isSize() == 0)
		{
			return true;
		}
		return false;
	}
	TreeNode *peek()
	{
		if (this->isSize() == 0)
		{
			return NULL;
		}
		else
		{
			return this->front->n;
		}
	}
};
// Define Binary Tree
class BinaryTree
{
	public: TreeNode *root;
	BinaryTree()
	{
		this->root = NULL;
	}
	// Print the middle element of given level
	void printMiddleNode(vector < int > level)
	{
		if (level.size() > 0)
		{
			int middle = level.size() / 2;
			if ((level.size() % 2) == 0)
			{
				// When two middle element possible
				cout << "\n " << level.at(middle - 1);
				cout << " " << level.at(middle);
			}
			else
			{
				cout << "\n " << level.at(middle);
			}
		}
	}
	// This is display middle node of each level in binary tree
	void middleLevelNode()
	{
		if (this->root == NULL)
		{
			// When tree is empty
			return;
		}
		// Auxiliary queue which is capable to contain a tree level nodes
		MyQueue *q1 = new MyQueue();
		MyQueue *q2 = new MyQueue();
		// Auxiliary temp variable
		TreeNode *temp = NULL;
		int level = 1;
		// It will be use assemble a level node.
		vector < int > record ;
		// Add first node in q1
		q1->enqueue(this->root);
		// This loop execute until auxiliary queue q1 and q2 are not empty
		while (!q1->isEmpty() || !q2->isEmpty())
		{
			// Execute loop until q1 queue are not empty
			// And store the next level node in q2 queue
			while (!q1->isEmpty())
			{
				// Get top node of q1 queue
				temp = q1->peek();
				// Add node value
				record.push_back(temp->data);
				if (temp->left != NULL)
				{
					q2->enqueue(temp->left);
				}
				if (temp->right != NULL)
				{
					q2->enqueue(temp->right);
				}
				// Remove top element of q1 queue
				q1->dequeue();
			}
			this->printMiddleNode(record);
			record.clear();
			level++;
			// Execute loop until q2 queue are not empty
			// And store the next level node in q1 queue
			while (!q2->isEmpty())
			{
				// Get top node of q2 queue
				temp = q2->peek();
				// Add node value
				record.push_back(temp->data);
				if (temp->left != NULL)
				{
					q1->enqueue(temp->left);
				}
				if (temp->right != NULL)
				{
					q1->enqueue(temp->right);
				}
				// Remove top element of q2 queue
				q2->dequeue();
			}
			this->printMiddleNode(record);
			record.clear();
			level++;
		}
	}
};
int main()
{
	BinaryTree *tree = new BinaryTree();
	/*
	    Create Binary Tree
	    -----------------
	         -6                            
	       /   \    
	      4    -7    
	     / \     \               
	    2   3     12
	       / \   /  \
	      10 -4 5    9
	     /     \      \
	    1      7      8
	*/
	tree->root = new TreeNode(-6);
	tree->root->left = new TreeNode(4);
	tree->root->left->right = new TreeNode(3);
	tree->root->left->right->left = new TreeNode(10);
	tree->root->left->right->left->left = new TreeNode(1);
	tree->root->left->right->right = new TreeNode(-4);
	tree->root->left->right->right->right = new TreeNode(7);
	tree->root->left->left = new TreeNode(2);
	tree->root->right = new TreeNode(-7);
	tree->root->right->right = new TreeNode(12);
	tree->root->right->right->left = new TreeNode(5);
	tree->root->right->right->right = new TreeNode(9);
	tree->root->right->right->right->right = new TreeNode(8);
	tree->middleLevelNode();
	return 0;
}

input

 -6
 4 -7
 3
 -4 5
 7
// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Print the middle nodes of each level of a binary tree

// Binary Tree node
public class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Queue Node
public class QNode
{
	public TreeNode n;
	public QNode next;
	public QNode(TreeNode n)
	{
		this.n = n;
		this.next = null;
	}
}
//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 n)
	{
		QNode node = new QNode(n);
		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 TreeNode peek()
	{
		if (this.isSize() == 0)
		{
			return null;
		}
		else
		{
			return this.front.n;
		}
	}
}
// Define Binary Tree
public class BinaryTree
{
	public TreeNode root;
	public BinaryTree()
	{
		this.root = null;
	}
	// Print the middle element of given level
	public void printMiddleNode(List<int> level)
	{
		if (level.Count > 0)
		{
			int middle = level.Count / 2;
			if ((level.Count % 2) == 0)
			{
				// When two middle element possible
				Console.Write("\n " + level[middle - 1]);
				Console.Write(" " + level[middle]);
			}
			else
			{
				Console.Write("\n " + level[middle]);
			}
		}
	}
	// This is display middle node of each level in binary tree
	public void middleLevelNode()
	{
		if (this.root == null)
		{
			// When tree is empty
			return;
		}
		// Auxiliary queue which is capable to contain a tree level nodes
		MyQueue q1 = new MyQueue();
		MyQueue q2 = new MyQueue();
		// Auxiliary temp variable
		TreeNode temp = null;
		int level = 1;
		// It will be use assemble a level node.
		List < int > record = new List < int > ();
		// Add first node in q1
		q1.enqueue(this.root);
		// This loop execute until auxiliary queue q1 and q2 are not empty
		while (!q1.isEmpty() || !q2.isEmpty())
		{
			// Execute loop until q1 queue are not empty
			// And store the next level node in q2 queue
			while (!q1.isEmpty())
			{
				// Get top node of q1 queue
				temp = q1.peek();
				// Add node value
				record.Add(temp.data);
				if (temp.left != null)
				{
					q2.enqueue(temp.left);
				}
				if (temp.right != null)
				{
					q2.enqueue(temp.right);
				}
				// Remove top element of q1 queue
				q1.dequeue();
			}
			this.printMiddleNode(record);
			record.Clear();
			level++;
			// Execute loop until q2 queue are not empty
			// And store the next level node in q1 queue
			while (!q2.isEmpty())
			{
				// Get top node of q2 queue
				temp = q2.peek();
				// Add node value
				record.Add(temp.data);
				if (temp.left != null)
				{
					q1.enqueue(temp.left);
				}
				if (temp.right != null)
				{
					q1.enqueue(temp.right);
				}
				// Remove top element of q2 queue
				q2.dequeue();
			}
			this.printMiddleNode(record);
			record.Clear();
			level++;
		}
	}
	public static void Main(String[] args)
	{
		BinaryTree tree = new BinaryTree();
		/*
		    Create Binary Tree
		    -----------------
		         -6                            
		       /   \    
		      4    -7    
		     / \     \               
		    2   3     12
		       / \   /  \
		      10 -4 5    9
		     /     \      \
		    1      7      8
		*/
		tree.root = new TreeNode(-6);
		tree.root.left = new TreeNode(4);
		tree.root.left.right = new TreeNode(3);
		tree.root.left.right.left = new TreeNode(10);
		tree.root.left.right.left.left = new TreeNode(1);
		tree.root.left.right.right = new TreeNode(-4);
		tree.root.left.right.right.right = new TreeNode(7);
		tree.root.left.left = new TreeNode(2);
		tree.root.right = new TreeNode(-7);
		tree.root.right.right = new TreeNode(12);
		tree.root.right.right.left = new TreeNode(5);
		tree.root.right.right.right = new TreeNode(9);
		tree.root.right.right.right.right = new TreeNode(8);
		tree.middleLevelNode();
	}
}

input

 -6
 4 -7
 3
 -4 5
 7
<?php
// Php program for
// Print the middle nodes of each level of a binary tree

// Binary Tree node
class TreeNode
{
	public $data;
	public $left;
	public $right;
	public	function __construct($data)
	{
		// Set node value
		$this->data = $data;
		$this->left = NULL;
		$this->right = NULL;
	}
}
// Queue Node
class QNode
{
	public $n;
	public $next;
	public	function __construct($n)
	{
		$this->n = $n;
		$this->next = NULL;
	}
}
//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($n)
	{
		$node = new QNode($n);
		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->n;
		}
	}
}
// Define Binary Tree
class BinaryTree
{
	public $root;
	public	function __construct()
	{
		$this->root = NULL;
	}
	// Print the middle element of given level
	public	function printMiddleNode($level)
	{
		if (count($level) > 0)
		{
			$middle = (int)(count($level) / 2);
			if ((count($level) % 2) == 0)
			{
				// When two middle element possible
				echo("\n ".$level[$middle - 1]);
				echo(" ".$level[$middle]);
			}
			else
			{
				echo("\n ".$level[$middle]);
			}
		}
	}
	// This is display middle node of each level in binary tree
	public	function middleLevelNode()
	{
		if ($this->root == NULL)
		{
			// When tree is empty
			return;
		}
		// Auxiliary queue which is capable to contain a tree level nodes
		$q1 = new MyQueue();
		$q2 = new MyQueue();
		// Auxiliary temp variable
		$temp = NULL;
		$level = 1;
		// It will be use assemble a level node.
		$record =  array();
		// Add first node in q1
		$q1->enqueue($this->root);
		// This loop execute until auxiliary queue q1 and q2 are not empty
		while (!$q1->isEmpty() || !$q2->isEmpty())
		{
			// Execute loop until q1 queue are not empty
			// And store the next level node in q2 queue
			while (!$q1->isEmpty())
			{
				// Get top node of q1 queue
				$temp = $q1->peek();
				// Add node value
				$record[] = $temp->data;
				if ($temp->left != NULL)
				{
					$q2->enqueue($temp->left);
				}
				if ($temp->right != NULL)
				{
					$q2->enqueue($temp->right);
				}
				// Remove top element of q1 queue
				$q1->dequeue();
			}
			$this->printMiddleNode($record);
			$record = array();
			$level++;
			// Execute loop until q2 queue are not empty
			// And store the next level node in q1 queue
			while (!$q2->isEmpty())
			{
				// Get top node of q2 queue
				$temp = $q2->peek();
				// Add node value
				$record[] = $temp->data;
				if ($temp->left != NULL)
				{
					$q1->enqueue($temp->left);
				}
				if ($temp->right != NULL)
				{
					$q1->enqueue($temp->right);
				}
				// Remove top element of q2 queue
				$q2->dequeue();
			}
			$this->printMiddleNode($record);
			$record = array();
			$level++;
		}
	}
}

function main()
{
	$tree = new BinaryTree();
	/*
	    Create Binary Tree
	    -----------------
	         -6                            
	       /   \    
	      4    -7    
	     / \     \               
	    2   3     12
	       / \   /  \
	      10 -4 5    9
	     /     \      \
	    1      7      8
	*/
	$tree->root = new TreeNode(-6);
	$tree->root->left = new TreeNode(4);
	$tree->root->left->right = new TreeNode(3);
	$tree->root->left->right->left = new TreeNode(10);
	$tree->root->left->right->left->left = new TreeNode(1);
	$tree->root->left->right->right = new TreeNode(-4);
	$tree->root->left->right->right->right = new TreeNode(7);
	$tree->root->left->left = new TreeNode(2);
	$tree->root->right = new TreeNode(-7);
	$tree->root->right->right = new TreeNode(12);
	$tree->root->right->right->left = new TreeNode(5);
	$tree->root->right->right->right = new TreeNode(9);
	$tree->root->right->right->right->right = new TreeNode(8);
	$tree->middleLevelNode();
}
main();

input

 -6
 4 -7
 3
 -4 5
 7
// Node JS program for
// Print the middle nodes of each level of a binary tree

// Binary Tree node
class TreeNode
{
	constructor(data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Queue Node
class QNode
{
	constructor(n)
	{
		this.n = n;
		this.next = null;
	}
}
//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(n)
	{
		var node = new QNode(n);
		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.n;
		}
	}
}
// Define Binary Tree
class BinaryTree
{
	constructor()
	{
		this.root = null;
	}
	// Print the middle element of given level
	printMiddleNode(level)
	{
		if (level.length > 0)
		{
			var middle = parseInt(level.length / 2);
			if ((level.length % 2) == 0)
			{
				// When two middle element possible
				process.stdout.write("\n " + level[middle - 1]);
				process.stdout.write(" " + level[middle]);
			}
			else
			{
				process.stdout.write("\n " + level[middle]);
			}
		}
	}
	// This is display middle node of each level in binary tree
	middleLevelNode()
	{
		if (this.root == null)
		{
			// When tree is empty
			return;
		}
		// Auxiliary queue which is capable to contain a tree level nodes
		var q1 = new MyQueue();
		var q2 = new MyQueue();
		// Auxiliary temp variable
		var temp = null;
		var level = 1;
		// It will be use assemble a level node.
		var record = [];
		// Add first node in q1
		q1.enqueue(this.root);
		// This loop execute until auxiliary queue q1 and q2 are not empty
		while (!q1.isEmpty() || !q2.isEmpty())
		{
			// Execute loop until q1 queue are not empty
			// And store the next level node in q2 queue
			while (!q1.isEmpty())
			{
				// Get top node of q1 queue
				temp = q1.peek();
				// Add node value
				record.push(temp.data);
				if (temp.left != null)
				{
					q2.enqueue(temp.left);
				}
				if (temp.right != null)
				{
					q2.enqueue(temp.right);
				}
				// Remove top element of q1 queue
				q1.dequeue();
			}
			this.printMiddleNode(record);
			record = [];
			level++;
			// Execute loop until q2 queue are not empty
			// And store the next level node in q1 queue
			while (!q2.isEmpty())
			{
				// Get top node of q2 queue
				temp = q2.peek();
				// Add node value
				record.push(temp.data);
				if (temp.left != null)
				{
					q1.enqueue(temp.left);
				}
				if (temp.right != null)
				{
					q1.enqueue(temp.right);
				}
				// Remove top element of q2 queue
				q2.dequeue();
			}
			this.printMiddleNode(record);
			record = [];
			level++;
		}
	}
}

function main()
{
	var tree = new BinaryTree();
	/*
	    Create Binary Tree
	    -----------------
	         -6                            
	       /   \    
	      4    -7    
	     / \     \               
	    2   3     12
	       / \   /  \
	      10 -4 5    9
	     /     \      \
	    1      7      8
	*/
	tree.root = new TreeNode(-6);
	tree.root.left = new TreeNode(4);
	tree.root.left.right = new TreeNode(3);
	tree.root.left.right.left = new TreeNode(10);
	tree.root.left.right.left.left = new TreeNode(1);
	tree.root.left.right.right = new TreeNode(-4);
	tree.root.left.right.right.right = new TreeNode(7);
	tree.root.left.left = new TreeNode(2);
	tree.root.right = new TreeNode(-7);
	tree.root.right.right = new TreeNode(12);
	tree.root.right.right.left = new TreeNode(5);
	tree.root.right.right.right = new TreeNode(9);
	tree.root.right.right.right.right = new TreeNode(8);
	tree.middleLevelNode();
}
main();

input

 -6
 4 -7
 3
 -4 5
 7
#  Python 3 program for
#  Print the middle nodes of each level of a binary tree

#  Binary Tree node
class TreeNode :
	def __init__(self, data) :
		#  Set node value
		self.data = data
		self.left = None
		self.right = None
	

#  Queue Node
class QNode :
	def __init__(self, n) :
		self.n = n
		self.next = None
	

# 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, n) :
		node = QNode(n)
		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.n
		
	

#  Define Binary Tree
class BinaryTree :
	def __init__(self) :
		self.root = None
	
	#  Print the middle element of given level
	def printMiddleNode(self, level) :
		if (len(level) > 0) :
			middle = int(len(level) / 2)
			if ((len(level) % 2) == 0) :
				#  When two middle element possible
				print("\n ", level[middle - 1], end = "")
				print(" ", level[middle], end = "")
			else :
				print("\n ", level[middle], end = "")
			
		
	
	#  This is display middle node of each level in binary tree
	def middleLevelNode(self) :
		if (self.root == None) :
			#  When tree is empty
			return
		
		#  Auxiliary queue which is capable to contain a tree level nodes
		q1 = MyQueue()
		q2 = MyQueue()
		#  Auxiliary temp variable
		temp = None
		level = 1
		#  It will be use assemble a level node.
		record = []
		#  Add first node in q1
		q1.enqueue(self.root)
		#  This loop execute until auxiliary queue q1 and q2 are not empty
		while (not q1.isEmpty() or not q2.isEmpty()) :
			#  Execute loop until q1 queue are not empty
			#  And store the next level node in q2 queue
			while (not q1.isEmpty()) :
				#  Get top node of q1 queue
				temp = q1.peek()
				#  Add node value
				record.append(temp.data)
				if (temp.left != None) :
					q2.enqueue(temp.left)
				
				if (temp.right != None) :
					q2.enqueue(temp.right)
				
				#  Remove top element of q1 queue
				q1.dequeue()
			
			self.printMiddleNode(record)
			record.clear()
			level += 1
			#  Execute loop until q2 queue are not empty
			#  And store the next level node in q1 queue
			while (not q2.isEmpty()) :
				#  Get top node of q2 queue
				temp = q2.peek()
				#  Add node value
				record.append(temp.data)
				if (temp.left != None) :
					q1.enqueue(temp.left)
				
				if (temp.right != None) :
					q1.enqueue(temp.right)
				
				#  Remove top element of q2 queue
				q2.dequeue()
			
			self.printMiddleNode(record)
			record.clear()
			level += 1
		
	

def main() :
	tree = BinaryTree()
	#    Create Binary Tree
	#    -----------------
	#         -6                            
	#       /   \    
	#      4    -7    
	#     / \     \               
	#    2   3     12
	#       / \   /  \
	#      10 -4 5    9
	#     /     \      \
	#    1      7      8
	tree.root = TreeNode(-6)
	tree.root.left = TreeNode(4)
	tree.root.left.right = TreeNode(3)
	tree.root.left.right.left = TreeNode(10)
	tree.root.left.right.left.left = TreeNode(1)
	tree.root.left.right.right = TreeNode(-4)
	tree.root.left.right.right.right = TreeNode(7)
	tree.root.left.left = TreeNode(2)
	tree.root.right = TreeNode(-7)
	tree.root.right.right = TreeNode(12)
	tree.root.right.right.left = TreeNode(5)
	tree.root.right.right.right = TreeNode(9)
	tree.root.right.right.right.right = TreeNode(8)
	tree.middleLevelNode()

if __name__ == "__main__": main()

input

  -6
  4  -7
  3
  -4  5
  7
#  Ruby program for
#  Print the middle nodes of each level of a binary tree

#  Binary 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) 
		#  Set node value
		self.data = data
		self.left = nil
		self.right = nil
	end

end

#  Queue Node
class QNode 
	# Define the accessor and reader of class QNode
	attr_reader :n, :next
	attr_accessor :n, :next
	def initialize(n) 
		self.n = n
		self.next = nil
	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(n) 
		node = QNode.new(n)
		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.n
		end

	end

end

#  Define Binary Tree
class BinaryTree 
	# Define the accessor and reader of class BinaryTree
	attr_reader :root
	attr_accessor :root
	def initialize() 
		self.root = nil
	end

	#  Print the middle element of given level
	def printMiddleNode(level) 
		if (level.length > 0) 
			middle = level.length / 2
			if ((level.length % 2) == 0) 
				#  When two middle element possible
				print("\n ", level[middle - 1])
				print(" ", level[middle])
			else 
				print("\n ", level[middle])
			end

		end

	end

	#  This is display middle node of each level in binary tree
	def middleLevelNode() 
		if (self.root == nil) 
			#  When tree is empty
			return
		end

		#  Auxiliary queue which is capable to contain a tree level nodes
		q1 = MyQueue.new()
		q2 = MyQueue.new()
		#  Auxiliary temp variable
		temp = nil
		level = 1
		#  It will be use assemble a level node.
		record = []
		#  Add first node in q1
		q1.enqueue(self.root)
		#  This loop execute until auxiliary queue q1 and q2 are not empty
		while (!q1.isEmpty() || !q2.isEmpty()) 
			#  Execute loop until q1 queue are not empty
			#  And store the next level node in q2 queue
			while (!q1.isEmpty()) 
				#  Get top node of q1 queue
				temp = q1.peek()
				#  Add node value
				record.push(temp.data)
				if (temp.left != nil) 
					q2.enqueue(temp.left)
				end

				if (temp.right != nil) 
					q2.enqueue(temp.right)
				end

				#  Remove top element of q1 queue
				q1.dequeue()
			end

			self.printMiddleNode(record)
			record.clear()
			level += 1
			#  Execute loop until q2 queue are not empty
			#  And store the next level node in q1 queue
			while (!q2.isEmpty()) 
				#  Get top node of q2 queue
				temp = q2.peek()
				#  Add node value
				record.push(temp.data)
				if (temp.left != nil) 
					q1.enqueue(temp.left)
				end

				if (temp.right != nil) 
					q1.enqueue(temp.right)
				end

				#  Remove top element of q2 queue
				q2.dequeue()
			end

			self.printMiddleNode(record)
			record.clear()
			level += 1
		end

	end

end

def main() 
	tree = BinaryTree.new()
	#    Create Binary Tree
	#    -----------------
	#         -6                            
	#       /   \    
	#      4    -7    
	#     / \     \               
	#    2   3     12
	#       / \   /  \
	#      10 -4 5    9
	#     /     \      \
	#    1      7      8
	tree.root = TreeNode.new(-6)
	tree.root.left = TreeNode.new(4)
	tree.root.left.right = TreeNode.new(3)
	tree.root.left.right.left = TreeNode.new(10)
	tree.root.left.right.left.left = TreeNode.new(1)
	tree.root.left.right.right = TreeNode.new(-4)
	tree.root.left.right.right.right = TreeNode.new(7)
	tree.root.left.left = TreeNode.new(2)
	tree.root.right = TreeNode.new(-7)
	tree.root.right.right = TreeNode.new(12)
	tree.root.right.right.left = TreeNode.new(5)
	tree.root.right.right.right = TreeNode.new(9)
	tree.root.right.right.right.right = TreeNode.new(8)
	tree.middleLevelNode()
end

main()

input

 -6
 4 -7
 3
 -4 5
 7
import scala.collection.mutable._;
// Scala program for
// Print the middle nodes of each level of a binary tree

// Binary Tree node
class TreeNode(var data: Int , var left: TreeNode , var right: TreeNode)
{
	def this(data: Int)
	{
		// Set node value
		this(data,null,null);
	}
}
// Queue Node
class QNode(var n: TreeNode , var next: QNode)
{
	def this(n: TreeNode)
	{
		this(n,null);
	}
}
//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(n: TreeNode): Unit = {
		var node: QNode = new QNode(n);
		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(): TreeNode = {
		if (this.isSize() == 0)
		{
			return null;
		}
		else
		{
			return this.front.n;
		}
	}
}
// Define Binary Tree
class BinaryTree(var root: TreeNode)
{
	def this()
	{
		this(null);
	}
	// Print the middle element of given level
	def printMiddleNode(level: ArrayBuffer[Int]): Unit = {
		if (level.size > 0)
		{
			var middle: Int = level.size / 2;
			if ((level.size % 2) == 0)
			{
				// When two middle element possible
				print("\n " + level(middle - 1));
				print(" " + level(middle));
			}
			else
			{
				print("\n " + level(middle));
			}
		}
	}
	// This is display middle node of each level in binary tree
	def middleLevelNode(): Unit = {
		if (this.root == null)
		{
			// When tree is empty
			return;
		}
		// Auxiliary queue which is capable to contain a tree level nodes
		var q1: MyQueue = new MyQueue();
		var q2: MyQueue = new MyQueue();
		// Auxiliary temp variable
		var temp: TreeNode = null;
		var level: Int = 1;
		// It will be use assemble a level node.
		var record: ArrayBuffer[Int] = new ArrayBuffer[Int]();
		// Add first node in q1
		q1.enqueue(this.root);
		// This loop execute until auxiliary queue q1 and q2 are not empty
		while (!q1.isEmpty() || !q2.isEmpty())
		{
			// Execute loop until q1 queue are not empty
			// And store the next level node in q2 queue
			while (!q1.isEmpty())
			{
				// Get top node of q1 queue
				temp = q1.peek();
				// Add node value
				record += temp.data;
				if (temp.left != null)
				{
					q2.enqueue(temp.left);
				}
				if (temp.right != null)
				{
					q2.enqueue(temp.right);
				}
				// Remove top element of q1 queue
				q1.dequeue();
			}
			printMiddleNode(record);
			record.clear();
			level += 1;
			// Execute loop until q2 queue are not empty
			// And store the next level node in q1 queue
			while (!q2.isEmpty())
			{
				// Get top node of q2 queue
				temp = q2.peek();
				// Add node value
				record += temp.data;
				if (temp.left != null)
				{
					q1.enqueue(temp.left);
				}
				if (temp.right != null)
				{
					q1.enqueue(temp.right);
				}
				// Remove top element of q2 queue
				q2.dequeue();
			}
			printMiddleNode(record);
			record.clear();
			level += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var tree: BinaryTree = new BinaryTree();
		/*
		    Create Binary Tree
		    -----------------
		         -6                            
		       /   \    
		      4    -7    
		     / \     \               
		    2   3     12
		       / \   /  \
		      10 -4 5    9
		     /     \      \
		    1      7      8
		*/
		tree.root = new TreeNode(-6);
		tree.root.left = new TreeNode(4);
		tree.root.left.right = new TreeNode(3);
		tree.root.left.right.left = new TreeNode(10);
		tree.root.left.right.left.left = new TreeNode(1);
		tree.root.left.right.right = new TreeNode(-4);
		tree.root.left.right.right.right = new TreeNode(7);
		tree.root.left.left = new TreeNode(2);
		tree.root.right = new TreeNode(-7);
		tree.root.right.right = new TreeNode(12);
		tree.root.right.right.left = new TreeNode(5);
		tree.root.right.right.right = new TreeNode(9);
		tree.root.right.right.right.right = new TreeNode(8);
		tree.middleLevelNode();
	}
}

input

 -6
 4 -7
 3
 -4 5
 7
// Swift 4 program for
// Print the middle nodes of each level of a binary tree

// Binary Tree node
class TreeNode
{
	var data: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ data: Int)
	{
		// Set node value
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
// Queue Node
class QNode
{
	var n: TreeNode? ;
	var next: QNode? ;
	init(_ n: TreeNode? )
	{
		self.n = n;
		self.next = nil;
	}
}
//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(_ n: TreeNode? )
	{
		let node: QNode = QNode(n);
		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()->TreeNode?
	{
		if (self.isSize() == 0)
		{
			return nil;
		}
		else
		{
			return self.front!.n;
		}
	}
}
// Define Binary Tree
class BinaryTree
{
	var root: TreeNode? ;
	init()
	{
		self.root = nil;
	}
	// Print the middle element of given level
	func printMiddleNode(_ level: [Int] )
	{
		if (level.count > 0)
		{
			let middle: Int = level.count / 2;
			if ((level.count % 2) == 0)
			{
				// When two middle element possible
				print("\n ", level[middle - 1], terminator: "");
				print(" ", level[middle], terminator: "");
			}
			else
			{
				print("\n ", level[middle], terminator: "");
			}
		}
	}
	// This is display middle node of each level in binary tree
	func middleLevelNode()
	{
		if (self.root == nil)
		{
			// When tree is empty
			return;
		}
		// Auxiliary queue which is capable to contain a tree level nodes
		let q1: MyQueue = MyQueue();
		let q2: MyQueue = MyQueue();
		// Auxiliary temp variable
		var temp: TreeNode? = nil;
		var level: Int = 1;
		// It will be use assemble a level node.
		var record: [Int] = [Int]();
		// Add first node in q1
		q1.enqueue(self.root);
		// This loop execute until auxiliary queue q1 and q2 are not empty
		while (!q1.isEmpty() || !q2.isEmpty())
		{
			// Execute loop until q1 queue are not empty
			// And store the next level node in q2 queue
			while (!q1.isEmpty())
			{
				// Get top node of q1 queue
				temp = q1.peek();
				// Add node value
				record.append(temp!.data);
				if (temp!.left  != nil)
				{
					q2.enqueue(temp!.left);
				}
				if (temp!.right  != nil)
				{
					q2.enqueue(temp!.right);
				}
				// Remove top element of q1 queue
				q1.dequeue();
			}
			self.printMiddleNode(record);
			record.removeAll();
			level += 1;
			// Execute loop until q2 queue are not empty
			// And store the next level node in q1 queue
			while (!q2.isEmpty())
			{
				// Get top node of q2 queue
				temp = q2.peek();
				// Add node value
				record.append(temp!.data);
				if (temp!.left  != nil)
				{
					q1.enqueue(temp!.left);
				}
				if (temp!.right  != nil)
				{
					q1.enqueue(temp!.right);
				}
				// Remove top element of q2 queue
				q2.dequeue();
			}
			self.printMiddleNode(record);
			record.removeAll();
			level += 1;
		}
	}
}
func main()
{
	let tree: BinaryTree = BinaryTree();
	/*
	    Create Binary Tree
	    -----------------
	         -6                            
	       /   \    
	      4    -7    
	     / \     \               
	    2   3     12
	       / \   /  \
	      10 -4 5    9
	     /     \      \
	    1      7      8
	*/
	tree.root = TreeNode(-6);
	tree.root!.left = TreeNode(4);
	tree.root!.left!.right = TreeNode(3);
	tree.root!.left!.right!.left = TreeNode(10);
	tree.root!.left!.right!.left!.left = TreeNode(1);
	tree.root!.left!.right!.right = TreeNode(-4);
	tree.root!.left!.right!.right!.right = TreeNode(7);
	tree.root!.left!.left = TreeNode(2);
	tree.root!.right = TreeNode(-7);
	tree.root!.right!.right = TreeNode(12);
	tree.root!.right!.right!.left = TreeNode(5);
	tree.root!.right!.right!.right = TreeNode(9);
	tree.root!.right!.right!.right!.right = TreeNode(8);
	tree.middleLevelNode();
}
main();

input

  -6
  4  -7
  3
  -4  5
  7
// Kotlin program for
// Print the middle nodes of each level of a binary tree

// Binary Tree node
class TreeNode
{
	var data: Int;
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(data: Int)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Queue Node
class QNode
{
	var n: TreeNode ? ;
	var next: QNode ? ;
	constructor(n: TreeNode ? )
	{
		this.n = n;
		this.next = null;
	}
}
//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(n: TreeNode ? ): Unit
	{
		val node: QNode = QNode(n);
		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(): TreeNode ?
	{
		if (this.isSize() == 0)
		{
			return null;
		}
		else
		{
			return this.front?.n;
		}
	}
}
// Define Binary Tree
class BinaryTree
{
	var root: TreeNode ? ;
	constructor()
	{
		this.root = null;
	}
	// Print the middle element of given level
	fun printMiddleNode(level: MutableList<Int> ): Unit
	{
		if (level.size > 0)
		{
			val middle: Int = level.size / 2;
			if ((level.size % 2) == 0)
			{
				// When two middle element possible
				print("\n " + level[middle - 1]);
				print(" " + level[middle]);
			}
			else
			{
				print("\n " + level[middle]);
			}
		}
	}
	// This is display middle node of each level in binary tree
	fun middleLevelNode(): Unit
	{
		if (this.root == null)
		{
			// When tree is empty
			return;
		}
		// Auxiliary queue which is capable to contain a tree level nodes
		val q1: MyQueue = MyQueue();
		val q2: MyQueue = MyQueue();
		// Auxiliary temp variable
		var temp: TreeNode ? ;
		var level: Int = 1;
		// It will be use assemble a level node.
		var record = mutableListOf<Int>();
		// Add first node in q1
		q1.enqueue(this.root);
		// This loop execute until auxiliary queue q1 and q2 are not empty
		while (!q1.isEmpty() || !q2.isEmpty())
		{
			// Execute loop until q1 queue are not empty
			// And store the next level node in q2 queue
			while (!q1.isEmpty())
			{
				// Get top node of q1 queue
				temp = q1.peek();
				// Add node value
				record.add(temp!!.data);
				if (temp.left != null)
				{
					q2.enqueue(temp.left);
				}
				if (temp.right != null)
				{
					q2.enqueue(temp.right);
				}
				// Remove top element of q1 queue
				q1.dequeue();
			}
			this.printMiddleNode(record);
			record.clear();
			level += 1;
			// Execute loop until q2 queue are not empty
			// And store the next level node in q1 queue
			while (!q2.isEmpty())
			{
				// Get top node of q2 queue
				temp = q2.peek();
				// Add node value
				record.add(temp!!.data);
				if (temp.left != null)
				{
					q1.enqueue(temp.left);
				}
				if (temp.right != null)
				{
					q1.enqueue(temp.right);
				}
				// Remove top element of q2 queue
				q2.dequeue();
			}
			this.printMiddleNode(record);
			record.clear();
			level += 1;
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val tree: BinaryTree = BinaryTree();
	/*
	    Create Binary Tree
	    -----------------
	         -6                            
	       /   \    
	      4    -7    
	     / \     \               
	    2   3     12
	       / \   /  \
	      10 -4 5    9
	     /     \      \
	    1      7      8
	*/
	tree.root = TreeNode(-6);
	tree.root?.left = TreeNode(4);
	tree.root?.left?.right = TreeNode(3);
	tree.root?.left?.right?.left = TreeNode(10);
	tree.root?.left?.right?.left?.left = TreeNode(1);
	tree.root?.left?.right?.right = TreeNode(-4);
	tree.root?.left?.right?.right?.right = TreeNode(7);
	tree.root?.left?.left = TreeNode(2);
	tree.root?.right = TreeNode(-7);
	tree.root?.right?.right = TreeNode(12);
	tree.root?.right?.right?.left = TreeNode(5);
	tree.root?.right?.right?.right = TreeNode(9);
	tree.root?.right?.right?.right?.right = TreeNode(8);
	tree.middleLevelNode();
}

input

 -6
 4 -7
 3
 -4 5
 7

Time Complexity

The time complexity of this approach is O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once during the level order traversal. The insertion and removal operations in the queues take constant time.

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