Sum of nodes in top view of binary tree
The problem at hand involves finding the sum of nodes in the top view of a binary tree. The top view of a binary tree is defined as the set of nodes visible when looking at the tree from the top. The task is to calculate the sum of these visible nodes.
Problem Statement
Given a binary tree, the goal is to find the sum of nodes that are part of the top view of the tree. The top view nodes are the ones that would be visible when looking at the tree from above.
Example
Consider the following binary tree:

The top view of this tree is: 1, 2, 3, 4, 11, 6, 14, -3. The sum of these nodes is 38.
Idea to Solve
To solve this problem, we can perform a level order traversal of the tree while keeping track of the horizontal distance of each node from the root. We'll use a queue to store nodes as we traverse the tree. We'll also use a hash table or an array to keep track of the first node encountered at each horizontal distance.
Pseudocode
sumTopView(root):
Create an empty queue
Enqueue (root, 0) into the queue
Initialize min_distance = 0, max_distance = 0
Initialize a hash table or array to store top view nodes
Initialize sum = root.data
Print root.data
while queue is not empty:
Dequeue a node, distance from the queue
Update min_distance and max_distance
if distance not in hash table:
Insert the node's data into the hash table or array
Update sum
if node has left child:
Enqueue (left child, distance - 1) into the queue
if node has right child:
Enqueue (right child, distance + 1) into the queue
Print sum
Algorithm Explanation
- We start by initializing a queue and enqueue the root node with a distance of 0. We also initialize variables to track the minimum and maximum distances encountered.
- We use a hash table or array to store the first node encountered at each horizontal distance. This helps us determine the top view nodes.
- As we dequeue nodes from the queue, we check if the current distance is not present in the hash table. If not, we insert the node's data into the hash table and update the sum of top view nodes.
- We then enqueue the left and right children of the current node if they exist, with appropriate distances.
- The process continues until the queue is empty.
- Finally, we print the sum of top view nodes.
Code Solution
/*
C Program
Sum of nodes in top view of binary tree
*/
#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;
}
}
// Sum of nodes in top view
void sumTopView(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;
int sum = root->data;
// Add first element
enqueue(q, root, 0);
struct TreeNode *node = root;
// root node of tree is always part of top view
printf("\n 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;
printf(" %d", node->left->data);
// Add the result top view node
sum += node->left->data;
}
enqueue(q, node->left, distance - 1);
}
if (node->right != NULL)
{
if (max < distance + 1)
{
max = distance + 1;
printf(" %d", node->right->data);
// Add the result top view node
sum += 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 Sum of nodes : %d \n", sum);
}
}
int main(int argc, char
const *argv[])
{
// Define tree
struct BinaryTree *tree = makeTree();
/*
1
/ \
2 3
/ \ \
4 5 11
/ \ / \
6 7 8 9
/ \
-2 10
/ \
-1 14
/
-3
-----------------------
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(14);
tree->root->left->left->right->left = newNode(-2);
tree->root->left->left->right->left->left = newNode(-1);
tree->root->left->left->right->left->left->left = newNode(-3);
sumTopView(tree->root);
return 0;
}
Output
Top view of binary tree
1 2 3 4 11 6 14 -3
Sum of nodes : 38
/*
Java Program
Sum of nodes in top view of binary tree
*/
// Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Queue Node
class QueueNode
{
public TreeNode element;
public 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;
}
// Sum of nodes in top view
public void sumTopView()
{
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 sum = this.root.data;
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;
// Add the result top view node
sum += node.left.data;
System.out.print(" " + node.left.data);
}
q.enqueue(node.left, distance - 1);
}
if (node.right != null)
{
if (max < distance + 1)
{
max = distance + 1;
// Add the result top view node
sum += node.right.data;
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 Sum of nodes : " + sum + " \n");
}
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
1
/ \
2 3
/ \ \
4 5 11
/ \ / \
6 7 8 9
/ \
-2 10
/ \
-1 14
/
-3
-----------------------
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(14);
tree.root.left.left.right.left = new TreeNode(-2);
tree.root.left.left.right.left.left = new TreeNode(-1);
tree.root.left.left.right.left.left.left = new TreeNode(-3);
tree.sumTopView();
}
}
Output
Level order Top view of binary tree
1 2 3 4 11 6 14 -3
Sum of nodes : 38
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Sum of nodes in top view of binary tree
*/
// Binary Tree node
class TreeNode
{
public: int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// Queue Node
class QueueNode
{
public: TreeNode *element;
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)
{
if (this->tail == this->front)
{
this->tail = NULL;
this->front = NULL;
}
else
{
this->front = this->front->next;
}
}
}
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;
}
// Sum of nodes in top view
void sumTopView()
{
if (this->root == NULL)
{
return;
}
else
{
MyQueue q = MyQueue();
// min and max decide boundary of top view
int min = 0;
int max = 0;
int sum = this->root->data;
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;
// Add the result top view node
sum += node->left->data;
cout << " " << node->left->data;
}
q.enqueue(node->left, distance - 1);
}
if (node->right != NULL)
{
if (max < distance + 1)
{
max = distance + 1;
// Add the result top view node
sum += node->right->data;
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 Sum of nodes : " << sum << " \n";
}
}
};
int main()
{
BinaryTree tree = BinaryTree();
/*
1
/ \
2 3
/ \ \
4 5 11
/ \ / \
6 7 8 9
/ \
-2 10
/ \
-1 14
/
-3
-----------------------
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(14);
tree.root->left->left->right->left = new TreeNode(-2);
tree.root->left->left->right->left->left = new TreeNode(-1);
tree.root->left->left->right->left->left->left = new TreeNode(-3);
tree.sumTopView();
return 0;
}
Output
Level order Top view of binary tree
1 2 3 4 11 6 14 -3
Sum of nodes : 38
// Include namespace system
using System;
/*
C# Program
Sum of nodes in top view of binary tree
*/
// 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;
}
// Sum of nodes in top view
public void sumTopView()
{
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 sum = this.root.data;
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;
// Add the result top view node
sum += node.left.data;
Console.Write(" " + node.left.data);
}
q.enqueue(node.left, distance - 1);
}
if (node.right != null)
{
if (max < distance + 1)
{
max = distance + 1;
// Add the result top view node
sum += node.right.data;
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 Sum of nodes : " + sum + " \n");
}
}
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
1
/ \
2 3
/ \ \
4 5 11
/ \ / \
6 7 8 9
/ \
-2 10
/ \
-1 14
/
-3
-----------------------
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(14);
tree.root.left.left.right.left = new TreeNode(-2);
tree.root.left.left.right.left.left = new TreeNode(-1);
tree.root.left.left.right.left.left.left = new TreeNode(-3);
tree.sumTopView();
}
}
Output
Level order Top view of binary tree
1 2 3 4 11 6 14 -3
Sum of nodes : 38
<?php
/*
Php Program
Sum of nodes in top view of binary tree
*/
// Binary Tree node
class TreeNode
{
public $data;
public $left;
public $right;
function __construct($data)
{
// Set node value
$this->data = $data;
$this->left = null;
$this->right = null;
}
}
// Queue Node
class QueueNode
{
public $element;
public $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;
}
// Sum of nodes in top view
public function sumTopView()
{
if ($this->root == null)
{
return;
}
else
{
$q = new MyQueue();
// min and max decide boundary of top view
$min = 0;
$max = 0;
$sum = $this->root->data;
$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;
// Add the result top view node
$sum += $node->left->data;
echo " ". $node->left->data;
}
$q->enqueue($node->left, $distance - 1);
}
if ($node->right != null)
{
if ($max < $distance + 1)
{
$max = $distance + 1;
// Add the result top view node
$sum += $node->right->data;
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 Sum of nodes : ". $sum ." \n";
}
}
}
function main()
{
$tree = new BinaryTree();
/*
1
/ \
2 3
/ \ \
4 5 11
/ \ / \
6 7 8 9
/ \
-2 10
/ \
-1 14
/
-3
-----------------------
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(14);
$tree->root->left->left->right->left = new TreeNode(-2);
$tree->root->left->left->right->left->left = new TreeNode(-1);
$tree->root->left->left->right->left->left->left = new TreeNode(-3);
$tree->sumTopView();
}
main();
Output
Level order Top view of binary tree
1 2 3 4 11 6 14 -3
Sum of nodes : 38
/*
Node Js Program
Sum of nodes in top view of binary tree
*/
// Binary Tree node
class TreeNode
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Queue Node
class QueueNode
{
constructor(element, 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;
}
// Sum of nodes in top view
sumTopView()
{
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 sum = this.root.data;
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;
// Add the result top view node
sum += node.left.data;
process.stdout.write(" " + node.left.data);
}
q.enqueue(node.left, distance - 1);
}
if (node.right != null)
{
if (max < distance + 1)
{
max = distance + 1;
// Add the result top view node
sum += node.right.data;
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 Sum of nodes : " + sum + " \n");
}
}
}
function main()
{
var tree = new BinaryTree();
/*
1
/ \
2 3
/ \ \
4 5 11
/ \ / \
6 7 8 9
/ \
-2 10
/ \
-1 14
/
-3
-----------------------
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(14);
tree.root.left.left.right.left = new TreeNode(-2);
tree.root.left.left.right.left.left = new TreeNode(-1);
tree.root.left.left.right.left.left.left = new TreeNode(-3);
tree.sumTopView();
}
main();
Output
Level order Top view of binary tree
1 2 3 4 11 6 14 -3
Sum of nodes : 38
# Python 3 Program
# Sum of nodes in top view of binary tree
# Binary Tree node
class TreeNode :
def __init__(self, data) :
# Set node value
self.data = data
self.left = None
self.right = None
# Queue Node
class QueueNode :
def __init__(self, element, 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
# Sum of nodes in top view
def sumTopView(self) :
if (self.root == None) :
return
else :
q = MyQueue()
# min and max decide boundary of top view
min = 0
max = 0
sum = self.root.data
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
# Add the result top view node
sum += node.left.data
print(" ", node.left.data, end = "")
q.enqueue(node.left, distance - 1)
if (node.right != None) :
if (max < distance + 1) :
max = distance + 1
# Add the result top view node
sum += node.right.data
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("\n Sum of nodes : ", sum ," ")
def main() :
tree = BinaryTree()
#
# 1
# / \
# 2 3
# / \ \
# 4 5 11
# / \ / \
# 6 7 8 9
# / \
# -2 10
# / \
# -1 14
# /
# -3
# -----------------------
# 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(14)
tree.root.left.left.right.left = TreeNode(-2)
tree.root.left.left.right.left.left = TreeNode(-1)
tree.root.left.left.right.left.left.left = TreeNode(-3)
tree.sumTopView()
if __name__ == "__main__": main()
Output
Level order Top view of binary tree
1 2 3 4 11 6 14 -3
Sum of nodes : 38
# Ruby Program
# Sum of nodes in top view of binary tree
# Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(data)
# Set node value
self.data = data
self.left = nil
self.right = nil
end
end
# Queue Node
class QueueNode
# Define the accessor and reader of class QueueNode
attr_reader :element, :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
# Sum of nodes in top view
def sumTopView()
if (self.root == nil)
return
else
q = MyQueue.new()
# min and max decide boundary of top view
min = 0
max = 0
sum = self.root.data
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
# Add the result top view node
sum += node.left.data
print(" ", node.left.data)
end
q.enqueue(node.left, distance - 1)
end
if (node.right != nil)
if (max < distance + 1)
max = distance + 1
# Add the result top view node
sum += node.right.data
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 Sum of nodes : ", sum ," \n")
end
end
end
def main()
tree = BinaryTree.new()
#
# 1
# / \
# 2 3
# / \ \
# 4 5 11
# / \ / \
# 6 7 8 9
# / \
# -2 10
# / \
# -1 14
# /
# -3
# -----------------------
# 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(14)
tree.root.left.left.right.left = TreeNode.new(-2)
tree.root.left.left.right.left.left = TreeNode.new(-1)
tree.root.left.left.right.left.left.left = TreeNode.new(-3)
tree.sumTopView()
end
main()
Output
Level order Top view of binary tree
1 2 3 4 11 6 14 -3
Sum of nodes : 38
/*
Scala Program
Sum of nodes in top view of binary tree
*/
// Binary Tree node
class TreeNode(var data: Int , var left: TreeNode , var right: TreeNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
// Queue Node
class QueueNode(var element: TreeNode , var 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);
}
// Sum of nodes in top view
def sumTopView(): 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 sum: Int = this.root.data;
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;
// Add the result top view node
sum += node.left.data;
print(" " + node.left.data);
}
q.enqueue(node.left, distance - 1);
}
if (node.right != null)
{
if (max < distance + 1)
{
max = distance + 1;
// Add the result top view node
sum += node.right.data;
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 Sum of nodes : " + sum + " \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinaryTree = new BinaryTree();
/*
1
/ \
2 3
/ \ \
4 5 11
/ \ / \
6 7 8 9
/ \
-2 10
/ \
-1 14
/
-3
-----------------------
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(14);
tree.root.left.left.right.left = new TreeNode(-2);
tree.root.left.left.right.left.left = new TreeNode(-1);
tree.root.left.left.right.left.left.left = new TreeNode(-3);
tree.sumTopView();
}
}
Output
Level order Top view of binary tree
1 2 3 4 11 6 14 -3
Sum of nodes : 38
/*
Swift 4 Program
Sum of nodes in top view of binary tree
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
// Queue Node
class QueueNode
{
var element: TreeNode? ;
var 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;
}
// Sum of nodes in top view
func sumTopView()
{
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 sum: Int = self.root!.data;
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;
// Add the result top view node
sum += node!.left!.data;
print(" ", node!.left!.data, terminator: "");
}
q.enqueue(node!.left, distance - 1);
}
if (node!.right != nil)
{
if (max < distance + 1)
{
max = distance + 1;
// Add the result top view node
sum += node!.right!.data;
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("\n Sum of nodes : ", sum ," ");
}
}
}
func main()
{
let tree: BinaryTree = BinaryTree();
/*
1
/ \
2 3
/ \ \
4 5 11
/ \ / \
6 7 8 9
/ \
-2 10
/ \
-1 14
/
-3
-----------------------
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(14);
tree.root!.left!.left!.right!.left = TreeNode(-2);
tree.root!.left!.left!.right!.left!.left = TreeNode(-1);
tree.root!.left!.left!.right!.left!.left!.left = TreeNode(-3);
tree.sumTopView();
}
main();
Output
Level order Top view of binary tree
1 2 3 4 11 6 14 -3
Sum of nodes : 38
/*
Kotlin Program
Sum of nodes in top view of binary tree
*/
// 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;
}
// Sum of nodes in top view
fun sumTopView(): 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 sum: Int = this.root!!.data;
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;
// Add the result top view node
sum += node.left!!.data;
print(" " + node.left!!.data);
}
q.enqueue(node.left, distance - 1);
}
if (node.right != null)
{
if (max < distance + 1)
{
max = distance + 1;
// Add the result top view node
sum += node.right!!.data;
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 Sum of nodes : " + sum + " \n");
}
}
}
fun main(args: Array < String > ): Unit
{
var tree: BinaryTree = BinaryTree();
/*
1
/ \
2 3
/ \ \
4 5 11
/ \ / \
6 7 8 9
/ \
-2 10
/ \
-1 14
/
-3
-----------------------
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(14);
tree.root?.left?.left?.right?.left = TreeNode(-2);
tree.root?.left?.left?.right?.left?.left = TreeNode(-1);
tree.root?.left?.left?.right?.left?.left?.left = TreeNode(-3);
tree.sumTopView();
}
Output
Level order Top view of binary tree
1 2 3 4 11 6 14 -3
Sum of nodes : 38
Resultant Output Explanation
Given the example binary tree, the top view is [1, 2, 3, 4, 11, 6, 14, -3]. The sum of these nodes is 38.
Time Complexity
The time complexity of this approach is O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once during the level order traversal. The insertion and lookup operations in the hash table take constant time.
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