Print top view of a binary tree using level order traversal
The problem at hand is to print the top view of a binary tree using a level-order traversal. The top view of a binary tree refers to the set of nodes visible when looking at the tree from the top. This view captures the nodes that would appear in a vertical line when viewed from above.
Problem Statement
Given a binary tree, the task is to print its top view using a level-order traversal. This involves determining the nodes that are visible when looking at the tree from the top.
Example Scenario
Imagine you have a binary tree with various levels and branches. The top view of this tree would consist of the nodes that are visible when looking at the tree from the top, considering the vertical alignment of nodes.
Idea to Solve the Problem

To solve this problem, you can perform a level-order traversal of the binary tree using a queue. While traversing the tree level by level, you need to keep track of the horizontal distance of each node from the root node. For each horizontal distance, you should only print the first encountered node, as it will be the one visible from the top view at that horizontal distance.
Pseudocode
struct QueueNode {
struct TreeNode *element;
struct QueueNode *next;
int distance;
};
struct MyQueue {
// ...
};
void printTopView(struct TreeNode *root) {
// Create an empty queue
// Create variables to track minimum and maximum distances
// Add root node to the queue with distance 0
// Print the root node's data
// Traverse the tree level by level
while (queue is not empty) {
// Dequeue a node from the queue
// Get the node's distance
// If the node's distance is outside the current boundaries,
// update the boundaries and print the node's data
// Enqueue the left child with distance - 1
// Enqueue the right child with distance + 1
}
}
Algorithm Explanation
- Initialize a queue and enqueue the root node with distance 0.
- Print the root node's data, as it will be part of the top view.
- Traverse the tree using the queue:
- Dequeue a node from the queue and get its distance.
- If the node's distance is outside the current boundaries (min and max), update the boundaries and print the node's data.
- Enqueue the left child with a distance of
distance - 1
. - Enqueue the right child with a distance of
distance + 1
.
- Continue this process until the queue is empty.
Code Solution
/*
C Program
Print top view of a binary tree using level order traversal
*/
#include <stdio.h>
#include <stdlib.h>
// Queue node
struct QueueNode
{
struct TreeNode *element;
struct QueueNode *next;
int distance;
};
// Define queue
struct MyQueue
{
struct QueueNode *front;
struct QueueNode *tail;
};
// Binary Tree node
struct TreeNode
{
int data;
struct TreeNode *left, *right;
};
struct BinaryTree
{
struct TreeNode *root;
};
struct MyQueue *makeQueue()
{
// Create dynamic node of MyQueue
struct MyQueue *node = (struct MyQueue *) malloc(sizeof(struct MyQueue));
if (node == NULL)
{
printf("\n Memory Overflow, when creating a new Queue\n");
}
else
{
node->front = NULL;
node->tail = NULL;
}
return node;
}
// Returns a new node of tree
struct TreeNode *newNode(int data)
{
// Create dynamic node
struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
if (node != NULL)
{
//Set data and pointer values
node->data = data;
node->left = NULL;
node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
return node;
}
struct BinaryTree *makeTree()
{
// Create dynamic node of BinaryTree
struct BinaryTree *node = (struct BinaryTree *) malloc(sizeof(struct BinaryTree));
if (node == NULL)
{
printf("\nMemory Overflow, when creating a new BinaryTree\n");
}
else
{
node->root = NULL;
}
return node;
}
int isEmpty(struct MyQueue *queue)
{
if (queue == NULL || queue->front == NULL)
{
return 1;
}
else
{
return 0;
}
}
// Create a queue node and returns this node
void enqueue(struct MyQueue *queue, struct TreeNode *element, int distance)
{
// Make a new Queue node
struct QueueNode *node = (struct QueueNode *) malloc(sizeof(struct QueueNode));
if (node != NULL)
{
// Set node values
node->element = element;
node->next = NULL;
node->distance = distance;
if (queue->front == NULL)
{
queue->front = node;
queue->tail = queue->front;
}
else
{
queue->tail->next = node;
queue->tail = node;
}
}
else
{
printf("\nMemory Overflow, when creating a new Queue Node\n");
}
}
//Remove a queue elements
void dequeue(struct MyQueue *queue)
{
if (isEmpty(queue) == 0)
{
struct QueueNode *remove = queue->front;
if (queue->front == queue->tail)
{
queue->tail = NULL;
}
queue->front = queue->front->next;
remove->element = NULL;
remove->next = NULL;
//free node
free(remove);
remove = NULL;
}
}
// Return front element of queue
struct QueueNode *peek(struct MyQueue *queue)
{
if (isEmpty(queue) == 1)
{
return NULL;
}
else
{
return queue->front;
}
}
// Display top view of binary tree using level order traversal
void printTopView(struct TreeNode *root)
{
if (root == NULL)
{
return;
}
else
{
struct MyQueue *q = makeQueue();
// min and max decide boundary of top view
int min = 0;
int max = 0;
int distance = 0;
// Add first element
enqueue(q, root, 0);
struct TreeNode *node = root;
// root node of tree is always part of top view
printf("\n Level order Top view of binary tree \n %d", root->data);
while (node != NULL)
{
// Get node distance
distance = peek(q)->distance;
if (node->left != NULL)
{
if (min > distance - 1)
{
min = distance - 1;
// Displaying the result top view node
printf(" %d", node->left->data);
}
enqueue(q, node->left, distance - 1);
}
if (node->right != NULL)
{
if (max < distance + 1)
{
max = distance + 1;
// Displaying the result top view node
printf(" %d", node->right->data);
}
enqueue(q, node->right, distance + 1);
}
// Remove queue element
dequeue(q);
if (isEmpty(q) == 1)
{
node = NULL;
}
else
{
// Get tree node
node = peek(q)->element;
}
}
printf("\n");
}
}
int main(int argc, char
const *argv[])
{
// Define tree
struct BinaryTree *tree = makeTree();
/*
1
/ \
2 3
/ \ \
4 5 11
/ \ / \
6 7 8 9
\
10
\
15
-----------------------
Binary Tree
-----------------------
*/
tree->root = newNode(1);
tree->root->left = newNode(2);
tree->root->right = newNode(3);
tree->root->left->left = newNode(4);
tree->root->left->right = newNode(5);
tree->root->left->left->left = newNode(6);
tree->root->left->left->right = newNode(7);
tree->root->left->right->left = newNode(8);
tree->root->left->right->right = newNode(9);
tree->root->left->right->right->right = newNode(10);
tree->root->right->right = newNode(11);
tree->root->left->right->right->right->right = newNode(15);
printTopView(tree->root);
return 0;
}
Output
Level order Top view of binary tree
1 2 3 4 11 6 15
/*
Java Program
Print top view of a binary tree using level order traversal
*/
// 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 int distance;
public QueueNode next;
public QueueNode(TreeNode element, int distance)
{
this.element = element;
this.next = null;
this.distance = distance;
}
}
//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 distance)
{
QueueNode new_node = new QueueNode(element, distance);
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 front 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 isEmpty()
{
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
public QueueNode peek()
{
if (isEmpty() == false)
{
return this.front;
}
else
{
return null;
}
}
}
// Define Binary Tree
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set root of tree
this.root = null;
}
// Display top view of binary tree using level order traversal
public void printTopView()
{
if (this.root == null)
{
return;
}
else
{
MyQueue q = new MyQueue();
// min and max decide boundary of top view
int min = 0;
int max = 0;
int distance = 0;
// Add first element
q.enqueue(this.root, 0);
TreeNode node = this.root;
// root node of tree is always part of top view
System.out.print("\n Level order Top view of binary tree \n " + node.data);
while (node != null)
{
// Get node distance
distance = q.peek().distance;
if (node.left != null)
{
if (min > distance - 1)
{
min = distance - 1;
// Displaying the result top view node
System.out.print(" " + node.left.data);
}
q.enqueue(node.left, distance - 1);
}
if (node.right != null)
{
if (max < distance + 1)
{
max = distance + 1;
// Displaying the result top view node
System.out.print(" " + node.right.data);
}
q.enqueue(node.right, distance + 1);
}
// Remove queue element
q.dequeue();
if (q.isEmpty() == true)
{
node = null;
}
else
{
// Get tree node
node = q.peek().element;
}
}
System.out.print("\n");
}
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
1
/ \
2 3
/ \ \
4 5 11
/ \ / \
6 7 8 9
\
10
\
15
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(4);
tree.root.left.right = new TreeNode(5);
tree.root.left.left.left = new TreeNode(6);
tree.root.left.left.right = new TreeNode(7);
tree.root.left.right.left = new TreeNode(8);
tree.root.left.right.right = new TreeNode(9);
tree.root.left.right.right.right = new TreeNode(10);
tree.root.right.right = new TreeNode(11);
tree.root.left.right.right.right.right = new TreeNode(15);
tree.printTopView();
}
}
Output
Level order Top view of binary tree
1 2 3 4 11 6 15
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Print top view of a binary tree using level order traversal
*/
// 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;
int distance;
QueueNode *next;
QueueNode(TreeNode *element, int distance)
{
this->element = element;
this->next = NULL;
this->distance = distance;
}
};
//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 distance)
{
QueueNode *new_node = new QueueNode(element, distance);
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 front 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 isEmpty()
{
if (this->front == NULL)
{
return true;
}
else
{
return false;
}
}
QueueNode *peek()
{
if (this->isEmpty() == false)
{
return this->front;
}
else
{
return NULL;
}
}
};
// Define Binary Tree
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
// Set root of tree
this->root = NULL;
}
// Display top view of binary tree using level order traversal
void printTopView()
{
if (this->root == NULL)
{
return;
}
else
{
MyQueue q = MyQueue();
// min and max decide boundary of top view
int min = 0;
int max = 0;
int distance = 0;
// Add first element
q.enqueue(this->root, 0);
TreeNode *node = this->root;
// root node of tree is always part of top view
cout << "\n Level order Top view of binary tree \n " << node->data;
while (node != NULL)
{
// Get node distance
distance = q.peek()->distance;
if (node->left != NULL)
{
if (min > distance - 1)
{
min = distance - 1;
// Displaying the result top view node
cout << " " << node->left->data;
}
q.enqueue(node->left, distance - 1);
}
if (node->right != NULL)
{
if (max < distance + 1)
{
max = distance + 1;
// Displaying the result top view node
cout << " " << node->right->data;
}
q.enqueue(node->right, distance + 1);
}
// Remove queue element
q.dequeue();
if (q.isEmpty() == true)
{
node = NULL;
}
else
{
// Get tree node
node = q.peek()->element;
}
}
cout << "\n";
}
}
};
int main()
{
BinaryTree tree = BinaryTree();
/*
1
/ \
2 3
/ \ \
4 5 11
/ \ / \
6 7 8 9
\
10
\
15
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root->left = new TreeNode(2);
tree.root->right = new TreeNode(3);
tree.root->left->left = new TreeNode(4);
tree.root->left->right = new TreeNode(5);
tree.root->left->left->left = new TreeNode(6);
tree.root->left->left->right = new TreeNode(7);
tree.root->left->right->left = new TreeNode(8);
tree.root->left->right->right = new TreeNode(9);
tree.root->left->right->right->right = new TreeNode(10);
tree.root->right->right = new TreeNode(11);
tree.root->left->right->right->right->right = new TreeNode(15);
tree.printTopView();
return 0;
}
Output
Level order Top view of binary tree
1 2 3 4 11 6 15
// Include namespace system
using System;
/*
C# Program
Print top view of a binary tree using level order traversal
*/
// Binary Tree node
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Queue Node
public class QueueNode
{
public TreeNode element;
public int distance;
public QueueNode next;
public QueueNode(TreeNode element, int distance)
{
this.element = element;
this.next = null;
this.distance = distance;
}
}
//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 distance)
{
QueueNode new_node = new QueueNode(element, distance);
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 front 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 isEmpty()
{
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
public QueueNode peek()
{
if (isEmpty() == false)
{
return this.front;
}
else
{
return null;
}
}
}
// Define Binary Tree
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set root of tree
this.root = null;
}
// Display top view of binary tree using level order traversal
public void printTopView()
{
if (this.root == null)
{
return;
}
else
{
MyQueue q = new MyQueue();
// min and max decide boundary of top view
int min = 0;
int max = 0;
int distance = 0;
// Add first element
q.enqueue(this.root, 0);
TreeNode node = this.root;
// root node of tree is always part of top view
Console.Write("\n Level order Top view of binary tree \n " + node.data);
while (node != null)
{
// Get node distance
distance = q.peek().distance;
if (node.left != null)
{
if (min > distance - 1)
{
min = distance - 1;
// Displaying the result top view node
Console.Write(" " + node.left.data);
}
q.enqueue(node.left, distance - 1);
}
if (node.right != null)
{
if (max < distance + 1)
{
max = distance + 1;
// Displaying the result top view node
Console.Write(" " + node.right.data);
}
q.enqueue(node.right, distance + 1);
}
// Remove queue element
q.dequeue();
if (q.isEmpty() == true)
{
node = null;
}
else
{
// Get tree node
node = q.peek().element;
}
}
Console.Write("\n");
}
}
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
1
/ \
2 3
/ \ \
4 5 11
/ \ / \
6 7 8 9
\
10
\
15
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(4);
tree.root.left.right = new TreeNode(5);
tree.root.left.left.left = new TreeNode(6);
tree.root.left.left.right = new TreeNode(7);
tree.root.left.right.left = new TreeNode(8);
tree.root.left.right.right = new TreeNode(9);
tree.root.left.right.right.right = new TreeNode(10);
tree.root.right.right = new TreeNode(11);
tree.root.left.right.right.right.right = new TreeNode(15);
tree.printTopView();
}
}
Output
Level order Top view of binary tree
1 2 3 4 11 6 15
<?php
/*
Php Program
Print top view of a binary tree using level order traversal
*/
// 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 $distance;
public $next;
function __construct($element, $distance)
{
$this->element = $element;
$this->next = null;
$this->distance = $distance;
}
}
//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, $distance)
{
$new_node = new QueueNode($element, $distance);
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 front 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 isEmpty()
{
if ($this->front == null)
{
return true;
}
else
{
return false;
}
}
public function peek()
{
if ($this->isEmpty() == false)
{
return $this->front;
}
else
{
return null;
}
}
}
// Define Binary Tree
class BinaryTree
{
public $root;
function __construct()
{
// Set root of tree
$this->root = null;
}
// Display top view of binary tree using level order traversal
public function printTopView()
{
if ($this->root == null)
{
return;
}
else
{
$q = new MyQueue();
// min and max decide boundary of top view
$min = 0;
$max = 0;
$distance = 0;
// Add first element
$q->enqueue($this->root, 0);
$node = $this->root;
// root node of tree is always part of top view
echo "\n Level order Top view of binary tree \n ". $node->data;
while ($node != null)
{
// Get node distance
$distance = $q->peek()->distance;
if ($node->left != null)
{
if ($min > $distance - 1)
{
$min = $distance - 1;
// Displaying the result top view node
echo " ". $node->left->data;
}
$q->enqueue($node->left, $distance - 1);
}
if ($node->right != null)
{
if ($max < $distance + 1)
{
$max = $distance + 1;
// Displaying the result top view node
echo " ". $node->right->data;
}
$q->enqueue($node->right, $distance + 1);
}
// Remove queue element
$q->dequeue();
if ($q->isEmpty() == true)
{
$node = null;
}
else
{
// Get tree node
$node = $q->peek()->element;
}
}
echo "\n";
}
}
}
function main()
{
$tree = new BinaryTree();
/*
1
/ \
2 3
/ \ \
4 5 11
/ \ / \
6 7 8 9
\
10
\
15
-----------------------
Binary Tree
-----------------------
*/
$tree->root = new TreeNode(1);
$tree->root->left = new TreeNode(2);
$tree->root->right = new TreeNode(3);
$tree->root->left->left = new TreeNode(4);
$tree->root->left->right = new TreeNode(5);
$tree->root->left->left->left = new TreeNode(6);
$tree->root->left->left->right = new TreeNode(7);
$tree->root->left->right->left = new TreeNode(8);
$tree->root->left->right->right = new TreeNode(9);
$tree->root->left->right->right->right = new TreeNode(10);
$tree->root->right->right = new TreeNode(11);
$tree->root->left->right->right->right->right = new TreeNode(15);
$tree->printTopView();
}
main();
Output
Level order Top view of binary tree
1 2 3 4 11 6 15
/*
Node Js Program
Print top view of a binary tree using level order traversal
*/
// 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, distance)
{
this.element = element;
this.next = null;
this.distance = distance;
}
}
//Define custom queue class
class MyQueue
{
constructor()
{
this.front = null;
this.tail = null;
}
// Add a new node at last of queue
enqueue(element, distance)
{
var new_node = new QueueNode(element, distance);
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 front 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;
}
}
}
isEmpty()
{
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
peek()
{
if (this.isEmpty() == false)
{
return this.front;
}
else
{
return null;
}
}
}
// Define Binary Tree
class BinaryTree
{
constructor()
{
// Set root of tree
this.root = null;
}
// Display top view of binary tree using level order traversal
printTopView()
{
if (this.root == null)
{
return;
}
else
{
var q = new MyQueue();
// min and max decide boundary of top view
var min = 0;
var max = 0;
var distance = 0;
// Add first element
q.enqueue(this.root, 0);
var node = this.root;
// root node of tree is always part of top view
process.stdout.write("\n Level order Top view of binary tree \n " + node.data);
while (node != null)
{
// Get node distance
distance = q.peek().distance;
if (node.left != null)
{
if (min > distance - 1)
{
min = distance - 1;
// Displaying the result top view node
process.stdout.write(" " + node.left.data);
}
q.enqueue(node.left, distance - 1);
}
if (node.right != null)
{
if (max < distance + 1)
{
max = distance + 1;
// Displaying the result top view node
process.stdout.write(" " + node.right.data);
}
q.enqueue(node.right, distance + 1);
}
// Remove queue element
q.dequeue();
if (q.isEmpty() == true)
{
node = null;
}
else
{
// Get tree node
node = q.peek().element;
}
}
process.stdout.write("\n");
}
}
}
function main()
{
var tree = new BinaryTree();
/*
1
/ \
2 3
/ \ \
4 5 11
/ \ / \
6 7 8 9
\
10
\
15
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(4);
tree.root.left.right = new TreeNode(5);
tree.root.left.left.left = new TreeNode(6);
tree.root.left.left.right = new TreeNode(7);
tree.root.left.right.left = new TreeNode(8);
tree.root.left.right.right = new TreeNode(9);
tree.root.left.right.right.right = new TreeNode(10);
tree.root.right.right = new TreeNode(11);
tree.root.left.right.right.right.right = new TreeNode(15);
tree.printTopView();
}
main();
Output
Level order Top view of binary tree
1 2 3 4 11 6 15
# Python 3 Program
# Print top view of a binary tree using level order traversal
# 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, distance) :
self.element = element
self.next = None
self.distance = distance
# 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, distance) :
new_node = QueueNode(element, distance)
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 front 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 isEmpty(self) :
if (self.front == None) :
return True
else :
return False
def peek(self) :
if (self.isEmpty() == False) :
return self.front
else :
return None
# Define Binary Tree
class BinaryTree :
def __init__(self) :
# Set root of tree
self.root = None
# Display top view of binary tree using level order traversal
def printTopView(self) :
if (self.root == None) :
return
else :
q = MyQueue()
# min and max decide boundary of top view
min = 0
max = 0
distance = 0
# Add first element
q.enqueue(self.root, 0)
node = self.root
# root node of tree is always part of top view
print("\n Level order Top view of binary tree \n ", node.data, end = "")
while (node != None) :
# Get node distance
distance = q.peek().distance
if (node.left != None) :
if (min > distance - 1) :
min = distance - 1
# Displaying the result top view node
print(" ", node.left.data, end = "")
q.enqueue(node.left, distance - 1)
if (node.right != None) :
if (max < distance + 1) :
max = distance + 1
# Displaying the result top view node
print(" ", node.right.data, end = "")
q.enqueue(node.right, distance + 1)
# Remove queue element
q.dequeue()
if (q.isEmpty() == True) :
node = None
else :
# Get tree node
node = q.peek().element
print(end = "\n")
def main() :
tree = BinaryTree()
#
# 1
# / \
# 2 3
# / \ \
# 4 5 11
# / \ / \
# 6 7 8 9
# \
# 10
# \
# 15
# -----------------------
# Binary Tree
# -----------------------
tree.root = TreeNode(1)
tree.root.left = TreeNode(2)
tree.root.right = TreeNode(3)
tree.root.left.left = TreeNode(4)
tree.root.left.right = TreeNode(5)
tree.root.left.left.left = TreeNode(6)
tree.root.left.left.right = TreeNode(7)
tree.root.left.right.left = TreeNode(8)
tree.root.left.right.right = TreeNode(9)
tree.root.left.right.right.right = TreeNode(10)
tree.root.right.right = TreeNode(11)
tree.root.left.right.right.right.right = TreeNode(15)
tree.printTopView()
if __name__ == "__main__": main()
Output
Level order Top view of binary tree
1 2 3 4 11 6 15
# Ruby Program
# Print top view of a binary tree using level order traversal
# 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, :distance, :next
attr_accessor :element, :distance, :next
def initialize(element, distance)
self.element = element
self.next = nil
self.distance = distance
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, distance)
new_node = QueueNode.new(element, distance)
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 front 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 isEmpty()
if (self.front == nil)
return true
else
return false
end
end
def peek()
if (self.isEmpty() == false)
return self.front
else
return nil
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
# Display top view of binary tree using level order traversal
def printTopView()
if (self.root == nil)
return
else
q = MyQueue.new()
# min and max decide boundary of top view
min = 0
max = 0
distance = 0
# Add first element
q.enqueue(self.root, 0)
node = self.root
# root node of tree is always part of top view
print("\n Level order Top view of binary tree \n ", node.data)
while (node != nil)
# Get node distance
distance = q.peek().distance
if (node.left != nil)
if (min > distance - 1)
min = distance - 1
# Displaying the result top view node
print(" ", node.left.data)
end
q.enqueue(node.left, distance - 1)
end
if (node.right != nil)
if (max < distance + 1)
max = distance + 1
# Displaying the result top view node
print(" ", node.right.data)
end
q.enqueue(node.right, distance + 1)
end
# Remove queue element
q.dequeue()
if (q.isEmpty() == true)
node = nil
else
# Get tree node
node = q.peek().element
end
end
print("\n")
end
end
end
def main()
tree = BinaryTree.new()
#
# 1
# / \
# 2 3
# / \ \
# 4 5 11
# / \ / \
# 6 7 8 9
# \
# 10
# \
# 15
# -----------------------
# Binary Tree
# -----------------------
tree.root = TreeNode.new(1)
tree.root.left = TreeNode.new(2)
tree.root.right = TreeNode.new(3)
tree.root.left.left = TreeNode.new(4)
tree.root.left.right = TreeNode.new(5)
tree.root.left.left.left = TreeNode.new(6)
tree.root.left.left.right = TreeNode.new(7)
tree.root.left.right.left = TreeNode.new(8)
tree.root.left.right.right = TreeNode.new(9)
tree.root.left.right.right.right = TreeNode.new(10)
tree.root.right.right = TreeNode.new(11)
tree.root.left.right.right.right.right = TreeNode.new(15)
tree.printTopView()
end
main()
Output
Level order Top view of binary tree
1 2 3 4 11 6 15
/*
Scala Program
Print top view of a binary tree using level order traversal
*/
// 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 distance: Int , var next: QueueNode)
{
def this(element: TreeNode, distance: Int)
{
this(element, distance, null);
}
}
//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, distance: Int): Unit = {
var new_node: QueueNode = new QueueNode(element, distance);
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 front 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 isEmpty(): Boolean = {
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
def peek(): QueueNode = {
if (this.isEmpty() == false)
{
return this.front;
}
else
{
return null;
}
}
}
// Define Binary Tree
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
// Display top view of binary tree using level order traversal
def printTopView(): Unit = {
if (this.root == null)
{
return;
}
else
{
var q: MyQueue = new MyQueue();
// min and max decide boundary of top view
var min: Int = 0;
var max: Int = 0;
var distance: Int = 0;
// Add first element
q.enqueue(this.root, 0);
var node: TreeNode = this.root;
// root node of tree is always part of top view
print("\n Level order Top view of binary tree \n " + node.data);
while (node != null)
{
// Get node distance
distance = q.peek().distance;
if (node.left != null)
{
if (min > distance - 1)
{
min = distance - 1;
// Displaying the result top view node
print(" " + node.left.data);
}
q.enqueue(node.left, distance - 1);
}
if (node.right != null)
{
if (max < distance + 1)
{
max = distance + 1;
// Displaying the result top view node
print(" " + node.right.data);
}
q.enqueue(node.right, distance + 1);
}
// Remove queue element
q.dequeue();
if (q.isEmpty() == true)
{
node = null;
}
else
{
// Get tree node
node = q.peek().element;
}
}
print("\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinaryTree = new BinaryTree();
/*
1
/ \
2 3
/ \ \
4 5 11
/ \ / \
6 7 8 9
\
10
\
15
-----------------------
Binary Tree
-----------------------
*/
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(4);
tree.root.left.right = new TreeNode(5);
tree.root.left.left.left = new TreeNode(6);
tree.root.left.left.right = new TreeNode(7);
tree.root.left.right.left = new TreeNode(8);
tree.root.left.right.right = new TreeNode(9);
tree.root.left.right.right.right = new TreeNode(10);
tree.root.right.right = new TreeNode(11);
tree.root.left.right.right.right.right = new TreeNode(15);
tree.printTopView();
}
}
Output
Level order Top view of binary tree
1 2 3 4 11 6 15
/*
Swift 4 Program
Print top view of a binary tree using level order traversal
*/
// 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 distance: Int;
var next: QueueNode? ;
init(_ element: TreeNode? , _ distance : Int)
{
self.element = element;
self.next = nil;
self.distance = distance;
}
}
//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? , _ distance : Int)
{
let new_node: QueueNode? = QueueNode(element, distance);
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 front 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 isEmpty()->Bool
{
if (self.front == nil)
{
return true;
}
else
{
return false;
}
}
func peek()->QueueNode?
{
if (self.isEmpty() == false)
{
return self.front;
}
else
{
return nil;
}
}
}
// Define Binary Tree
class BinaryTree
{
var root: TreeNode? ;
init()
{
// Set root of tree
self.root = nil;
}
// Display top view of binary tree using level order traversal
func printTopView()
{
if (self.root == nil)
{
return;
}
else
{
let q: MyQueue = MyQueue();
// min and max decide boundary of top view
var min: Int = 0;
var max: Int = 0;
var distance: Int = 0;
// Add first element
q.enqueue(self.root, 0);
var node: TreeNode? = self.root;
// root node of tree is always part of top view
print("\n Level order Top view of binary tree \n ", node!.data, terminator: "");
while (node != nil)
{
// Get node distance
distance = q.peek()!.distance;
if (node!.left != nil)
{
if (min > distance - 1)
{
min = distance - 1;
// Displaying the result top view node
print(" ", node!.left!.data, terminator: "");
}
q.enqueue(node!.left, distance - 1);
}
if (node!.right != nil)
{
if (max < distance + 1)
{
max = distance + 1;
// Displaying the result top view node
print(" ", node!.right!.data, terminator: "");
}
q.enqueue(node!.right, distance + 1);
}
// Remove queue element
q.dequeue();
if (q.isEmpty() == true)
{
node = nil;
}
else
{
// Get tree node
node = q.peek()!.element;
}
}
print(terminator: "\n");
}
}
}
func main()
{
let tree: BinaryTree = BinaryTree();
/*
1
/ \
2 3
/ \ \
4 5 11
/ \ / \
6 7 8 9
\
10
\
15
-----------------------
Binary Tree
-----------------------
*/
tree.root = TreeNode(1);
tree.root!.left = TreeNode(2);
tree.root!.right = TreeNode(3);
tree.root!.left!.left = TreeNode(4);
tree.root!.left!.right = TreeNode(5);
tree.root!.left!.left!.left = TreeNode(6);
tree.root!.left!.left!.right = TreeNode(7);
tree.root!.left!.right!.left = TreeNode(8);
tree.root!.left!.right!.right = TreeNode(9);
tree.root!.left!.right!.right!.right = TreeNode(10);
tree.root!.right!.right = TreeNode(11);
tree.root!.left!.right!.right!.right!.right = TreeNode(15);
tree.printTopView();
}
main();
Output
Level order Top view of binary tree
1 2 3 4 11 6 15
/*
Kotlin Program
Print top view of a binary tree using level order traversal
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Queue Node
class QueueNode
{
var element: TreeNode ? ;
var distance: Int;
var next: QueueNode ? ;
constructor(element: TreeNode ? , distance : Int)
{
this.element = element;
this.next = null;
this.distance = distance;
}
}
//Define custom queue class
class MyQueue
{
var front: QueueNode ? ;
var tail: QueueNode ? ;
constructor()
{
this.front = null;
this.tail = null;
}
// Add a new node at last of queue
fun enqueue(element: TreeNode ? , distance : Int): Unit
{
var new_node: QueueNode ? = QueueNode(element, distance);
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 front node of queue
fun dequeue(): Unit
{
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front?.next;
}
}
}
fun isEmpty(): Boolean
{
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
fun peek(): QueueNode ?
{
if (this.isEmpty() == false)
{
return this.front;
}
else
{
return null;
}
}
}
// Define Binary Tree
class BinaryTree
{
var root: TreeNode ? ;
constructor()
{
// Set root of tree
this.root = null;
}
// Display top view of binary tree using level order traversal
fun printTopView(): Unit
{
if (this.root == null)
{
return;
}
else
{
var q: MyQueue = MyQueue();
// min and max decide boundary of top view
var min: Int = 0;
var max: Int = 0;
var distance: Int;
// Add first element
q.enqueue(this.root, 0);
var node: TreeNode ? = this.root;
// root node of tree is always part of top view
print("\n Level order Top view of binary tree \n " + node!!.data);
while (node != null)
{
// Get node distance
distance = q.peek()!!.distance;
if (node.left != null)
{
if (min > distance - 1)
{
min = distance - 1;
// Displaying the result top view node
print(" " + node.left!!.data);
}
q.enqueue(node.left, distance - 1);
}
if (node.right != null)
{
if (max < distance + 1)
{
max = distance + 1;
// Displaying the result top view node
print(" " + node.right!!.data);
}
q.enqueue(node.right, distance + 1);
}
// Remove queue element
q.dequeue();
if (q.isEmpty() == true)
{
node = null;
}
else
{
// Get tree node
node = q.peek()?.element;
}
}
print("\n");
}
}
}
fun main(args: Array <String> ): Unit
{
var tree: BinaryTree = BinaryTree();
/*
1
/ \
2 3
/ \ \
4 5 11
/ \ / \
6 7 8 9
\
10
\
15
-----------------------
Binary Tree
-----------------------
*/
tree.root = TreeNode(1);
tree.root?.left = TreeNode(2);
tree.root?.right = TreeNode(3);
tree.root?.left?.left = TreeNode(4);
tree.root?.left?.right = TreeNode(5);
tree.root?.left?.left?.left = TreeNode(6);
tree.root?.left?.left?.right = TreeNode(7);
tree.root?.left?.right?.left = TreeNode(8);
tree.root?.left?.right?.right = TreeNode(9);
tree.root?.left?.right?.right?.right = TreeNode(10);
tree.root?.right?.right = TreeNode(11);
tree.root?.left?.right?.right?.right?.right = TreeNode(15);
tree.printTopView();
}
Output
Level order Top view of binary tree
1 2 3 4 11 6 15
Output Explanation
The code demonstrates the printing of the top view of a binary tree using a level-order traversal. It enqueues and dequeues nodes while maintaining the min and max distances to determine the visible nodes from the top view.
Time Complexity
The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. Each node is enqueued and dequeued once, and each operation takes constant time. The space complexity is O(w), where w is the maximum width of the tree (number of nodes in a level), due to the queue's space usage.
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