Skip to main content

Print the nodes at even levels of a tree

The given problem involves printing the nodes of a binary tree that are at even levels. In a binary tree, the root is considered to be at level 1, its children are at level 2, and so on. The even-level nodes are the nodes present at levels with even numbers.

Problem Statement

Given a binary tree, we need to print the values of all nodes that are at even levels.

Explanation with Example

Consider the binary tree provided in the code:


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

The nodes at even levels in this tree are 2, 3, 7, 3, 6, 11, -1, 9, and -6.

Idea to Solve the Problem

To print the nodes at even levels, we can perform a level-order traversal of the binary tree using a queue. We start from the root and enqueue its children. At each level, we enqueue the children of the nodes present in the queue while keeping track of their levels. If the level is even, we print the value of that node.

Pseudocode

Here's the pseudocode to print the nodes at even levels of a binary tree:

1. Function insert(data)
2.     Create a new binary tree node new_node
3.     Set new_node's data to data
4.     Set new_node's left and right pointers to NULL
5.     Return new_node
6. End Function

7. Function enqueue(tree_node)
8.     Create a new queue node new_node
9.     Set new_node's element to tree_node
10.    Set new_node's next pointer to NULL
11.    Return new_node
12. End Function

13. Function dequeue(front)
14.    if front is not NULL
15.        Create a pointer remove and set it to front
16.        Set front to front's next node
17.        Set remove's element and next pointers to NULL
18.        Free remove
19.    End If
20. End Function

21. Function even_level_nodes(root)
22.    if root is not NULL
23.        Create two pointers front and tail, set both to NULL
24.        Set front to enqueue(root)
25.        Set front's level to 1
26.        Set tail to front
27.        Create a pointer node, set it to NULL
28.        Print "Even Level Nodes"
29.        while front is not NULL
30.            Set node to front's element
31.            if node's left child is not NULL
32.                Set tail's next to enqueue(node's left child)
33.                Set tail's next's level to front's level + 1
34.                Set tail to tail's next
35.            End If
36.            if node's right child is not NULL
37.                Set tail's next to enqueue(node's right child)
38.                Set tail's next's level to front's level + 1
39.                Set tail to tail's next
40.            End If
41.            if front's level is even
42.                Print node's data
43.            End If
44.            Call dequeue(front)
45.        End While
46.    End If
47. End Function

48. Main
49.    Create a pointer root and set it to NULL
50.    Add nodes to the binary tree (as provided in the example)
51.    Call even_level_nodes(root)
52. End Main

Algorithm Explanation

  1. The insert function creates a new binary tree node and returns its reference. It sets the data and initializes the left and right pointers to NULL.
  2. The enqueue function creates a new queue node and returns its reference. It sets the element and initializes the next pointer to NULL.
  3. The dequeue function removes the front node from the queue and frees its memory.
  4. The even_level_nodes function takes the root of the binary tree as input and performs a level-order traversal using a queue.
  5. It starts by enqueuing the root and setting its level to 1.
  6. It then iterates through the queue, dequeuing nodes, and enqueuing their children while keeping track of the levels.
  7. If the level is even, it prints the value of the node.

Code Solution

// C program
// Print the nodes at even levels of a tree 
#include <stdio.h>
#include <stdlib.h>

//Node of binary tree
struct Node
{
	int data;
	struct Node * left, * right;
};
struct MyQueue
{
	int level;
	struct Node * element;
	struct MyQueue * next;
};
//Create a binary tree nodes and node fields (data,pointer) 
//And returning the reference of newly nodes
struct Node * insert(int data)
{
	//create dynamic memory to new binary tree node
	struct Node * new_node = (struct Node * ) malloc(sizeof(struct Node));
	if (new_node != NULL)
	{
		//Set node value
		new_node->data = data;
		new_node->left = NULL;
		new_node->right = NULL;
	}
	else
	{
		printf("Memory Overflow\n");
	}
	//return reference
	return new_node;
}
//Create a queue node and returns this node
struct MyQueue * enqueue(struct Node * tree_node)
{
	//Make a new Queue node
	struct MyQueue * new_node = (struct MyQueue * ) malloc(sizeof(struct MyQueue));
	if (new_node != NULL)
	{
		//Set node values
		new_node->element = tree_node;
		new_node->next = NULL;
	}
	else
	{
		printf("Memory Overflow\n");
	}
	return new_node;
}
//Remove a queue elements
void dequeue(struct MyQueue ** front)
{
	if ( * front != NULL)
	{
		struct MyQueue * remove = * front;
		//Visit to next node
		* front = remove->next;
		remove->element = NULL;
		remove->next = NULL;
		//free node
		free(remove);
		remove = NULL;
	}
}
//print all even level nodes in binary tree
void even_level_nodes(struct Node * root)
{
	if (root != NULL)
	{
		// make a queue pointers
		struct MyQueue * front = NULL, * tail = NULL;
		// Get first node of tree
		front = enqueue(root);
		// Start level of first node is one
		front->level = 1;
		// Set tail node to first node
		tail = front;
		// Define a tree variable
		struct Node * node = NULL;
		printf(" Odd Level Nodes \n");
		// Traversal tree elements in level order
		while (front != NULL)
		{
			// Tree node
			node = front->element;
			if (node->left != NULL)
			{
				// Add new left child node
				tail->next = enqueue(node->left);
				tail->next->level = front->level + 1;
				tail = tail->next;
			}
			if (node->right != NULL)
			{
				// Add new right child node
				tail->next = enqueue(node->right);
				tail->next->level = front->level + 1;
				tail = tail->next;
			}
			if (front->level % 2 == 0)
			{
				// When get even level node
				printf(" %d", node->data);
			}
			dequeue( & front);
		}
		printf("\n");
		tail = NULL;
	}
	else
	{
		printf("\nEmpty Tree\n");
	}
}
int main()
{
	struct Node * root = NULL;
	/*  
	Construct Binary Tree
	-----------------------
	           10
	         /   \
	        2     3
	       /     / \
	      4     9   5
	     /  \    \    \
	    7    3    6   11
	        /  \     /
	       2    8  -3
	           / \   \   
	         -1   9   -6

	-----------------------
	*/
	//Add node
	root = insert(10);
	root->left = insert(2);
	root->right = insert(3);
	root->right->right = insert(5);
	root->right->left = insert(9);
	root->left->left = insert(4);
	root->left->left->left = insert(7);
	root->left->left->right = insert(3);
	root->right->left->right = insert(6);
	root->right->right->right = insert(11);
	root->right->right->right->left = insert(-3);
	root->right->right->right->left->right = insert(-6);
	root->left->left->right->left = insert(2);
	root->left->left->right->right = insert(8);
	root->left->left->right->right->left = insert(-1);
	root->left->left->right->right->right = insert(9);
	even_level_nodes(root);
	return 0;
}

Output

 Odd Level Nodes
 2 3 7 3 6 11 -1 9 -6
/* 
  Java program 
  Print the nodes at even levels of a 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 QueueNode
{
	public TreeNode element;
	public QueueNode next;
	public int level;
	public QueueNode(TreeNode element, int level)
	{
		this.element = element;
		this.next = null;
		this.level = level;
	}
}
//Define custom queue class
class MyQueue
{
	public QueueNode front;
	public QueueNode tail;
	public MyQueue()
	{
		this.front = null;
		this.tail = null;
	}
	//Add a new node at last of queue
	public void enqueue(TreeNode element, int level)
	{
		QueueNode new_node = new QueueNode(element, level);
		if (this.front == null)
		{
			//When first node of queue
			this.front = new_node;
		}
		else
		{
			//Add node at last position
			this.tail.next = new_node;
		}
		this.tail = new_node;
	}
	//Delete first node of queue
	public void dequeue()
	{
		if (this.front != null)
		{
			if (this.tail == this.front)
			{
				this.tail = null;
				this.front = null;
			}
			else
			{
				this.front = this.front.next;
			}
		}
	}
	public boolean is_empty()
	{
		if (this.front == null)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
}
class BinaryTree
{
	public TreeNode root;
	public BinaryTree()
	{
		//set initial tree root to null
		this.root = null;
	}
	//print all even level nodes in binary tree
	public void even_level_nodes()
	{
		if (this.root == null)
		{
			System.out.print("\n Empty Binary Tree \n");
		}
		else
		{
			//Get top node in tree
			TreeNode node = this.root;
			int level = 1;
			//Create a Queue
			MyQueue queue = new MyQueue();
			//Add first node at the level of one
			queue.enqueue(node, level);
			System.out.print("\n Even Level Nodes \n");
			//Execute loop until the queue is not empty
			while (queue.is_empty() == false)
			{
				node = queue.front.element;
				level = queue.front.level;
				if (node.left != null)
				{
					//Add left node
					queue.enqueue(node.left, level + 1);
				}
				if (node.right != null)
				{
					//Add right node
					queue.enqueue(node.right, level + 1);
				}
				if (level % 2 == 0)
				{
					System.out.print("  " + node.data);
				}
				//remove element into queue
				queue.dequeue();
			}
		}
	}
	public static void main(String[] args)
	{
		//Make object of Binary Tree
		BinaryTree tree = new BinaryTree();
		/*  
		Construct Binary Tree
		-----------------------
		           10
		         /   \
		        2     3
		       /     / \
		      4     9   5
		     /  \    \    \
		    7    3    6   11
		        /  \     /
		       2    8  -3
		           / \   \
		         -1   9   -6

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

Output

 Even Level Nodes
  2  3  7  3  6  11  -1  9  -3
//Include header file
#include <iostream>
using namespace std;

/*
  C++ program 
  Print the nodes at even levels of a 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 QueueNode
{
	public: 
    TreeNode *element;
	QueueNode *next;
	int level;
	QueueNode(TreeNode *element, int level)
	{
		this->element = element;
		this->next = NULL;
		this->level = level;
	}
};
//Define custom queue class
class MyQueue
{
	public: QueueNode *front;
	QueueNode *tail;
	MyQueue()
	{
		this->front = NULL;
		this->tail = NULL;
	}
	//Add a new node at last of queue
	void enqueue(TreeNode *element, int level)
	{
		QueueNode *new_node = new QueueNode(element, level);
		if (this->front == NULL)
		{
			//When first node of queue
			this->front = new_node;
		}
		else
		{
			//Add node at last position
			this->tail->next = new_node;
		}
		this->tail = new_node;
	}
	//Delete first node of queue
	void dequeue()
	{
		if (this->front != NULL)
		{	
          	QueueNode *node = this->front;
			if (this->tail == this->front)
			{  
				this->tail = NULL;
				this->front = NULL;
			}
			else
			{
				this->front = this->front->next;
			}
         	delete node;
		}
	}
	bool is_empty()
	{
		if (this->front == NULL)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
};
class BinaryTree
{
	public: TreeNode *root;
	BinaryTree()
	{
		//set initial tree root to null
		this->root = NULL;
	}
	//print all even level nodes in binary tree
	void even_level_nodes()
	{
		if (this->root == NULL)
		{
			cout << "\n Empty Binary Tree \n";
		}
		else
		{
			//Get top node in tree
			TreeNode *node = this->root;
			int level = 1;
			//Create a Queue
			MyQueue queue = MyQueue();
			//Add first node at the level of one
			queue.enqueue(node, level);
			cout << "\n Even Level Nodes \n";
			//Execute loop until the queue is not empty
			while (queue.is_empty() == false)
			{
				node = queue.front->element;
				level = queue.front->level;
				if (node->left != NULL)
				{
					//Add left node
					queue.enqueue(node->left, level + 1);
				}
				if (node->right != NULL)
				{
					//Add right node
					queue.enqueue(node->right, level + 1);
				}
				if (level % 2 == 0)
				{
					cout << "  " << node->data;
				}
				//remove element into queue
				queue.dequeue();
			}
		}
	}
};
int main()
{
	//Make object of Binary Tree
	BinaryTree tree = BinaryTree();
	tree.root = new TreeNode(10);
	tree.root->left = new TreeNode(2);
	tree.root->right = new TreeNode(3);
	tree.root->right->right = new TreeNode(5);
	tree.root->right->left = new TreeNode(9);
	tree.root->left->left = new TreeNode(4);
	tree.root->left->left->left = new TreeNode(7);
	tree.root->left->left->right = new TreeNode(3);
	tree.root->right->left->right = new TreeNode(6);
	tree.root->right->right->right = new TreeNode(11);
	tree.root->right->right->right->left = new TreeNode(-3);
	tree.root->right->right->right->left->right = new TreeNode(-3);
	tree.root->left->left->right->left = new TreeNode(2);
	tree.root->left->left->right->right = new TreeNode(8);
	tree.root->left->left->right->right->left = new TreeNode(-1);
	tree.root->left->left->right->right->right = new TreeNode(9);
	tree.even_level_nodes();
	return 0;
}

Output

 Even Level Nodes
  2  3  7  3  6  11  -1  9  -3
//Include namespace system
using System;

/* 
  C# program 
  Print the nodes at even levels of a 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 QueueNode
{
	public TreeNode element;
	public QueueNode next;
	public int level;
	public QueueNode(TreeNode element, int level)
	{
		this.element = element;
		this.next = null;
		this.level = level;
	}
}
//Define custom queue class
class MyQueue
{
	public QueueNode front;
	public QueueNode tail;
	public MyQueue()
	{
		this.front = null;
		this.tail = null;
	}
	//Add a new node at last of queue
	public void enqueue(TreeNode element, int level)
	{
		QueueNode new_node = new QueueNode(element, level);
		if (this.front == null)
		{
			//When first node of queue
			this.front = new_node;
		}
		else
		{
			//Add node at last position
			this.tail.next = new_node;
		}
		this.tail = new_node;
	}
	//Delete first node of queue
	public void dequeue()
	{
		if (this.front != null)
		{
			if (this.tail == this.front)
			{
				this.tail = null;
				this.front = null;
			}
			else
			{
				this.front = this.front.next;
			}
		}
	}
	public Boolean is_empty()
	{
		if (this.front == null)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
}
class BinaryTree
{
	public TreeNode root;
	public BinaryTree()
	{
		//set initial tree root to null
		this.root = null;
	}
	//print all even level nodes in binary tree
	public void even_level_nodes()
	{
		if (this.root == null)
		{
			Console.Write("\n Empty Binary Tree \n");
		}
		else
		{
			//Get top node in tree
			TreeNode node = this.root;
			int level = 1;
			//Create a Queue
			MyQueue queue = new MyQueue();
			//Add first node at the level of one
			queue.enqueue(node, level);
			Console.Write("\n Even Level Nodes \n");
			//Execute loop until the queue is not empty
			while (queue.is_empty() == false)
			{
				node = queue.front.element;
				level = queue.front.level;
				if (node.left != null)
				{
					//Add left node
					queue.enqueue(node.left, level + 1);
				}
				if (node.right != null)
				{
					//Add right node
					queue.enqueue(node.right, level + 1);
				}
				if (level % 2 == 0)
				{
					Console.Write("  " + node.data);
				}
				//remove element into queue
				queue.dequeue();
			}
		}
	}
	public static void Main(String[] args)
	{
		//Make object of Binary Tree
		BinaryTree tree = new BinaryTree();
		tree.root = new TreeNode(10);
		tree.root.left = new TreeNode(2);
		tree.root.right = new TreeNode(3);
		tree.root.right.right = new TreeNode(5);
		tree.root.right.left = new TreeNode(9);
		tree.root.left.left = new TreeNode(4);
		tree.root.left.left.left = new TreeNode(7);
		tree.root.left.left.right = new TreeNode(3);
		tree.root.right.left.right = new TreeNode(6);
		tree.root.right.right.right = new TreeNode(11);
		tree.root.right.right.right.left = new TreeNode(-3);
		tree.root.right.right.right.left.right = new TreeNode(-3);
		tree.root.left.left.right.left = new TreeNode(2);
		tree.root.left.left.right.right = new TreeNode(8);
		tree.root.left.left.right.right.left = new TreeNode(-1);
		tree.root.left.left.right.right.right = new TreeNode(9);
		tree.even_level_nodes();
	}
}

Output

 Even Level Nodes
  2  3  7  3  6  11  -1  9  -3
<?php
/* 
  Php program 
  Print the nodes at even levels of a tree 
*/
//Binary Tree node
class TreeNode
{
	public $data;
	public $left;
	public $right;

	function __construct($data)
	{
		//set node value
		$this->data = $data;
		$this->left = null;
		$this->right = null;
	}
}
// Queue Node
class QueueNode
{
	public $element;
	public $next;
	public $level;

	function __construct($element, $level)
	{
		$this->element = $element;
		$this->next = null;
		$this->level = $level;
	}
}
//Define custom queue class
class MyQueue
{
	public $front;
	public $tail;

	function __construct()
	{
		$this->front = null;
		$this->tail = null;
	}
	//Add a new node at last of queue
	public	function enqueue($element, $level)
	{
		$new_node = new QueueNode($element, $level);
		if ($this->front == null)
		{
			//When first node of queue
			$this->front = $new_node;
		}
		else
		{
			//Add node at last position
			$this->tail->next = $new_node;
		}
		$this->tail = $new_node;
	}
	//Delete first node of queue
	public	function dequeue()
	{
		if ($this->front != null)
		{
			if ($this->tail == $this->front)
			{
				$this->tail = null;
				$this->front = null;
			}
			else
			{
				$this->front = $this->front->next;
			}
		}
	}
	public	function is_empty()
	{
		if ($this->front == null)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
}
class BinaryTree
{
	public $root;

	function __construct()
	{
		//set initial tree root to null
		$this->root = null;
	}
	//print all even level nodes in binary tree
	public	function even_level_nodes()
	{
		if ($this->root == null)
		{
			echo "\n Empty Binary Tree \n";
		}
		else
		{
			//Get top node in tree
			$node = $this->root;
			$level = 1;
			//Create a Queue
			$queue = new MyQueue();
			//Add first node at the level of one
			$queue->enqueue($node, $level);
			echo "\n Even Level Nodes \n";
			//Execute loop until the queue is not empty
			while ($queue->is_empty() == false)
			{
				$node = $queue->front->element;
				$level = $queue->front->level;
				if ($node->left != null)
				{
					//Add left node
					$queue->enqueue($node->left, $level + 1);
				}
				if ($node->right != null)
				{
					//Add right node
					$queue->enqueue($node->right, $level + 1);
				}
				if ($level % 2 == 0)
				{
					echo "  ". $node->data;
				}
				//remove element into queue
				$queue->dequeue();
			}
		}
	}
}

function main()
{
	//Make object of Binary Tree
	$tree = new BinaryTree();
	/*  
			Construct Binary Tree
			-----------------------
			           10
			         /   \
			        2     3
			       /     / \
			      4     9   5
			     /  \    \    \
			    7    3    6   11
			        /  \     /
			       2    8  -3
			           / \   \
			         -1   9   -6

			-----------------------
			*/
	//Add node
	$tree->root = new TreeNode(10);
	$tree->root->left = new TreeNode(2);
	$tree->root->right = new TreeNode(3);
	$tree->root->right->right = new TreeNode(5);
	$tree->root->right->left = new TreeNode(9);
	$tree->root->left->left = new TreeNode(4);
	$tree->root->left->left->left = new TreeNode(7);
	$tree->root->left->left->right = new TreeNode(3);
	$tree->root->right->left->right = new TreeNode(6);
	$tree->root->right->right->right = new TreeNode(11);
	$tree->root->right->right->right->left = new TreeNode(-3);
	$tree->root->right->right->right->left->right = new TreeNode(-3);
	$tree->root->left->left->right->left = new TreeNode(2);
	$tree->root->left->left->right->right = new TreeNode(8);
	$tree->root->left->left->right->right->left = new TreeNode(-1);
	$tree->root->left->left->right->right->right = new TreeNode(9);
	$tree->even_level_nodes();
}
main();

Output

 Even Level Nodes
  2  3  7  3  6  11  -1  9  -3
/* 
  Node Js program 
  Print the nodes at even levels of a tree 
*/

//Binary Tree node
class TreeNode
{
	constructor(data)
	{
		//set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
// Queue Node
class QueueNode
{
	constructor(element, level)
	{
		this.element = element;
		this.next = null;
		this.level = level;
	}
}
//Define custom queue class
class MyQueue
{
	constructor()
	{
		this.front = null;
		this.tail = null;
	}
	//Add a new node at last of queue
	enqueue(element, level)
	{
		var new_node = new QueueNode(element, level);
		if (this.front == null)
		{
			//When first node of queue
			this.front = new_node;
		}
		else
		{
			//Add node at last position
			this.tail.next = new_node;
		}
		this.tail = new_node;
	}
	//Delete first node of queue
	dequeue()
	{
		if (this.front != null)
		{
			if (this.tail == this.front)
			{
				this.tail = null;
				this.front = null;
			}
			else
			{
				this.front = this.front.next;
			}
		}
	}
	is_empty()
	{
		if (this.front == null)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
}
class BinaryTree
{
	constructor()
	{
		//set initial tree root to null
		this.root = null;
	}
	//print all even level nodes in binary tree
	even_level_nodes()
	{
		if (this.root == null)
		{
			process.stdout.write("\n Empty Binary Tree \n");
		}
		else
		{
			//Get top node in tree
			var node = this.root;
			var level = 1;
			//Create a Queue
			var queue = new MyQueue();
			//Add first node at the level of one
			queue.enqueue(node, level);
			process.stdout.write("\n Even Level Nodes \n");
			//Execute loop until the queue is not empty
			while (queue.is_empty() == false)
			{
				node = queue.front.element;
				level = queue.front.level;
				if (node.left != null)
				{
					//Add left node
					queue.enqueue(node.left, level + 1);
				}
				if (node.right != null)
				{
					//Add right node
					queue.enqueue(node.right, level + 1);
				}
				if (level % 2 == 0)
				{
					process.stdout.write("  " + node.data);
				}
				//remove element into queue
				queue.dequeue();
			}
		}
	}
}

function main()
{
	//Make object of Binary Tree
	var tree = new BinaryTree();
	/*  
			Construct Binary Tree
			-----------------------
			           10
			         /   \
			        2     3
			       /     / \
			      4     9   5
			     /  \    \    \
			    7    3    6   11
			        /  \     /
			       2    8  -3
			           / \   \
			         -1   9   -6

			-----------------------
			*/
	//Add node
	tree.root = new TreeNode(10);
	tree.root.left = new TreeNode(2);
	tree.root.right = new TreeNode(3);
	tree.root.right.right = new TreeNode(5);
	tree.root.right.left = new TreeNode(9);
	tree.root.left.left = new TreeNode(4);
	tree.root.left.left.left = new TreeNode(7);
	tree.root.left.left.right = new TreeNode(3);
	tree.root.right.left.right = new TreeNode(6);
	tree.root.right.right.right = new TreeNode(11);
	tree.root.right.right.right.left = new TreeNode(-3);
	tree.root.right.right.right.left.right = new TreeNode(-3);
	tree.root.left.left.right.left = new TreeNode(2);
	tree.root.left.left.right.right = new TreeNode(8);
	tree.root.left.left.right.right.left = new TreeNode(-1);
	tree.root.left.left.right.right.right = new TreeNode(9);
	tree.even_level_nodes();
}
main();

Output

 Even Level Nodes
  2  3  7  3  6  11  -1  9  -3
#   Python 3 program 
#   Print the nodes at even levels of a 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 QueueNode :
	
	def __init__(self, element, level) :
		self.element = element
		self.next = None
		self.level = level
	

# Define custom queue class
class MyQueue :
	
	def __init__(self) :
		self.front = None
		self.tail = None
	
	# Add a new node at last of queue
	def enqueue(self, element, level) :
		new_node = QueueNode(element, level)
		if (self.front == None) :
			# When first node of queue
			self.front = new_node
		else :
			# Add node at last position
			self.tail.next = new_node
		
		self.tail = new_node
	
	# Delete first node of queue
	def dequeue(self) :
		if (self.front != None) :
			if (self.tail == self.front) :
				self.tail = None
				self.front = None
			else :
				self.front = self.front.next
			
		
	
	def is_empty(self) :
		if (self.front == None) :
			return True
		else :
			return False
		
	

class BinaryTree :
	
	def __init__(self) :
		# set initial tree root to null
		self.root = None
	
	# print all even level nodes in binary tree
	def even_level_nodes(self) :
		if (self.root == None) :
			print("\n Empty Binary Tree \n", end = "")
		else :
			# Get top node in tree
			node = self.root
			level = 1
			# Create a Queue
			queue = MyQueue()
			# Add first node at the level of one
			queue.enqueue(node, level)
			print("\n Even Level Nodes \n", end = "")
			# Execute loop until the queue is not empty
			while (queue.is_empty() == False) :
				node = queue.front.element
				level = queue.front.level
				if (node.left != None) :
					# Add left node
					queue.enqueue(node.left, level + 1)
				
				if (node.right != None) :
					# Add right node
					queue.enqueue(node.right, level + 1)
				
				if (level % 2 == 0) :
					print("  ", node.data, end = "")
				
				# remove element into queue
				queue.dequeue()
			
		
	

def main() :
	# Make object of Binary Tree
	tree = BinaryTree()
	#   
	# 		Construct Binary Tree
	# 		-----------------------
	# 		           10
	# 		         /   \
	# 		        2     3
	# 		       /     / \
	# 		      4     9   5
	# 		     /  \    \    \
	# 		    7    3    6   11
	# 		        /  \     /
	# 		       2    8  -3
	# 		           / \   \
	# 		         -1   9   -6
	# 		-----------------------
	# 		
	
	# Add node
	tree.root = TreeNode(10)
	tree.root.left = TreeNode(2)
	tree.root.right = TreeNode(3)
	tree.root.right.right = TreeNode(5)
	tree.root.right.left = TreeNode(9)
	tree.root.left.left = TreeNode(4)
	tree.root.left.left.left = TreeNode(7)
	tree.root.left.left.right = TreeNode(3)
	tree.root.right.left.right = TreeNode(6)
	tree.root.right.right.right = TreeNode(11)
	tree.root.right.right.right.left = TreeNode(-3)
	tree.root.right.right.right.left.right = TreeNode(-3)
	tree.root.left.left.right.left = TreeNode(2)
	tree.root.left.left.right.right = TreeNode(8)
	tree.root.left.left.right.right.left = TreeNode(-1)
	tree.root.left.left.right.right.right = TreeNode(9)
	tree.even_level_nodes()

if __name__ == "__main__": main()

Output

 Even Level Nodes
   2   3   7   3   6   11   -1   9   -3
#   Ruby program 
#   Print the nodes at even levels of a 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 QueueNode  
	# Define the accessor and reader of class QueueNode  
	attr_reader :element, :next, :level
	attr_accessor :element, :next, :level
 
	
	def initialize(element, level) 
		self.element = element
		self.next = nil
		self.level = level
	end

end

# Define custom queue class
class MyQueue  
	# Define the accessor and reader of class MyQueue  
	attr_reader :front, :tail
	attr_accessor :front, :tail
 
	
	def initialize() 
		self.front = nil
		self.tail = nil
	end

	# Add a new node at last of queue
	def enqueue(element, level) 
		new_node = QueueNode.new(element, level)
		if (self.front == nil) 
			# When first node of queue
			self.front = new_node
		else 
			# Add node at last position
			self.tail.next = new_node
		end

		self.tail = new_node
	end

	# Delete first node of queue
	def dequeue() 
		if (self.front != nil) 
			if (self.tail == self.front) 
				self.tail = nil
				self.front = nil
			else 
				self.front = self.front.next
			end

		end

	end

	def is_empty() 
		if (self.front == nil) 
			return true
		else 
			return false
		end

	end

end

class BinaryTree  
	# Define the accessor and reader of class BinaryTree  
	attr_reader :root
	attr_accessor :root
 
	
	def initialize() 
		# set initial tree root to null
		self.root = nil
	end

	# print all even level nodes in binary tree
	def even_level_nodes() 
		if (self.root == nil) 
			print("\n Empty Binary Tree \n")
		else 
			# Get top node in tree
			node = self.root
			level = 1
			# Create a Queue
			queue = MyQueue.new()
			# Add first node at the level of one
			queue.enqueue(node, level)
			print("\n Even Level Nodes \n")
			# Execute loop until the queue is not empty
			while (queue.is_empty() == false) 
				node = queue.front.element
				level = queue.front.level
				if (node.left != nil) 
					# Add left node
					queue.enqueue(node.left, level + 1)
				end

				if (node.right != nil) 
					# Add right node
					queue.enqueue(node.right, level + 1)
				end

				if (level % 2 == 0) 
					print("  ", node.data)
				end

				# remove element into queue
				queue.dequeue()
			end

		end

	end

end

def main() 
	# Make object of Binary Tree
	tree = BinaryTree.new()
	#   
	# 		Construct Binary Tree
	# 		-----------------------
	# 		           10
	# 		         /   \
	# 		        2     3
	# 		       /     / \
	# 		      4     9   5
	# 		     /  \    \    \
	# 		    7    3    6   11
	# 		        /  \     /
	# 		       2    8  -3
	# 		           / \   \
	# 		         -1   9   -6
	# 		-----------------------
	# 		
	
	# Add node
	tree.root = TreeNode.new(10)
	tree.root.left = TreeNode.new(2)
	tree.root.right = TreeNode.new(3)
	tree.root.right.right = TreeNode.new(5)
	tree.root.right.left = TreeNode.new(9)
	tree.root.left.left = TreeNode.new(4)
	tree.root.left.left.left = TreeNode.new(7)
	tree.root.left.left.right = TreeNode.new(3)
	tree.root.right.left.right = TreeNode.new(6)
	tree.root.right.right.right = TreeNode.new(11)
	tree.root.right.right.right.left = TreeNode.new(-3)
	tree.root.right.right.right.left.right = TreeNode.new(-3)
	tree.root.left.left.right.left = TreeNode.new(2)
	tree.root.left.left.right.right = TreeNode.new(8)
	tree.root.left.left.right.right.left = TreeNode.new(-1)
	tree.root.left.left.right.right.right = TreeNode.new(9)
	tree.even_level_nodes()
end

main()

Output

 Even Level Nodes 
  2  3  7  3  6  11  -1  9  -3
/* 
  Scala program 
  Print the nodes at even levels of a tree 
*/

//Binary Tree node
class TreeNode(var data: Int,
	var left: TreeNode,
		var right: TreeNode)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
// Queue Node
class QueueNode(var element: TreeNode,
	var next: QueueNode,
		var level: Int)
{
	def this(element: TreeNode, level: Int)
	{
		this(element, null, level);
	}
}
//Define custom queue class
class MyQueue(var front: QueueNode,
	var tail: QueueNode)
{
	def this()
	{
		this(null, null);
	}
	//Add a new node at last of queue
	def enqueue(element: TreeNode, level: Int): Unit = {
		var new_node: QueueNode = new QueueNode(element, level);
		if (this.front == null)
		{
			//When first node of queue
			this.front = new_node;
		}
		else
		{
			//Add node at last position
			this.tail.next = new_node;
		}
		this.tail = new_node;
	}
	//Delete first node of queue
	def dequeue(): Unit = {
		if (this.front != null)
		{
			if (this.tail == this.front)
			{
				this.tail = null;
				this.front = null;
			}
			else
			{
				this.front = this.front.next;
			}
		}
	}
	def is_empty(): Boolean = {
		if (this.front == null)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
}
class BinaryTree(var root: TreeNode)
{
	def this()
	{
		this(null);
	}
	//print all even level nodes in binary tree
	def even_level_nodes(): Unit = {
		if (this.root == null)
		{
			print("\n Empty Binary Tree \n");
		}
		else
		{
			//Get top node in tree
			var node: TreeNode = this.root;
			var level: Int = 1;
			//Create a Queue
			var queue: MyQueue = new MyQueue();
			//Add first node at the level of one
			queue.enqueue(node, level);
			print("\n Even Level Nodes \n");
			//Execute loop until the queue is not empty
			while (queue.is_empty() == false)
			{
				node = queue.front.element;
				level = queue.front.level;
				if (node.left != null)
				{
					//Add left node
					queue.enqueue(node.left, level + 1);
				}
				if (node.right != null)
				{
					//Add right node
					queue.enqueue(node.right, level + 1);
				}
				if (level % 2 == 0)
				{
					print("  " + node.data);
				}
				//remove element into queue
				queue.dequeue();
			}
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		//Make object of Binary Tree
		var tree: BinaryTree = new BinaryTree();
		/*  
				Construct Binary Tree
				-----------------------
				           10
				         /   \
				        2     3
				       /     / \
				      4     9   5
				     /  \    \    \
				    7    3    6   11
				        /  \     /
				       2    8  -3
				           / \   \
				         -1   9   -6

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

Output

 Even Level Nodes
  2  3  7  3  6  11  -1  9  -3
/* 
  Swift 4 program 
  Print the nodes at even levels of a 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 QueueNode
{
	var element: TreeNode? ;
	var next: QueueNode? ;
	var level: Int;
	init(_ element: TreeNode? , _ level : Int)
	{
		self.element = element;
		self.next = nil;
		self.level = level;
	}
}
//Define custom queue class
class MyQueue
{
	var front: QueueNode? ;
	var tail: QueueNode? ;
	init()
	{
		self.front = nil;
		self.tail = nil;
	}
	//Add a new node at last of queue
	func enqueue(_ element: TreeNode? , _ level : Int)
	{
		let new_node: QueueNode? = QueueNode(element, level);
		if (self.front == nil)
		{
			//When first node of queue
			self.front = new_node;
		}
		else
		{
			//Add node at last position
			self.tail!.next = new_node;
		}
		self.tail = new_node;
	}
	//Delete first node of queue
	func dequeue()
	{
		if (self.front != nil)
		{
			if (self.tail === self.front)
			{
				self.tail = nil;
				self.front = nil;
			}
			else
			{
				self.front = self.front!.next;
			}
		}
	}
	func is_empty() -> Bool
	{
		if (self.front == nil)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
}
class BinaryTree
{
	var root: TreeNode? ;
	init()
	{
		//set initial tree root to null
		self.root = nil;
	}
	//print all even level nodes in binary tree
	func even_level_nodes()
	{
		if (self.root == nil)
		{
			print("\n Empty Binary Tree \n", terminator: "");
		}
		else
		{
			//Get top node in tree
			var node: TreeNode? = self.root;
			var level: Int = 1;
			//Create a Queue
			let queue: MyQueue = MyQueue();
			//Add first node at the level of one
			queue.enqueue(node, level);
			print("\n Even Level Nodes \n", terminator: "");
			//Execute loop until the queue is not empty
			while (queue.is_empty() == false)
			{
				node = queue.front!.element;
				level = queue.front!.level;
				if (node!.left != nil)
				{
					//Add left node
					queue.enqueue(node!.left, level + 1);
				}
				if (node!.right != nil)
				{
					//Add right node
					queue.enqueue(node!.right, level + 1);
				}
				if (level % 2 == 0)
				{
					print("  ", node!.data, terminator: "");
				}
				//remove element into queue
				queue.dequeue();
			}
		}
	}
}
func main()
{
	//Make object of Binary Tree
	let tree: BinaryTree = BinaryTree();
	tree.root = TreeNode(10);
	tree.root!.left = TreeNode(2);
	tree.root!.right = TreeNode(3);
	tree.root!.right!.right = TreeNode(5);
	tree.root!.right!.left = TreeNode(9);
	tree.root!.left!.left = TreeNode(4);
	tree.root!.left!.left!.left = TreeNode(7);
	tree.root!.left!.left!.right = TreeNode(3);
	tree.root!.right!.left!.right = TreeNode(6);
	tree.root!.right!.right!.right = TreeNode(11);
	tree.root!.right!.right!.right!.left = TreeNode(-3);
	tree.root!.right!.right!.right!.left!.right = TreeNode(-3);
	tree.root!.left!.left!.right!.left = TreeNode(2);
	tree.root!.left!.left!.right!.right = TreeNode(8);
	tree.root!.left!.left!.right!.right!.left = TreeNode(-1);
	tree.root!.left!.left!.right!.right!.right = TreeNode(9);
	tree.even_level_nodes();
}
main();

Output

 Even Level Nodes
   2   3   7   3   6   11   -1   9   -3

Resultant Output Explanation

The program executes the even_level_nodes function and prints the nodes at even levels for the given binary tree. The output is:

Even Level Nodes
2 3 7 3 6 11 -1 9 -6

These are the values of the nodes at even levels in the given binary tree.

Time Complexity

The time complexity of the code is O(n), where 'n' is the number of nodes in the binary tree. This is because we visit each node once during the level-order traversal using the queue. The time complexity of enqueue and dequeue operations is O(1) since we are using a simple linked list-based queue. Therefore, the overall time complexity is linear.

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment