Posted on by Kalkicode
Code Queue

# Print the nodes at odd levels of a tree

The problem is to print the nodes at odd levels of a binary tree. In a binary tree, the root node is considered to be at level 1, its children are at level 2, their children are at level 3, and so on. We need to traverse the tree level by level and print the nodes that are at odd levels.

## Problem Statement

Given a binary tree, we need to print the nodes that are at odd levels. For example, consider the following binary tree:

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

``````

The output for this tree would be:

``````
Odd Level Nodes
10 4 9 5 2 8 -3
``````

## Idea to Solve

To solve this problem, we can use a breadth-first search (BFS) approach. We will traverse the binary tree level by level using a queue. At each level, we check whether the level is odd or even. If it is odd, we print the nodes at that level.

## Pseudocode

``````
// Function to print the nodes at odd levels of a binary tree
function printNodesAtOddLevels(root):
if root is null:
// Empty binary tree
return

// Create a queue to perform BFS
queue = emptyQueue()

// Enqueue the root node along with its level (level 1)
queue.enqueue(root, 1)

// While the queue is not empty
while queue is not empty:
// Dequeue a node and its level
node, level = queue.dequeue()

// Check if the level is odd
if level is odd:
// Print the node's data
print node.data

// Enqueue the left child with the next level (level + 1)
if node.left is not null:
queue.enqueue(node.left, level + 1)

// Enqueue the right child with the next level (level + 1)
if node.right is not null:
queue.enqueue(node.right, level + 1)

``````
1. Create a custom queue `MyQueue` with methods `enqueue`, `dequeue`, and `is_empty`.
2. Create a method `odd_level_nodes()` in the `BinaryTree` class to perform the BFS and print the nodes at odd levels.
3. Initialize a counter variable `level` to 1.
4. Enqueue the root node of the binary tree with level 1 into the custom queue.
5. Print "Odd Level Nodes".
6. While the custom queue is not empty:
• Dequeue a node from the front of the custom queue.
• If the level is odd, print the node's data.
• Enqueue the left child and right child (if they exist) of the dequeued node into the custom queue with level + 1.
• Dequeue a node from the front of the queue.
7. Continue the loop until the queue is empty.

## Algorithm Explanation

The provided code already implements the above pseudocode using the `MyQueue` class and the `odd_level_nodes()` method. The custom queue `MyQueue` is used to traverse the binary tree level by level. At each level, the nodes are checked if they are at odd levels, and their data is printed accordingly.

## Code Solution

Here given code implementation process.

``````// C program
// Print the nodes at odd 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 odd level nodes in binary tree
void odd_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 odd 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

-----------------------
*/
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->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);
odd_level_nodes(root);
return 0;
}``````

#### Output

`````` Odd Level Nodes
10 4 9 5 2 8 -3``````
``````/*
Java program
Print the nodes at odd 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
{
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 odd level nodes in binary tree
public void odd_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 Odd 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)
{
queue.enqueue(node.left, level + 1);
}
if (node.right != null)
{
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

-----------------------
*/
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.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.odd_level_nodes();
}
}``````

#### Output

`````` Odd Level Nodes
10  4  9  5  2  8  -3``````
``````//Include header file
#include <iostream>
using namespace std;

/*
C++ program
Print the nodes at odd 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
{
this->tail->next = new_node;
}
this->tail = new_node;
}
//Delete first node of queue
void dequeue()
{
if (this->front != NULL)
{
if (this->tail == this->front)
{
this->tail = NULL;
this->front = NULL;
}
else
{
this->front = this->front->next;
}
}
}
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 odd level nodes in binary tree
void odd_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 Odd 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)
{
queue.enqueue(node->left, level + 1);
}
if (node->right != NULL)
{
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->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.odd_level_nodes();
return 0;
}``````

#### Output

`````` Odd Level Nodes
10  4  9  5  2  8  -3``````
``````//Include namespace system
using System;

/*
C# program
Print the nodes at odd 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
{
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 odd level nodes in binary tree
public void odd_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 Odd 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)
{
queue.enqueue(node.left, level + 1);
}
if (node.right != null)
{
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.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.odd_level_nodes();
}
}``````

#### Output

`````` Odd Level Nodes
10  4  9  5  2  8  -3``````
``````<?php
/*
Php program
Print the nodes at odd 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
{
\$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 odd level nodes in binary tree
public	function odd_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 Odd 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)
{
\$queue->enqueue(\$node->left, \$level + 1);
}
if (\$node->right != null)
{
\$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

-----------------------
*/
\$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->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->odd_level_nodes();
}
main();``````

#### Output

`````` Odd Level Nodes
10  4  9  5  2  8  -3``````
``````/*
Node Js program
Print the nodes at odd 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
{
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 odd level nodes in binary tree
odd_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 Odd 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)
{
queue.enqueue(node.left, level + 1);
}
if (node.right != null)
{
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

-----------------------
*/
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.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.odd_level_nodes();
}
main();``````

#### Output

`````` Odd Level Nodes
10  4  9  5  2  8  -3``````
``````#   Python 3 program
#   Print the nodes at odd 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 odd level nodes in binary tree
def odd_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 Odd 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) :
queue.enqueue(node.left, level + 1)

if (node.right != None) :
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
# 		-----------------------
#

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.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.odd_level_nodes()

if __name__ == "__main__": main()``````

#### Output

`````` Odd Level Nodes
10   4   9   5   2   8   -3``````
``````#   Ruby program
#   Print the nodes at odd levels of a tree

# Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
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_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_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_accessor :root

def initialize()
# set initial tree root to null
self.root = nil
end

# print all odd level nodes in binary tree
def odd_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 Odd 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)
queue.enqueue(node.left, level + 1)
end

if (node.right != nil)
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
# 		-----------------------
#

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.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.odd_level_nodes()
end

main()``````

#### Output

`````` Odd Level Nodes
10  4  9  5  2  8  -3``````
``````/*
Scala program
Print the nodes at odd 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
{
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 odd level nodes in binary tree
def odd_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 Odd 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)
{
queue.enqueue(node.left, level + 1);
}
if (node.right != null)
{
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

-----------------------
*/
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.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.odd_level_nodes();
}
}``````

#### Output

`````` Odd Level Nodes
10  4  9  5  2  8  -3``````
``````/*
Swift 4 program
Print the nodes at odd 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
{
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 odd level nodes in binary tree
func odd_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 Odd 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)
{
queue.enqueue(node!.left, level + 1);
}
if (node!.right != nil)
{
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!.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.odd_level_nodes();
}
main();``````

#### Output

`````` Odd Level Nodes
10   4   9   5   2   8   -3``````

## Resultant Output Explanation

The output shows the nodes at odd levels of the binary tree. The nodes are traversed level by level, and only the nodes at odd levels are printed. For the given binary tree, the nodes at odd levels are 10, 4, 9, 5, 2, 8, and -3, which are printed in that order.

## Time Complexity

The time complexity of the algorithm is O(N), where N is the number of nodes in the binary tree. This is because each node is visited once during the BFS traversal. The BFS traversal takes linear time with respect to the number of nodes in the tree, resulting in O(N) time complexity.

## 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.

Categories
Relative Post