Print alternate nodes in level order of a binary tree
In this problem, we are given a binary tree, and we are required to print all the alternate nodes in level order. In level order traversal, we visit the nodes level by level, from left to right.
Example
Consider the following binary tree:
10
/ \
2 3
/ / \
4 9 5
/ \ \ \
7 3 6 20
/ \ /
2 8 -8
The alternate nodes in level order are: 10, 3, 9, 7, 6, 2, -8
Idea to Solve the Problem
To print the alternate nodes in level order, we can perform a level order traversal of the binary tree using a custom queue data structure. For each level, we can print the alternate nodes based on a flag. We alternate the flag value for each level, so that alternate nodes are printed.
Code Solution
// C program
// Print alternate nodes in level order of a binary 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 alternate nodes in binary tree in level order
void print_alternate_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;
// Result indicator
int status = 1;
printf(" Alternate 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 (status == 1)
{
// When get alternate node
printf(" %d", node->data);
// Change selection
status = 0;
}
else
{
// Change selection
status = 1;
}
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 20
/ \ /
2 8 -8
-----------------------
*/
//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(20);
root->right->right->right->left = insert(-8);
root->left->left->right->left = insert(2);
root->left->left->right->right = insert(8);
print_alternate_nodes(root);
return 0;
}
Output
Alternate Nodes
10 3 9 7 6 2 -8
/*
Java program
Print alternate nodes in level order 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 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 alternate nodes in binary tree in level order
public void print_alternate_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);
// Result indicator
boolean status = true;
//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 (status == true)
{
status = false;
System.out.print(" " + node.data);
}
else
{
status = true;
}
//remove element into queue
queue.dequeue();
}
}
}
public static void main(String[] args)
{
//Object of Binary Tree
BinaryTree tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
10
/ \
2 3
/ / \
4 9 5
/ \ \ \
7 3 6 20
/ \ /
2 8 -8
-----------------------
*/
//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(20);
tree.root.right.right.right.left = new TreeNode(-8);
tree.root.left.left.right.left = new TreeNode(2);
tree.root.left.left.right.right = new TreeNode(8);
tree.print_alternate_nodes();
}
}
Output
10 3 9 7 6 2 -8
//Include header file
#include <iostream>
using namespace std;
/*
C++ program
Print alternate nodes in level order 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 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)
{
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 alternate nodes in binary tree in level order
void print_alternate_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);
// Result indicator
bool status = true;
//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 (status == true)
{
status = false;
cout << " " << node->data;
}
else
{
status = true;
}
//remove element into queue
queue.dequeue();
}
}
}
};
int main()
{
//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(20);
tree.root->right->right->right->left = new TreeNode(-8);
tree.root->left->left->right->left = new TreeNode(2);
tree.root->left->left->right->right = new TreeNode(8);
tree.print_alternate_nodes();
return 0;
}
Output
10 3 9 7 6 2 -8
//Include namespace system
using System;
/*
C# program
Print alternate nodes in level order 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 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 alternate nodes in binary tree in level order
public void print_alternate_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);
// Result indicator
Boolean status = true;
//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 (status == true)
{
status = false;
Console.Write(" " + node.data);
}
else
{
status = true;
}
//remove element into queue
queue.dequeue();
}
}
}
public static void Main(String[] args)
{
//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(20);
tree.root.right.right.right.left = new TreeNode(-8);
tree.root.left.left.right.left = new TreeNode(2);
tree.root.left.left.right.right = new TreeNode(8);
tree.print_alternate_nodes();
}
}
Output
10 3 9 7 6 2 -8
<?php
/*
Php program
Print alternate nodes in level order of a binary 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 alternate nodes in binary tree in level order
public function print_alternate_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);
// Result indicator
$status = true;
//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 ($status == true)
{
$status = false;
echo " ". $node->data;
}
else
{
$status = true;
}
//remove element into queue
$queue->dequeue();
}
}
}
}
function main()
{
//Object of Binary Tree
$tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
10
/ \
2 3
/ / \
4 9 5
/ \ \ \
7 3 6 20
/ \ /
2 8 -8
-----------------------
*/
//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(20);
$tree->root->right->right->right->left = new TreeNode(-8);
$tree->root->left->left->right->left = new TreeNode(2);
$tree->root->left->left->right->right = new TreeNode(8);
$tree->print_alternate_nodes();
}
main();
Output
10 3 9 7 6 2 -8
/*
Node Js program
Print alternate nodes in level order 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 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 alternate nodes in binary tree in level order
print_alternate_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);
// Result indicator
var status = true;
//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 (status == true)
{
status = false;
process.stdout.write(" " + node.data);
}
else
{
status = true;
}
//remove element into queue
queue.dequeue();
}
}
}
}
function main()
{
//Object of Binary Tree
var tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
10
/ \
2 3
/ / \
4 9 5
/ \ \ \
7 3 6 20
/ \ /
2 8 -8
-----------------------
*/
//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(20);
tree.root.right.right.right.left = new TreeNode(-8);
tree.root.left.left.right.left = new TreeNode(2);
tree.root.left.left.right.right = new TreeNode(8);
tree.print_alternate_nodes();
}
main();
Output
10 3 9 7 6 2 -8
# Python 3 program
# Print alternate nodes in level order 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 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 alternate nodes in binary tree in level order
def print_alternate_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)
# Result indicator
status = True
# 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 (status == True) :
status = False
print(" ", node.data, end = "")
else :
status = True
# remove element into queue
queue.dequeue()
def main() :
# Object of Binary Tree
tree = BinaryTree()
#
# Construct Binary Tree
# -----------------------
# 10
# / \
# 2 3
# / / \
# 4 9 5
# / \ \ \
# 7 3 6 20
# / \ /
# 2 8 -8
# -----------------------
#
# 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(20)
tree.root.right.right.right.left = TreeNode(-8)
tree.root.left.left.right.left = TreeNode(2)
tree.root.left.left.right.right = TreeNode(8)
tree.print_alternate_nodes()
if __name__ == "__main__": main()
Output
10 3 9 7 6 2 -8
# Ruby program
# Print alternate nodes in level order 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 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 alternate nodes in binary tree in level order
def print_alternate_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)
# Result indicator
status = true
# 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 (status == true)
status = false
print(" ", node.data)
else
status = true
end
# remove element into queue
queue.dequeue()
end
end
end
end
def main()
# Object of Binary Tree
tree = BinaryTree.new()
#
# Construct Binary Tree
# -----------------------
# 10
# / \
# 2 3
# / / \
# 4 9 5
# / \ \ \
# 7 3 6 20
# / \ /
# 2 8 -8
# -----------------------
#
# 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(20)
tree.root.right.right.right.left = TreeNode.new(-8)
tree.root.left.left.right.left = TreeNode.new(2)
tree.root.left.left.right.right = TreeNode.new(8)
tree.print_alternate_nodes()
end
main()
Output
10 3 9 7 6 2 -8
/*
Scala program
Print alternate nodes in level order of a binary 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 alternate nodes in binary tree in level order
def print_alternate_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);
// Result indicator
var status: Boolean = true;
//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 (status == true)
{
status = false;
print(" " + node.data);
}
else
{
status = true;
}
//remove element into queue
queue.dequeue();
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
//Object of Binary Tree
var tree: BinaryTree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
10
/ \
2 3
/ / \
4 9 5
/ \ \ \
7 3 6 20
/ \ /
2 8 -8
-----------------------
*/
//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(20);
tree.root.right.right.right.left = new TreeNode(-8);
tree.root.left.left.right.left = new TreeNode(2);
tree.root.left.left.right.right = new TreeNode(8);
tree.print_alternate_nodes();
}
}
Output
10 3 9 7 6 2 -8
/*
Swift 4 program
Print alternate nodes in level order 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 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 alternate nodes in binary tree in level order
func print_alternate_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);
// Result indicator
var status: Bool = true;
//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 (status == true)
{
status = false;
print(" ", node!.data, terminator: "");
}
else
{
status = true;
}
//remove element into queue
queue.dequeue();
}
}
}
}
func main()
{
//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(20);
tree.root!.right!.right!.right!.left = TreeNode(-8);
tree.root!.left!.left!.right!.left = TreeNode(2);
tree.root!.left!.left!.right!.right = TreeNode(8);
tree.print_alternate_nodes();
}
main();
Output
10 3 9 7 6 2 -8
Algorithm
- Define the
TreeNode
class to represent a node in the binary tree. Each node will have a data value and pointers to its left and right children. - Define the
QueueNode
class to represent a node in the custom queue. Each node will contain a pointer to a binary tree node, its level, and a link to the next node in the queue. - Define the
MyQueue
class to implement the custom queue. It will have methods to enqueue and dequeue nodes, as well as a method to check if the queue is empty. - Define the
BinaryTree
class to represent the binary tree. It will have a methodprint_alternate_nodes()
to print all the alternate nodes in level order. - Perform a level order traversal of the binary tree using a queue. For each level, maintain a flag to decide whether to print the alternate nodes or not.
Time Complexity
- The time complexity of performing a level order traversal of the binary tree to print alternate nodes is O(N), where N is the number of nodes in the tree.
- Therefore, the overall time complexity of the algorithm is O(N), where N is the number of nodes in the binary tree.
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