Top view of a binary tree is the set of nodes visible when the tree is viewed from the top. Given a binary tree, the task is to print the sum of nodes in top view.
Examples:
Input:
1
/ \
2 3
/ \ \
4 5 6
Output: 16
Input:
1
/ \
2 3
\
4
\
5
\
6
Output: 12
Approach: The idea is to put nodes of same horizontal distance together. We do a level order traversal so that the topmost node at a horizontal node is visited before any other node of same horizontal distance below it and we keep summing up their values and store the result in variable sum. Hashing is used to check if a node at given horizontal distance is seen or not.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Structure of binary treestruct Node { Node* left; Node* right; int hd; int data;};// Function to create a new nodeNode* newNode(int key){ Node* node = new Node(); node->left = node->right = NULL; node->data = key; return node;}// Function that returns the sum of// nodes in top view of binary treeint SumOfTopView(Node* root){ if (root == NULL) return 0; queue<Node*> q; map<int, int> m; int hd = 0; root->hd = hd; int sum = 0; // Push node and horizontal distance to queue q.push(root); while (q.size()) { hd = root->hd; // Count function returns 1 if the container // contains an element whose key is equivalent // to hd, or returns zero otherwise. if (m.count(hd) == 0) { m[hd] = root->data; sum += m[hd]; } if (root->left) { root->left->hd = hd - 1; q.push(root->left); } if (root->right) { root->right->hd = hd + 1; q.push(root->right); } q.pop(); root = q.front(); } return sum;}// Driver codeint main(){ Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->right = newNode(4); root->left->right->right = newNode(5); root->left->right->right->right = newNode(6); cout << SumOfTopView(root); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class Sol{ // Structure of binary treestatic class Node { Node left; Node right; int hd; int data;};// Function to create a new nodestatic Node newNode(int key){ Node node = new Node(); node.left = node.right = null; node.data = key; return node;}// Function that returns the sum of// nodes in top view of binary treestatic int SumOfTopView(Node root){ if (root == null) return 0; Queue<Node> q = new LinkedList<Node>(); Map<Integer,Integer> m = new HashMap<Integer,Integer>(); int hd = 0; root.hd = hd; int sum = 0; // Push node and horizontal distance to queue q.add(root); while (q.size() > 0) { hd = root.hd; // Count function returns 1 if the container // contains an element whose key is equivalent // to hd, or returns zero otherwise. if (!m.containsKey(hd)) { m.put(hd, root.data); sum += m.get(hd); } if (root.left != null) { root.left.hd = hd - 1; q.add(root.left); } if (root.right != null) { root.right.hd = hd + 1; q.add(root.right); } q.remove(); if(q.size() > 0) root = q.peek(); } return sum;}// Driver codepublic static void main(String args[]){ Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.right = newNode(4); root.left.right.right = newNode(5); root.left.right.right.right = newNode(6); System.out.print(SumOfTopView(root));}}// This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approachfrom collections import defaultdictclass Node: def __init__(self, key): self.data = key self.hd = None self.left = None self.right = None# Function that returns the sum of# nodes in top view of binary treedef SumOfTopView(root): if root == None: return 0 q = [] m = defaultdict(lambda:0) hd, Sum = 0, 0 root.hd = hd # Push node and horizontal # distance to queue q.append(root) while len(q) > 0: hd = root.hd # Count function returns 1 if # the container contains an # element whose key is equivalent # to hd, or returns zero otherwise. if m[hd] == 0: m[hd] = root.data Sum += m[hd] if root.left != None: root.left.hd = hd - 1 q.append(root.left) if root.right != None: root.right.hd = hd + 1 q.append(root.right) q.pop(0) if len(q) > 0: root = q[0] return Sum# Driver codeif __name__ == "__main__": root = Node(1) root.left = Node(2) root.right = Node(3) root.left.right = Node(4) root.left.right.right = Node(5) root.left.right.right.right = Node(6) print(SumOfTopView(root))# This code is contributed by Rituraj Jain |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG{ // Structure of binary treepublic class Node { public Node left; public Node right; public int hd; public int data;};// Function to create a new nodestatic Node newNode(int key){ Node node = new Node(); node.left = node.right = null; node.data = key; return node;}// Function that returns the sum of// nodes in top view of binary treestatic int SumOfTopView(Node root){ if (root == null) return 0; Queue<Node> q = new Queue<Node>(); Dictionary<int, int> m = new Dictionary<int, int>(); int hd = 0; root.hd = hd; int sum = 0; // Push node and horizontal distance to queue q.Enqueue(root); while (q.Count > 0) { hd = root.hd; // Count function returns 1 if the container // contains an element whose key is equivalent // to hd, or returns zero otherwise. if (!m.ContainsKey(hd)) { m.Add(hd, root.data); sum += m[hd]; } if (root.left != null) { root.left.hd = hd - 1; q.Enqueue(root.left); } if (root.right != null) { root.right.hd = hd + 1; q.Enqueue(root.right); } q.Dequeue(); if(q.Count > 0) root = q.Peek(); } return sum;}// Driver codepublic static void Main(String []args){ Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.right = newNode(4); root.left.right.right = newNode(5); root.left.right.right.right = newNode(6); Console.Write(SumOfTopView(root));}}// This code is contributed by Princi Singh |
Javascript
<script> // JavaScript implementation of the approach // Structure of binary tree class Node { constructor(key) { this.left = null; this.right = null; this.data = key; this.hd; } } // Function to create a new node function newNode(key) { let node = new Node(key); return node; } // Function that returns the sum of // nodes in top view of binary tree function SumOfTopView(root) { if (root == null) return 0; let q = []; let m = new Map(); let hd = 0; root.hd = hd; let sum = 0; // Push node and horizontal distance to queue q.push(root); while (q.length > 0) { hd = root.hd; // Count function returns 1 if the container // contains an element whose key is equivalent // to hd, or returns zero otherwise. if (!m.has(hd)) { m.set(hd, root.data); sum += m.get(hd); } if (root.left != null) { root.left.hd = hd - 1; q.push(root.left); } if (root.right != null) { root.right.hd = hd + 1; q.push(root.right); } q.shift(); if(q.length > 0) root = q[0]; } return sum; } let root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.right = newNode(4); root.left.right.right = newNode(5); root.left.right.right.right = newNode(6); document.write(SumOfTopView(root)); </script> |
Output:
12
Time Complexity: O(N)
Auxiliary Space: O(N)
Approach:
To solve the problem follow the below idea:
Here we use the two variables, one for the vertical distance of the current node from the root and another for the depth of the current node from the root. We use the vertical distance for indexing. If one node with the same vertical distance comes again, we check if the depth of the new node is lower or higher with respect to the current node with the same vertical distance in the map. If the depth of the new node is lower, then we replace it.
Follow the below steps to solve the problem:
1) Create a map of the type <int, pair<int, int>> and two variables d and l to store horizontal and vertical distance from the root respectively
2) Call the function to return the SumOfTopView
3) If the root is equal to the null value then return from the function (Base case)
4) Check if this value of d is not present in the map, then set map[d] equal to {root->data, l}
5) Check if this value of d is already present and its vertical distance is greater than l, then set map[d] equal to {root->data, l}
6) Call this function recursively for (root->left, d-1, l+1, mp) and (root->right, d+1, l+1, mp)
7) return the sum of top view of the binary tree using the map
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Structure of binary treestruct Node { Node* left; Node* right; int data;};// function to create a new nodeNode* newNode(int data){ Node* temp = new Node(); temp->left = temp->right = NULL; temp->data = data; return temp;}// function to fill the mapvoid fillMap(Node* root, int d, int l, map<int, pair<int, int> >& m){ if (root == NULL) return; if (m.count(d) == 0) m[d] = make_pair(root->data, l); else if(m[d].second > l) m[d] = make_pair(root->data, l); fillMap(root->left, d - 1, l + 1, m); fillMap(root->right, d + 1, l + 1, m);}// function return the SumofTopView of// the given binary treeint SumOfTopView(Node* root){ // map to store the pair of node value and its level // with respect to the vertical distance from root. map<int, pair<int, int> > m; // Initializing map fillMap(root, 0, 0, m); int ans = 0; for(auto i : m){ ans += i.second.first; } return ans;}// Driver codeint main(){ Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->right = newNode(4); root->left->right->right = newNode(5); root->left->right->right->right = newNode(6); cout<<SumOfTopView(root); return 0;}// this code is contributed by Yash Agarwal(yashagarwal2852002) |
Java
import java.util.*;// structure of binary tree nodeclass Node { int data; Node left, right; Node(int data) { this.data = data; left = null; right = null; }}// pair classclass Pair { int first, second; Pair(int first, int second) { this.first = first; this.second = second; }}class Solution { // function to fill the map public void fillMap(Node root, int d, int l, Map<Integer, Pair> m) { if (root == null) return; if (m.get(d) == null) { m.put(d, new Pair(root.data, l)); } else if (m.get(d).second > 1) { m.put(d, new Pair(root.data, l)); } fillMap(root.left, d-1, l+1, m); fillMap(root.right, d+1, l+1, m); } // function returns the sumofTopView of the given binary tree public int sumOfTopView(Node root) { // map to store the pair of node value and its level // with respect to the vertical distance from root Map<Integer, Pair> m = new TreeMap<>(); // initializing map fillMap(root, 0, 0, m); int ans = 0; for(Integer x: m.keySet()) { ans += m.get(x).first; } return ans; } // driver program to test above functions public static void main(String[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.right = new Node(4); root.left.right.right = new Node(5); root.left.right.right.right = new Node(6); Solution s = new Solution(); System.out.println(s.sumOfTopView(root)); }} |
Python
# Python program for the above approach# structure of binary tree nodeclass Node: def __init__(self, data): self.data = data self.left = None self.right = None # pair classclass pair: def __init__(self, first, second): self.first = first self.second = second # function to create a new nodedef newNode(data): return Node(data)# function to fill the mapdef fillMap(root, d, l, m): if(root is None): return if(m.get(d) is None): m[d] = pair(root.data, l) elif(m.get(d).second > 1): m[d] = pair(root.data, l) fillMap(root.left, d-1, l+1, m) fillMap(root.right, d+1, l+1, m) # function returns the sumofTopView of# the given binary treedef SumOfTopView(root): # map to store the pair of node value and its level # with respect to the vertical distance from root m = {} # initializing map fillMap(root, 0, 0, m) ans = 0 for x in m: ans += m[x].first return ans# driver program to test above functionsroot = newNode(1)root.left = newNode(2)root.right = newNode(3)root.left.right = newNode(4)root.left.right.right = newNode(5)root.left.right.right.right = newNode(6)print(SumOfTopView(root)) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;using System.Collections;using System.Linq;// Structure of binary treeclass Node { public Node left; public Node right; public int data; public Node(int val){ data = val; left = null; right = null; }}class HelloWorld { // function to fill the map public static void fillMap(Node root, int d, int l, IDictionary<int, KeyValuePair<int,int> > m){ if (root == null) return; if (m.ContainsKey(d) == false) m.Add(new KeyValuePair<int, KeyValuePair<int,int>>(d, new KeyValuePair<int, int>(root.data, l))); else if(m[d].Value > 1){ m[d] = new KeyValuePair<int,int>(root.data, l); } fillMap(root.left, d - 1, l + 1, m); fillMap(root.right, d + 1, l + 1, m); } // function return the SumofTopView of // the given binary tree public static int SumOfTopView(Node root) { // map to store the pair of node value and its level // with respect to the vertical distance from root. IDictionary<int, KeyValuePair<int,int> > m = new Dictionary<int, KeyValuePair<int,int>>(); // Initializing map fillMap(root, 0, 0, m); int ans = 0; foreach(KeyValuePair<int, KeyValuePair<int,int>> i in m) { ans += i.Value.Key; // do something with entry.Value or entry.Key } return ans; } static void Main() { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.right = new Node(4); root.left.right.right = new Node(5); root.left.right.right.right = new Node(6); Console.WriteLine(SumOfTopView(root)); }}// The code is contributed by Nidhi goel. |
Javascript
// JavaScript program for the above approach// structure of binary tree nodeclass Node{ constructor(data){ this.data = data; this.left = null; this.right = null; }}// pair classclass pair{ constructor(first, second){ this.first = first; this.second = second; }}// function to create a new nodefunction newNode(data){ return new Node(data);}// functiont o fill the mapfunction fillMap(root, d, l, m){ if(root == null) return; if(m.has(d) == false) m.set(d, new pair(root.data, l)); else if(m.get(d).second > 1) m.set(d, new pair(root.data, l)); fillMap(root.left, d-1, l+1, m); fillMap(root.right, d+1, l+1, m);}// function return the SumOfTopView of // the given binary treefunction SumOfTopView(root){ // map to store the pair of node value and its level // with respect to the vertical distance from root let m = new Map(); // initializing map fillMap(root, 0, 0, m); let ans = 0; m.forEach(function(value, key){ ans += value.first; }) return ans;}// driver codelet root = newNode(1);root.left = newNode(2);root.right = newNode(3);root.left.right = newNode(4);root.left.right.right = newNode(5);root.left.right.right.right = newNode(6);document.write(SumOfTopView(root));// THIS CODE IS CONTRIBUTED BY KIRTI AGARWAL(KIRTIAGARWAL23121999) |
Output
12
Time complexity: O(N * log(N)), where N is the number of nodes in the given binary tree.
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
