Skip to main content

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

Top view of binary tree

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

  1. Initialize a queue and enqueue the root node with distance 0.
  2. Print the root node's data, as it will be part of the top view.
  3. 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.
  4. 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.





Comment

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

New Comment