Level order traversal with direction change of given intervals
Here given code implementation process.
/*
C Program
Level order traversal with direction change of given intervals
*/
#include <stdio.h>
#include <stdlib.h>
//Binary Tree node
struct Node
{
int data;
struct Node *left, *right;
};
// Define Queue Node
struct MyQueue
{
int level;
struct Node *element;
struct MyQueue *next;
};
// Define Stack Node
struct MyStack
{
int element;
struct MyStack *next;
};
//This is creating a binary tree node and return this
struct Node *get_node(int data)
{
// Create dynamic node
struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
if (new_node != NULL)
{
//Set data and pointer values
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
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;
}
}
//Add node at top of stack
void push(struct MyStack **top, int data)
{
//Make a new node
struct MyStack *new_node = (struct MyStack *) malloc(sizeof(struct MyStack));
if (new_node != NULL)
{
//Set node values
new_node->element = data;
new_node->next = *top;*top = new_node;
}
else
{
printf("Memory Overflow\n");
}
}
// Remove top element
void pop(struct MyStack **top)
{
if ( *top != NULL)
{
struct MyStack *temp = *top;*top = temp->next;
free(temp);
temp = NULL;
}
}
//Print stack elements
void print_stack(struct MyStack **top)
{
struct MyStack *temp = *top;
while (temp != NULL)
{
printf(" %d", temp->element);
temp = temp->next;
pop(top);
}
}
// Print binary tree level using change direction of given intervals
void print_interval(struct Node *root, int interval)
{
if (root == NULL)
{
printf("\n Empty Tree \n");
}
else if (interval <= 0)
{
printf("\n Invalid Interval");
}
else
{
printf("\n Direction Interval : %d",interval);
// Declare queue pointers
struct MyQueue *front = NULL, *tail = NULL;
struct MyQueue *temp = NULL;
// Declare stack pointer
struct MyStack *top = NULL;
//make a tree pointer
struct Node *node = 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;
// Start to first node
temp = front;
// Useful auxiliary variables
int level = 0;
int counter = 0;
// Get level elements into a queue
while (temp != NULL)
{
//Tree node
node = temp->element;
//Get node level
level = temp->level + 1;
if (node->left != NULL)
{
//Add new left child node
tail->next = enqueue(node->left);
tail->next->level = level;
tail = tail->next;
}
if (node->right != NULL)
{
//Add new right child node
tail->next = enqueue(node->right);
tail->next->level = level;
tail = tail->next;
}
//Visit to next node queue
temp = temp->next;
}
// Change the direction in the given interval and print the tree nodes
while (front != NULL)
{
level = (interval - 1) + front->level;
//Useful to find new levels in tree
counter = front->level - 1;
//print n level
while (front != NULL && front->level <= level)
{
if (front->level != counter)
{
//switch level
printf("\n");
counter = front->level;
}
printf(" %d", front->element->data);
//remove a queue node
dequeue( &front);
}
if (front != NULL)
{
level = (interval - 1) + front->level;
counter = front->level;
}
// Add interval into stack
while (front != NULL && front->level <= level)
{
if (front->level != counter)
{
//Switch level
printf("\n");
counter = front->level;
print_stack(&top);
}
push( &top, front->element->data);
//remove a queue node
dequeue( &front);
}
if (top != NULL)
{
printf("\n");
print_stack(&top);
}
}
printf("\n");
}
}
int main()
{
struct Node *root = NULL;
/*
8
/ \
/ \
/ \
5 10
/ \ / \
1 3 11 2
/ \ \ \
6 9 4 12
/ \ \
15 13 17
/ \ /
20 31 32
-----------------
Construct binary tree
*/
root = get_node(8);
root->left = get_node(5);
root->left->right = get_node(3);
root->left->right->right = get_node(9);
root->left->right->right->left = get_node(15);
root->left->right->right->left->left = get_node(20);
root->left->right->right->left->right = get_node(31);
root->left->left = get_node(1);
root->left->left->left = get_node(6);
root->right = get_node(10);
root->right->left = get_node(11);
root->right->left->right = get_node(4);
root->right->left->right->right = get_node(13);
root->right->left->right->right->left = get_node(32);
root->right->right = get_node(2);
root->right->right->right = get_node(12);
root->right->right->right->right = get_node(17);
//Test Cases
print_interval(root, 2);
print_interval(root, 1);
print_interval(root, 3);
return 0;
}Output
Direction Interval : 2
8
5 10
2 11 3 1
12 4 9 6
15 13 17
20 31 32
Direction Interval : 1
8
10 5
1 3 11 2
12 4 9 6
15 13 17
32 31 20
Direction Interval : 3
8
5 10
1 3 11 2
12 4 9 6
17 13 15
32 31 20/*
Java Program
Level order traversal with direction change of given intervals
*/
// 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;
}
}
//Stack Node
class StackNode
{
public int data;
public StackNode next;
public StackNode(int data)
{
this.data = data;
this.next = 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;
}
}
}
//Define custom stack and its operation
class MyStack
{
public StackNode top;
public MyStack()
{
this.top = null;
}
//Add a new element in stack
public void push(int data)
{
//Make a new stack node
StackNode new_node = new StackNode(data);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
}
else
{
System.out.print("Memory overflow\n");
}
}
//remove a top element in stack
public void pop()
{
if (this.top != null)
{
this.top = this.top.next;
}
}
// Check that whether stack is empty or not
public boolean is_empty()
{
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
// Used to get top element of stack
public int peek()
{
if (this.top != null)
{
return this.top.data;
}
else
{
return 0;
}
}
}
//Define Binary Tree
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
//Set root of tree
this.root = null;
}
public void print_stack(MyStack stack)
{
while (stack.is_empty() == false)
{
System.out.print(" " + stack.peek());
stack.pop();
}
}
// Print binary tree level using change direction of given intervals
public void print_interval(int interval)
{
if (this.root == null)
{
System.out.print("\n Empty Binary Tree \n");
}
else
{
System.out.print("\n Direction Interval : " + interval);
//Get top node in tree
TreeNode node = this.root;
//Define a Queue
MyQueue queue = new MyQueue();
//Define a stack
MyStack stack = new MyStack();
//Add first node at the level of one
queue.enqueue(node, 1);
QueueNode temp = queue.front;
int level = 0;
int counter = 0;
//Add tree level
while (temp != null)
{
node = temp.element;
level = temp.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);
}
temp = temp.next;
}
// Change the direction in the given interval and print the tree nodes
while (queue.is_empty() == false)
{
// Get interval
level = (interval - 1) + queue.front.level;
//Useful to find new levels in tree
counter = queue.front.level - 1;
//print n level
while (queue.is_empty() == false && queue.front.level <= level)
{
if (queue.front.level != counter)
{
//switch level
System.out.print("\n");
counter = queue.front.level;
}
System.out.print(" " + queue.front.element.data);
//remove a queue node
queue.dequeue();
}
if (queue.is_empty() == false)
{
level = (interval - 1) + queue.front.level;
counter = queue.front.level;
}
// Add interval into stack
while (queue.is_empty() == false && queue.front.level <= level)
{
if (queue.front.level != counter)
{
//Switch level
System.out.print("\n");
counter = queue.front.level;
print_stack(stack);
}
stack.push(queue.front.element.data);
//remove a queue node
queue.dequeue();
}
if (stack.is_empty() == false)
{
System.out.print("\n");
print_stack(stack);
}
}
}
}
public static void main(String[] args)
{
//Create tree object
BinaryTree tree = new BinaryTree();
/*
8
/ \
/ \
/ \
5 10
/ \ / \
1 3 11 2
/ \ \ \
6 9 4 12
/ \ \
15 13 17
/ \ /
20 31 32
-----------------
Construct binary tree
*/
tree.root = new TreeNode(8);
tree.root.left = new TreeNode(5);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.right = new TreeNode(9);
tree.root.left.right.right.left = new TreeNode(15);
tree.root.left.right.right.left.left = new TreeNode(20);
tree.root.left.right.right.left.right = new TreeNode(31);
tree.root.left.left = new TreeNode(1);
tree.root.left.left.left = new TreeNode(6);
tree.root.right = new TreeNode(10);
tree.root.right.left = new TreeNode(11);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.left.right.right = new TreeNode(13);
tree.root.right.left.right.right.left = new TreeNode(32);
tree.root.right.right = new TreeNode(2);
tree.root.right.right.right = new TreeNode(12);
tree.root.right.right.right.right = new TreeNode(17);
//Test Cases
tree.print_interval(2);
tree.print_interval(1);
tree.print_interval(3);
}
}Output
Direction Interval : 2
8
5 10
2 11 3 1
12 4 9 6
15 13 17
20 31 32
Direction Interval : 1
8
10 5
1 3 11 2
12 4 9 6
15 13 17
32 31 20
Direction Interval : 3
8
5 10
1 3 11 2
12 4 9 6
17 13 15
32 31 20// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Level order traversal with direction change of given intervals
*/
// 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;
}
};
// Stack Node
class StackNode
{
public: int data;
StackNode *next;
StackNode(int data)
{
this->data = data;
this->next = 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 *temp = this->front;
if (this->tail == this->front)
{
this->tail = NULL;
this->front = NULL;
}
else
{
this->front = this->front->next;
}
delete temp;
}
}
bool is_empty()
{
if (this->front == NULL)
{
return true;
}
else
{
return false;
}
}
};
// Define custom stack and its operation
class MyStack
{
public: StackNode *top;
MyStack()
{
this->top = NULL;
}
// Add a new element in stack
void push(int data)
{
// Make a new stack node
StackNode *new_node = new StackNode(data);
if (new_node != NULL)
{
new_node->next = this->top;
this->top = new_node;
}
else
{
cout << "Memory overflow\n";
}
}
// remove a top element in stack
void pop()
{
if (this->top != NULL)
{
StackNode *temp = this->top;
this->top = this->top->next;
delete temp;
}
}
// Check that whether stack is empty or not
bool is_empty()
{
if (this->top != NULL)
{
return false;
}
else
{
return true;
}
}
// Used to get top element of stack
int peek()
{
if (this->top != NULL)
{
return this->top->data;
}
else
{
return 0;
}
}
};
// Define Binary Tree
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
// Set root of tree
this->root = NULL;
}
void print_stack(MyStack &stack)
{
while (stack.is_empty() == false)
{
cout << " " << stack.peek();
stack.pop();
}
}
// Print binary tree level using change direction of given intervals
void print_interval(int interval)
{
if (this->root == NULL)
{
cout << "\n Empty Binary Tree \n";
}
else
{
cout << "\n Direction Interval : " << interval;
// Get top node in tree
TreeNode *node = this->root;
// Define a Queue
MyQueue queue = MyQueue();
// Define a stack
MyStack stack = MyStack();
// Add first node at the level of one
queue.enqueue(node, 1);
QueueNode *temp = queue.front;
int level = 0;
int counter = 0;
// Add tree level
while (temp != NULL)
{
node = temp->element;
level = temp->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);
}
temp = temp->next;
}
// Change the direction in the given interval and print the tree nodes
while (queue.is_empty() == false)
{
// Get interval
level = (interval - 1) + queue.front->level;
// Useful to find new levels in tree
counter = queue.front->level - 1;
// print n level
while (queue.is_empty() == false && queue.front->level <= level)
{
if (queue.front->level != counter)
{
// switch level
cout << "\n";
counter = queue.front->level;
}
cout << " " << queue.front->element->data;
// remove a queue node
queue.dequeue();
}
if (queue.is_empty() == false)
{
level = (interval - 1) + queue.front->level;
counter = queue.front->level;
}
// Add interval into stack
while (queue.is_empty() == false && queue.front->level <= level)
{
if (queue.front->level != counter)
{
// Switch level
cout << "\n";
counter = queue.front->level;
this->print_stack(stack);
}
stack.push(queue.front->element->data);
// remove a queue node
queue.dequeue();
}
if (stack.is_empty() == false)
{
cout << "\n";
this->print_stack(stack);
}
}
}
}
};
int main()
{
// Create tree object
BinaryTree tree = BinaryTree();
/*
8
/ \
/ \
/ \
5 10
/ \ / \
1 3 11 2
/ \ \ \
6 9 4 12
/ \ \
15 13 17
/ \ /
20 31 32
-----------------
Construct binary tree
*/
tree.root = new TreeNode(8);
tree.root->left = new TreeNode(5);
tree.root->left->right = new TreeNode(3);
tree.root->left->right->right = new TreeNode(9);
tree.root->left->right->right->left = new TreeNode(15);
tree.root->left->right->right->left->left = new TreeNode(20);
tree.root->left->right->right->left->right = new TreeNode(31);
tree.root->left->left = new TreeNode(1);
tree.root->left->left->left = new TreeNode(6);
tree.root->right = new TreeNode(10);
tree.root->right->left = new TreeNode(11);
tree.root->right->left->right = new TreeNode(4);
tree.root->right->left->right->right = new TreeNode(13);
tree.root->right->left->right->right->left = new TreeNode(32);
tree.root->right->right = new TreeNode(2);
tree.root->right->right->right = new TreeNode(12);
tree.root->right->right->right->right = new TreeNode(17);
// Test Cases
tree.print_interval(2);
tree.print_interval(1);
tree.print_interval(3);
return 0;
}Output
Direction Interval : 2
8
5 10
2 11 3 1
12 4 9 6
15 13 17
20 31 32
Direction Interval : 1
8
10 5
1 3 11 2
12 4 9 6
15 13 17
32 31 20
Direction Interval : 3
8
5 10
1 3 11 2
12 4 9 6
17 13 15
32 31 20// Include namespace system
using System;
/*
C# Program
Level order traversal with direction change of given intervals
*/
// Binary Tree node
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Stack Node
public class StackNode
{
public int data;
public StackNode next;
public StackNode(int data)
{
this.data = data;
this.next = null;
}
}
// Queue Node
public 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
public 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;
}
}
}
// Define custom stack and its operation
public class MyStack
{
public StackNode top;
public MyStack()
{
this.top = null;
}
// Add a new element in stack
public void push(int data)
{
// Make a new stack node
StackNode new_node = new StackNode(data);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
}
else
{
Console.Write("Memory overflow\n");
}
}
// remove a top element in stack
public void pop()
{
if (this.top != null)
{
this.top = this.top.next;
}
}
// Check that whether stack is empty or not
public Boolean is_empty()
{
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
// Used to get top element of stack
public int peek()
{
if (this.top != null)
{
return this.top.data;
}
else
{
return 0;
}
}
}
// Define Binary Tree
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set root of tree
this.root = null;
}
public void print_stack(MyStack stack)
{
while (stack.is_empty() == false)
{
Console.Write(" " + stack.peek());
stack.pop();
}
}
// Print binary tree level using change direction of given intervals
public void print_interval(int interval)
{
if (this.root == null)
{
Console.Write("\n Empty Binary Tree \n");
}
else
{
Console.Write("\n Direction Interval : " + interval);
// Get top node in tree
TreeNode node = this.root;
// Define a Queue
MyQueue queue = new MyQueue();
// Define a stack
MyStack stack = new MyStack();
// Add first node at the level of one
queue.enqueue(node, 1);
QueueNode temp = queue.front;
int level = 0;
int counter = 0;
// Add tree level
while (temp != null)
{
node = temp.element;
level = temp.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);
}
temp = temp.next;
}
// Change the direction in the given interval and print the tree nodes
while (queue.is_empty() == false)
{
// Get interval
level = (interval - 1) + queue.front.level;
// Useful to find new levels in tree
counter = queue.front.level - 1;
// print n level
while (queue.is_empty() == false && queue.front.level <= level)
{
if (queue.front.level != counter)
{
// switch level
Console.Write("\n");
counter = queue.front.level;
}
Console.Write(" " + queue.front.element.data);
// remove a queue node
queue.dequeue();
}
if (queue.is_empty() == false)
{
level = (interval - 1) + queue.front.level;
counter = queue.front.level;
}
// Add interval into stack
while (queue.is_empty() == false && queue.front.level <= level)
{
if (queue.front.level != counter)
{
// Switch level
Console.Write("\n");
counter = queue.front.level;
print_stack(stack);
}
stack.push(queue.front.element.data);
// remove a queue node
queue.dequeue();
}
if (stack.is_empty() == false)
{
Console.Write("\n");
print_stack(stack);
}
}
}
}
public static void Main(String[] args)
{
// Create tree object
BinaryTree tree = new BinaryTree();
/*
8
/ \
/ \
/ \
5 10
/ \ / \
1 3 11 2
/ \ \ \
6 9 4 12
/ \ \
15 13 17
/ \ /
20 31 32
-----------------
Construct binary tree
*/
tree.root = new TreeNode(8);
tree.root.left = new TreeNode(5);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.right = new TreeNode(9);
tree.root.left.right.right.left = new TreeNode(15);
tree.root.left.right.right.left.left = new TreeNode(20);
tree.root.left.right.right.left.right = new TreeNode(31);
tree.root.left.left = new TreeNode(1);
tree.root.left.left.left = new TreeNode(6);
tree.root.right = new TreeNode(10);
tree.root.right.left = new TreeNode(11);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.left.right.right = new TreeNode(13);
tree.root.right.left.right.right.left = new TreeNode(32);
tree.root.right.right = new TreeNode(2);
tree.root.right.right.right = new TreeNode(12);
tree.root.right.right.right.right = new TreeNode(17);
// Test Cases
tree.print_interval(2);
tree.print_interval(1);
tree.print_interval(3);
}
}Output
Direction Interval : 2
8
5 10
2 11 3 1
12 4 9 6
15 13 17
20 31 32
Direction Interval : 1
8
10 5
1 3 11 2
12 4 9 6
15 13 17
32 31 20
Direction Interval : 3
8
5 10
1 3 11 2
12 4 9 6
17 13 15
32 31 20<?php
/*
Php Program
Level order traversal with direction change of given intervals
*/
// 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;
}
}
// Stack Node
class StackNode
{
public $data;
public $next;
function __construct($data)
{
$this->data = $data;
$this->next = 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;
}
}
}
// Define custom stack and its operation
class MyStack
{
public $top;
function __construct()
{
$this->top = null;
}
// Add a new element in stack
public function push($data)
{
// Make a new stack node
$new_node = new StackNode($data);
if ($new_node != null)
{
$new_node->next = $this->top;
$this->top = $new_node;
}
else
{
echo "Memory overflow\n";
}
}
// remove a top element in stack
public function pop()
{
if ($this->top != null)
{
$this->top = $this->top->next;
}
}
// Check that whether stack is empty or not
public function is_empty()
{
if ($this->top != null)
{
return false;
}
else
{
return true;
}
}
// Used to get top element of stack
public function peek()
{
if ($this->top != null)
{
return $this->top->data;
}
else
{
return 0;
}
}
}
// Define Binary Tree
class BinaryTree
{
public $root;
function __construct()
{
// Set root of tree
$this->root = null;
}
public function print_stack($stack)
{
while ($stack->is_empty() == false)
{
echo " ". $stack->peek();
$stack->pop();
}
}
// Print binary tree level using change direction of given intervals
public function print_interval($interval)
{
if ($this->root == null)
{
echo "\n Empty Binary Tree \n";
}
else
{
echo "\n Direction Interval : ". $interval;
// Get top node in tree
$node = $this->root;
// Define a Queue
$queue = new MyQueue();
// Define a stack
$stack = new MyStack();
// Add first node at the level of one
$queue->enqueue($node, 1);
$temp = $queue->front;
$level = 0;
$counter = 0;
// Add tree level
while ($temp != null)
{
$node = $temp->element;
$level = $temp->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);
}
$temp = $temp->next;
}
// Change the direction in the given interval and print the tree nodes
while ($queue->is_empty() == false)
{
// Get interval
$level = ($interval - 1) + $queue->front->level;
// Useful to find new levels in tree
$counter = $queue->front->level - 1;
// print n level
while ($queue->is_empty() == false && $queue->front->level <= $level)
{
if ($queue->front->level != $counter)
{
// switch level
echo "\n";
$counter = $queue->front->level;
}
echo " ". $queue->front->element->data;
// remove a queue node
$queue->dequeue();
}
if ($queue->is_empty() == false)
{
$level = ($interval - 1) + $queue->front->level;
$counter = $queue->front->level;
}
// Add interval into stack
while ($queue->is_empty() == false && $queue->front->level <= $level)
{
if ($queue->front->level != $counter)
{
// Switch level
echo "\n";
$counter = $queue->front->level;
$this->print_stack($stack);
}
$stack->push($queue->front->element->data);
// remove a queue node
$queue->dequeue();
}
if ($stack->is_empty() == false)
{
echo "\n";
$this->print_stack($stack);
}
}
}
}
}
function main()
{
// Create tree object
$tree = new BinaryTree();
/*
8
/ \
/ \
/ \
5 10
/ \ / \
1 3 11 2
/ \ \ \
6 9 4 12
/ \ \
15 13 17
/ \ /
20 31 32
-----------------
Construct binary tree
*/
$tree->root = new TreeNode(8);
$tree->root->left = new TreeNode(5);
$tree->root->left->right = new TreeNode(3);
$tree->root->left->right->right = new TreeNode(9);
$tree->root->left->right->right->left = new TreeNode(15);
$tree->root->left->right->right->left->left = new TreeNode(20);
$tree->root->left->right->right->left->right = new TreeNode(31);
$tree->root->left->left = new TreeNode(1);
$tree->root->left->left->left = new TreeNode(6);
$tree->root->right = new TreeNode(10);
$tree->root->right->left = new TreeNode(11);
$tree->root->right->left->right = new TreeNode(4);
$tree->root->right->left->right->right = new TreeNode(13);
$tree->root->right->left->right->right->left = new TreeNode(32);
$tree->root->right->right = new TreeNode(2);
$tree->root->right->right->right = new TreeNode(12);
$tree->root->right->right->right->right = new TreeNode(17);
// Test Cases
$tree->print_interval(2);
$tree->print_interval(1);
$tree->print_interval(3);
}
main();Output
Direction Interval : 2
8
5 10
2 11 3 1
12 4 9 6
15 13 17
20 31 32
Direction Interval : 1
8
10 5
1 3 11 2
12 4 9 6
15 13 17
32 31 20
Direction Interval : 3
8
5 10
1 3 11 2
12 4 9 6
17 13 15
32 31 20/*
Node Js Program
Level order traversal with direction change of given intervals
*/
// Binary Tree node
class TreeNode
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Stack Node
class StackNode
{
constructor(data)
{
this.data = data;
this.next = 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;
}
}
}
// Define custom stack and its operation
class MyStack
{
constructor()
{
this.top = null;
}
// Add a new element in stack
push(data)
{
// Make a new stack node
var new_node = new StackNode(data);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
}
else
{
process.stdout.write("Memory overflow\n");
}
}
// remove a top element in stack
pop()
{
if (this.top != null)
{
this.top = this.top.next;
}
}
// Check that whether stack is empty or not
is_empty()
{
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
// Used to get top element of stack
peek()
{
if (this.top != null)
{
return this.top.data;
}
else
{
return 0;
}
}
}
// Define Binary Tree
class BinaryTree
{
constructor()
{
// Set root of tree
this.root = null;
}
print_stack(stack)
{
while (stack.is_empty() == false)
{
process.stdout.write(" " + stack.peek());
stack.pop();
}
}
// Print binary tree level using change direction of given intervals
print_interval(interval)
{
if (this.root == null)
{
process.stdout.write("\n Empty Binary Tree \n");
}
else
{
process.stdout.write("\n Direction Interval : " + interval);
// Get top node in tree
var node = this.root;
// Define a Queue
var queue = new MyQueue();
// Define a stack
var stack = new MyStack();
// Add first node at the level of one
queue.enqueue(node, 1);
var temp = queue.front;
var level = 0;
var counter = 0;
// Add tree level
while (temp != null)
{
node = temp.element;
level = temp.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);
}
temp = temp.next;
}
// Change the direction in the given interval and print the tree nodes
while (queue.is_empty() == false)
{
// Get interval
level = (interval - 1) + queue.front.level;
// Useful to find new levels in tree
counter = queue.front.level - 1;
// print n level
while (queue.is_empty() == false && queue.front.level <= level)
{
if (queue.front.level != counter)
{
// switch level
process.stdout.write("\n");
counter = queue.front.level;
}
process.stdout.write(" " + queue.front.element.data);
// remove a queue node
queue.dequeue();
}
if (queue.is_empty() == false)
{
level = (interval - 1) + queue.front.level;
counter = queue.front.level;
}
// Add interval into stack
while (queue.is_empty() == false && queue.front.level <= level)
{
if (queue.front.level != counter)
{
// Switch level
process.stdout.write("\n");
counter = queue.front.level;
this.print_stack(stack);
}
stack.push(queue.front.element.data);
// remove a queue node
queue.dequeue();
}
if (stack.is_empty() == false)
{
process.stdout.write("\n");
this.print_stack(stack);
}
}
}
}
}
function main()
{
// Create tree object
var tree = new BinaryTree();
/*
8
/ \
/ \
/ \
5 10
/ \ / \
1 3 11 2
/ \ \ \
6 9 4 12
/ \ \
15 13 17
/ \ /
20 31 32
-----------------
Construct binary tree
*/
tree.root = new TreeNode(8);
tree.root.left = new TreeNode(5);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.right = new TreeNode(9);
tree.root.left.right.right.left = new TreeNode(15);
tree.root.left.right.right.left.left = new TreeNode(20);
tree.root.left.right.right.left.right = new TreeNode(31);
tree.root.left.left = new TreeNode(1);
tree.root.left.left.left = new TreeNode(6);
tree.root.right = new TreeNode(10);
tree.root.right.left = new TreeNode(11);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.left.right.right = new TreeNode(13);
tree.root.right.left.right.right.left = new TreeNode(32);
tree.root.right.right = new TreeNode(2);
tree.root.right.right.right = new TreeNode(12);
tree.root.right.right.right.right = new TreeNode(17);
// Test Cases
tree.print_interval(2);
tree.print_interval(1);
tree.print_interval(3);
}
main();Output
Direction Interval : 2
8
5 10
2 11 3 1
12 4 9 6
15 13 17
20 31 32
Direction Interval : 1
8
10 5
1 3 11 2
12 4 9 6
15 13 17
32 31 20
Direction Interval : 3
8
5 10
1 3 11 2
12 4 9 6
17 13 15
32 31 20# Python 3 Program
# Level order traversal with direction change of given intervals
# Binary Tree node
class TreeNode :
def __init__(self, data) :
# Set node value
self.data = data
self.left = None
self.right = None
# Stack Node
class StackNode :
def __init__(self, data) :
self.data = data
self.next = 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
# Define custom stack and its operation
class MyStack :
def __init__(self) :
self.top = None
# Add a new element in stack
def push(self, data) :
# Make a new stack node
new_node = StackNode(data)
if (new_node != None) :
new_node.next = self.top
self.top = new_node
else :
print("Memory overflow\n", end = "")
# remove a top element in stack
def pop(self) :
if (self.top != None) :
self.top = self.top.next
# Check that whether stack is empty or not
def is_empty(self) :
if (self.top != None) :
return False
else :
return True
# Used to get top element of stack
def peek(self) :
if (self.top != None) :
return self.top.data
else :
return 0
# Define Binary Tree
class BinaryTree :
def __init__(self) :
# Set root of tree
self.root = None
def print_stack(self, stack) :
while (stack.is_empty() == False) :
print(" ", stack.peek(), end = "")
stack.pop()
# Print binary tree level using change direction of given intervals
def print_interval(self, interval) :
if (self.root == None) :
print("\n Empty Binary Tree \n", end = "")
else :
print("\n Direction Interval : ", interval, end = "")
# Get top node in tree
node = self.root
# Define a Queue
queue = MyQueue()
# Define a stack
stack = MyStack()
# Add first node at the level of one
queue.enqueue(node, 1)
temp = queue.front
level = 0
counter = 0
# Add tree level
while (temp != None) :
node = temp.element
level = temp.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)
temp = temp.next
# Change the direction in the given interval and print the tree nodes
while (queue.is_empty() == False) :
# Get interval
level = (interval - 1) + queue.front.level
# Useful to find new levels in tree
counter = queue.front.level - 1
# print n level
while (queue.is_empty() == False and queue.front.level <= level) :
if (queue.front.level != counter) :
# switch level
print("\n", end = "")
counter = queue.front.level
print(" ", queue.front.element.data, end = "")
# remove a queue node
queue.dequeue()
if (queue.is_empty() == False) :
level = (interval - 1) + queue.front.level
counter = queue.front.level
# Add interval into stack
while (queue.is_empty() == False and queue.front.level <= level) :
if (queue.front.level != counter) :
# Switch level
print("\n", end = "")
counter = queue.front.level
self.print_stack(stack)
stack.push(queue.front.element.data)
# remove a queue node
queue.dequeue()
if (stack.is_empty() == False) :
print("\n", end = "")
self.print_stack(stack)
def main() :
# Create tree object
tree = BinaryTree()
#
# 8
# / \
# / \
# / \
# 5 10
# / \ / \
# 1 3 11 2
# / \ \ \
# 6 9 4 12
# / \ \
# 15 13 17
# / \ /
# 20 31 32
# -----------------
# Construct binary tree
#
tree.root = TreeNode(8)
tree.root.left = TreeNode(5)
tree.root.left.right = TreeNode(3)
tree.root.left.right.right = TreeNode(9)
tree.root.left.right.right.left = TreeNode(15)
tree.root.left.right.right.left.left = TreeNode(20)
tree.root.left.right.right.left.right = TreeNode(31)
tree.root.left.left = TreeNode(1)
tree.root.left.left.left = TreeNode(6)
tree.root.right = TreeNode(10)
tree.root.right.left = TreeNode(11)
tree.root.right.left.right = TreeNode(4)
tree.root.right.left.right.right = TreeNode(13)
tree.root.right.left.right.right.left = TreeNode(32)
tree.root.right.right = TreeNode(2)
tree.root.right.right.right = TreeNode(12)
tree.root.right.right.right.right = TreeNode(17)
# Test Cases
tree.print_interval(2)
tree.print_interval(1)
tree.print_interval(3)
if __name__ == "__main__": main()Output
Direction Interval : 2
8
5 10
2 11 3 1
12 4 9 6
15 13 17
20 31 32
Direction Interval : 1
8
10 5
1 3 11 2
12 4 9 6
15 13 17
32 31 20
Direction Interval : 3
8
5 10
1 3 11 2
12 4 9 6
17 13 15
32 31 20# Ruby Program
# Level order traversal with direction change of given intervals
# 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
# Stack Node
class StackNode
# Define the accessor and reader of class StackNode
attr_reader :data, :next
attr_accessor :data, :next
def initialize(data)
self.data = data
self.next = 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
# Define custom stack and its operation
class MyStack
# Define the accessor and reader of class MyStack
attr_reader :top
attr_accessor :top
def initialize()
self.top = nil
end
# Add a new element in stack
def push(data)
# Make a new stack node
new_node = StackNode.new(data)
if (new_node != nil)
new_node.next = self.top
self.top = new_node
else
print("Memory overflow\n")
end
end
# remove a top element in stack
def pop()
if (self.top != nil)
self.top = self.top.next
end
end
# Check that whether stack is empty or not
def is_empty()
if (self.top != nil)
return false
else
return true
end
end
# Used to get top element of stack
def peek()
if (self.top != nil)
return self.top.data
else
return 0
end
end
end
# Define Binary Tree
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root
attr_accessor :root
def initialize()
# Set root of tree
self.root = nil
end
def print_stack(stack)
while (stack.is_empty() == false)
print(" ", stack.peek())
stack.pop()
end
end
# Print binary tree level using change direction of given intervals
def print_interval(interval)
if (self.root == nil)
print("\n Empty Binary Tree \n")
else
print("\n Direction Interval : ", interval)
# Get top node in tree
node = self.root
# Define a Queue
queue = MyQueue.new()
# Define a stack
stack = MyStack.new()
# Add first node at the level of one
queue.enqueue(node, 1)
temp = queue.front
level = 0
counter = 0
# Add tree level
while (temp != nil)
node = temp.element
level = temp.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
temp = temp.next
end
# Change the direction in the given interval and print the tree nodes
while (queue.is_empty() == false)
# Get interval
level = (interval - 1) + queue.front.level
# Useful to find new levels in tree
counter = queue.front.level - 1
# print n level
while (queue.is_empty() == false && queue.front.level <= level)
if (queue.front.level != counter)
# switch level
print("\n")
counter = queue.front.level
end
print(" ", queue.front.element.data)
# remove a queue node
queue.dequeue()
end
if (queue.is_empty() == false)
level = (interval - 1) + queue.front.level
counter = queue.front.level
end
# Add interval into stack
while (queue.is_empty() == false && queue.front.level <= level)
if (queue.front.level != counter)
# Switch level
print("\n")
counter = queue.front.level
self.print_stack(stack)
end
stack.push(queue.front.element.data)
# remove a queue node
queue.dequeue()
end
if (stack.is_empty() == false)
print("\n")
self.print_stack(stack)
end
end
end
end
end
def main()
# Create tree object
tree = BinaryTree.new()
#
# 8
# / \
# / \
# / \
# 5 10
# / \ / \
# 1 3 11 2
# / \ \ \
# 6 9 4 12
# / \ \
# 15 13 17
# / \ /
# 20 31 32
# -----------------
# Construct binary tree
#
tree.root = TreeNode.new(8)
tree.root.left = TreeNode.new(5)
tree.root.left.right = TreeNode.new(3)
tree.root.left.right.right = TreeNode.new(9)
tree.root.left.right.right.left = TreeNode.new(15)
tree.root.left.right.right.left.left = TreeNode.new(20)
tree.root.left.right.right.left.right = TreeNode.new(31)
tree.root.left.left = TreeNode.new(1)
tree.root.left.left.left = TreeNode.new(6)
tree.root.right = TreeNode.new(10)
tree.root.right.left = TreeNode.new(11)
tree.root.right.left.right = TreeNode.new(4)
tree.root.right.left.right.right = TreeNode.new(13)
tree.root.right.left.right.right.left = TreeNode.new(32)
tree.root.right.right = TreeNode.new(2)
tree.root.right.right.right = TreeNode.new(12)
tree.root.right.right.right.right = TreeNode.new(17)
# Test Cases
tree.print_interval(2)
tree.print_interval(1)
tree.print_interval(3)
end
main()Output
Direction Interval : 2
8
5 10
2 11 3 1
12 4 9 6
15 13 17
20 31 32
Direction Interval : 1
8
10 5
1 3 11 2
12 4 9 6
15 13 17
32 31 20
Direction Interval : 3
8
5 10
1 3 11 2
12 4 9 6
17 13 15
32 31 20/*
Scala Program
Level order traversal with direction change of given intervals
*/
// Binary Tree node
class TreeNode(var data: Int , var left: TreeNode , var right: TreeNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
// Stack Node
class StackNode(var data: Int , var next: StackNode)
{
def this(data: Int)
{
this(data, 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;
}
}
}
// Define custom stack and its operation
class MyStack(var top: StackNode)
{
def this()
{
this(null);
}
// Add a new element in stack
def push(data: Int): Unit = {
// Make a new stack node
var new_node: StackNode = new StackNode(data);
if (new_node != null)
{
new_node.next = this.top;
this.top = new_node;
}
else
{
print("Memory overflow\n");
}
}
// remove a top element in stack
def pop(): Unit = {
if (this.top != null)
{
this.top = this.top.next;
}
}
// Check that whether stack is empty or not
def is_empty(): Boolean = {
if (this.top != null)
{
return false;
}
else
{
return true;
}
}
// Used to get top element of stack
def peek(): Int = {
if (this.top != null)
{
return this.top.data;
}
else
{
return 0;
}
}
}
// Define Binary Tree
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
def print_stack(stack: MyStack): Unit = {
while (stack.is_empty() == false)
{
print(" " + stack.peek());
stack.pop();
}
}
// Print binary tree level using change direction of given intervals
def print_interval(interval: Int): Unit = {
if (this.root == null)
{
print("\n Empty Binary Tree \n");
}
else
{
print("\n Direction Interval : " + interval);
// Get top node in tree
var node: TreeNode = this.root;
// Define a Queue
var queue: MyQueue = new MyQueue();
// Define a stack
var stack: MyStack = new MyStack();
// Add first node at the level of one
queue.enqueue(node, 1);
var temp: QueueNode = queue.front;
var level: Int = 0;
var counter: Int = 0;
// Add tree level
while (temp != null)
{
node = temp.element;
level = temp.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);
}
temp = temp.next;
}
// Change the direction in the given interval and print the tree nodes
while (queue.is_empty() == false)
{
// Get interval
level = (interval - 1) + queue.front.level;
// Useful to find new levels in tree
counter = queue.front.level - 1;
// print n level
while (queue.is_empty() == false && queue.front.level <= level)
{
if (queue.front.level != counter)
{
// switch level
print("\n");
counter = queue.front.level;
}
print(" " + queue.front.element.data);
// remove a queue node
queue.dequeue();
}
if (queue.is_empty() == false)
{
level = (interval - 1) + queue.front.level;
counter = queue.front.level;
}
// Add interval into stack
while (queue.is_empty() == false && queue.front.level <= level)
{
if (queue.front.level != counter)
{
// Switch level
print("\n");
counter = queue.front.level;
print_stack(stack);
}
stack.push(queue.front.element.data);
// remove a queue node
queue.dequeue();
}
if (stack.is_empty() == false)
{
print("\n");
print_stack(stack);
}
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create tree object
var tree: BinaryTree = new BinaryTree();
/*
8
/ \
/ \
/ \
5 10
/ \ / \
1 3 11 2
/ \ \ \
6 9 4 12
/ \ \
15 13 17
/ \ /
20 31 32
-----------------
Construct binary tree
*/
tree.root = new TreeNode(8);
tree.root.left = new TreeNode(5);
tree.root.left.right = new TreeNode(3);
tree.root.left.right.right = new TreeNode(9);
tree.root.left.right.right.left = new TreeNode(15);
tree.root.left.right.right.left.left = new TreeNode(20);
tree.root.left.right.right.left.right = new TreeNode(31);
tree.root.left.left = new TreeNode(1);
tree.root.left.left.left = new TreeNode(6);
tree.root.right = new TreeNode(10);
tree.root.right.left = new TreeNode(11);
tree.root.right.left.right = new TreeNode(4);
tree.root.right.left.right.right = new TreeNode(13);
tree.root.right.left.right.right.left = new TreeNode(32);
tree.root.right.right = new TreeNode(2);
tree.root.right.right.right = new TreeNode(12);
tree.root.right.right.right.right = new TreeNode(17);
// Test Cases
tree.print_interval(2);
tree.print_interval(1);
tree.print_interval(3);
}
}Output
Direction Interval : 2
8
5 10
2 11 3 1
12 4 9 6
15 13 17
20 31 32
Direction Interval : 1
8
10 5
1 3 11 2
12 4 9 6
15 13 17
32 31 20
Direction Interval : 3
8
5 10
1 3 11 2
12 4 9 6
17 13 15
32 31 20/*
Swift 4 Program
Level order traversal with direction change of given intervals
*/
// 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;
}
}
// Stack Node
class StackNode
{
var data: Int;
var next: StackNode? ;
init(_ data: Int)
{
self.data = data;
self.next = 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;
}
}
}
// Define custom stack and its operation
class MyStack
{
var top: StackNode? ;
init()
{
self.top = nil;
}
// Add a new element in stack
func push(_ data: Int)
{
// Make a new stack node
let new_node: StackNode? = StackNode(data);
if (new_node != nil)
{
new_node!.next = self.top;
self.top = new_node;
}
else
{
print("Memory overflow\n", terminator: "");
}
}
// remove a top element in stack
func pop()
{
if (self.top != nil)
{
self.top = self.top!.next;
}
}
// Check that whether stack is empty or not
func is_empty()->Bool
{
if (self.top != nil)
{
return false;
}
else
{
return true;
}
}
// Used to get top element of stack
func peek()->Int
{
if (self.top != nil)
{
return self.top!.data;
}
else
{
return 0;
}
}
}
// Define Binary Tree
class BinaryTree
{
var root: TreeNode? ;
init()
{
// Set root of tree
self.root = nil;
}
func print_stack(_ stack: MyStack)
{
while (stack.is_empty() == false)
{
print(" ", stack.peek(), terminator: "");
stack.pop();
}
}
// Print binary tree level using change direction of given intervals
func print_interval(_ interval: Int)
{
if (self.root == nil)
{
print("\n Empty Binary Tree \n", terminator: "");
}
else
{
print("\n Direction Interval : ", interval, terminator: "");
// Get top node in tree
var node: TreeNode? = self.root;
// Define a Queue
let queue: MyQueue = MyQueue();
// Define a stack
let stack: MyStack = MyStack();
// Add first node at the level of one
queue.enqueue(node, 1);
var temp: QueueNode? = queue.front;
var level: Int = 0;
var counter: Int = 0;
// Add tree level
while (temp != nil)
{
node = temp!.element;
level = temp!.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);
}
temp = temp!.next;
}
// Change the direction in the given interval and print the tree nodes
while (queue.is_empty() == false)
{
// Get interval
level = (interval - 1) + queue.front!.level;
// Useful to find new levels in tree
counter = queue.front!.level - 1;
// print n level
while (queue.is_empty() == false && queue.front!.level <= level)
{
if (queue.front!.level != counter)
{
// switch level
print("\n", terminator: "");
counter = queue.front!.level;
}
print(" ", queue.front!.element!.data, terminator: "");
// remove a queue node
queue.dequeue();
}
if (queue.is_empty() == false)
{
level = (interval - 1) + queue.front!.level;
counter = queue.front!.level;
}
// Add interval into stack
while (queue.is_empty() == false && queue.front!.level <= level)
{
if (queue.front!.level != counter)
{
// Switch level
print("\n", terminator: "");
counter = queue.front!.level;
self.print_stack(stack);
}
stack.push(queue.front!.element!.data);
// remove a queue node
queue.dequeue();
}
if (stack.is_empty() == false)
{
print("\n", terminator: "");
self.print_stack(stack);
}
}
}
}
}
func main()
{
// Create tree object
let tree: BinaryTree = BinaryTree();
/*
8
/ \
/ \
/ \
5 10
/ \ / \
1 3 11 2
/ \ \ \
6 9 4 12
/ \ \
15 13 17
/ \ /
20 31 32
-----------------
Construct binary tree
*/
tree.root = TreeNode(8);
tree.root!.left = TreeNode(5);
tree.root!.left!.right = TreeNode(3);
tree.root!.left!.right!.right = TreeNode(9);
tree.root!.left!.right!.right!.left = TreeNode(15);
tree.root!.left!.right!.right!.left!.left = TreeNode(20);
tree.root!.left!.right!.right!.left!.right = TreeNode(31);
tree.root!.left!.left = TreeNode(1);
tree.root!.left!.left!.left = TreeNode(6);
tree.root!.right = TreeNode(10);
tree.root!.right!.left = TreeNode(11);
tree.root!.right!.left!.right = TreeNode(4);
tree.root!.right!.left!.right!.right = TreeNode(13);
tree.root!.right!.left!.right!.right!.left = TreeNode(32);
tree.root!.right!.right = TreeNode(2);
tree.root!.right!.right!.right = TreeNode(12);
tree.root!.right!.right!.right!.right = TreeNode(17);
// Test Cases
tree.print_interval(2);
tree.print_interval(1);
tree.print_interval(3);
}
main();Output
Direction Interval : 2
8
5 10
2 11 3 1
12 4 9 6
15 13 17
20 31 32
Direction Interval : 1
8
10 5
1 3 11 2
12 4 9 6
15 13 17
32 31 20
Direction Interval : 3
8
5 10
1 3 11 2
12 4 9 6
17 13 15
32 31 20
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