Given a binary tree, the task is to print the sum of nodes in the bottom view of the given Binary Tree. The bottom view of a binary tree is the set of nodes visible when the tree is viewed from the bottom.
Examples:
Input :
1
/ \
2 3
/ \ \
4 5 6
Output : 20
Input :
1
/ \
2 3
\
4
\
5
\
6
Output : 17
Approach: The idea is to use a queue.
- Put tree nodes in a queue for the level order traversal
- Start with the horizontal distance(hd) 0 of the root node, keep on adding left child to queue along with the horizontal distance as hd-1 and right child as hd+1.
- Use a map to store the hd value(as key) and the last node(as pair) having the corresponding hd value.
- Every time, we encounter a new horizontal distance or an existing horizontal distance put the node data for the horizontal distance as key. For the first time it will add to the map, next time it will replace the value. This will make sure that the bottom-most element for that horizontal distance is present in the map.
- Finally, traverse the map and calculate the sum of all the elements.
Below is the implementation of the above approach:
C++
// C++ implementation of the above 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 bottom view of binary treeint SumOfBottomView(Node* root){ if (root == NULL) return 0; queue<Node*> q; unordered_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()) { Node* temp = q.front(); q.pop(); hd = temp->hd; // Put the dequeued tree node to Map // having key as horizontal distance. Every // time we find a node having same horizontal // distance we need to replace the data in // the map. m[hd] = temp->data; if (temp->left) { temp->left->hd = hd - 1; q.push(temp->left); } if (temp->right) { temp->right->hd = hd + 1; q.push(temp->right); } } unordered_map<int, int>::iterator itr; // Sum up all the nodes in bottom view of the tree for (itr = m.begin(); itr != m.end(); itr++) sum += itr->second; return sum;}// Driver Codeint main(){ Node* root = newNode(20); root->left = newNode(8); root->right = newNode(22); root->left->left = newNode(5); root->left->right = newNode(3); root->right->left = newNode(4); root->right->right = newNode(25); root->left->right->left = newNode(10); root->left->right->right = newNode(14); cout << SumOfBottomView(root); return 0;} |
Java
// Java implementation of // the above approachimport java.util.*;class GFG{ // Structure of binary treepublic static 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.data = key; node.left = null; node.right = null; return node;} // Function that returns the sum of// nodes in bottom view of binary treestatic int SumOfBottomView(Node root){ if (root == null) return 0; Queue<Node> q = new LinkedList<>(); HashMap<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) { Node temp = q.poll(); hd = temp.hd; // Put the dequeued tree node // to Map having key as horizontal // distance. Every time we find a // node having same horizontal distance // we need to replace the data in // the map. m.put(hd, temp.data); if (temp.left != null) { temp.left.hd = hd - 1; q.add(temp.left); } if (temp.right != null) { temp.right.hd = hd + 1; q.add(temp.right); } } // Sum up all the nodes in // bottom view of the tree for(int value : m.values()) { sum += value; } return sum;} // Driver code public static void main(String[] args) { Node root = newNode(20); root.left = newNode(8); root.right = newNode(22); root.left.left = newNode(5); root.left.right = newNode(3); root.right.left = newNode(4); root.right.right = newNode(25); root.left.right.left = newNode(10); root.left.right.right = newNode(14); System.out.println(SumOfBottomView(root));}}// This code is contributed by pratham76 |
Python3
# Python3 implementation of the above approach class Node: def __init__(self, data): self.data = data self.left = None self.right = None self.hd = None# Function that returns the Sum of # nodes in bottom view of binary tree def SumOfBottomView(root): if root == None: return 0 q = [] m = {} hd, Sum = 0, 0 root.hd = hd # Push node and horizontal # distance to queue q.append(root) while len(q) > 0: temp = q.pop(0) hd = temp.hd # Put the dequeued tree node to Map # having key as horizontal distance. # Every time we find a node having # same horizontal distance we need # to replace the data in the map. m[hd] = temp.data if temp.left != None: temp.left.hd = hd - 1 q.append(temp.left) if temp.right != None: temp.right.hd = hd + 1 q.append(temp.right) # Sum up all the nodes in bottom # view of the tree for itr in m: Sum += m[itr] return Sum# Driver Code if __name__ == "__main__": root = Node(20) root.left = Node(8) root.right = Node(22) root.left.left = Node(5) root.left.right = Node(3) root.right.left = Node(4) root.right.right = Node(25) root.left.right.left = Node(10) root.left.right.right = Node(14) print(SumOfBottomView(root)) # This code is contributed by Rituraj Jain |
C#
// C# implementation of // the above approachusing System;using System.Collections; 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.data = key; node.left = null; node.right = null; return node;} // Function that returns the sum of// nodes in bottom view of binary treestatic int SumOfBottomView(Node root){ if (root == null) return 0; Queue q = new Queue(); 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) { Node temp = (Node)q.Peek(); q.Dequeue(); hd = temp.hd; // Put the dequeued tree node // to Map having key as horizontal // distance. Every time we find a // node having same horizontal distance // we need to replace the data in // the map. m[hd] = temp.data; if (temp.left != null) { temp.left.hd = hd - 1; q.Enqueue(temp.left); } if (temp.right != null) { temp.right.hd = hd + 1; q.Enqueue(temp.right); } } // Sum up all the nodes in // bottom view of the tree foreach(KeyValuePair<int, int> itr in m) { sum += itr.Value; } return sum;} // Driver code public static void Main(string[] args) { Node root = newNode(20); root.left = newNode(8); root.right = newNode(22); root.left.left = newNode(5); root.left.right = newNode(3); root.right.left = newNode(4); root.right.right = newNode(25); root.left.right.left = newNode(10); root.left.right.right = newNode(14); Console.Write(SumOfBottomView(root));}}// This code is contributed by rutvik_56 |
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 bottom view of binary tree function SumOfBottomView(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) { let temp = q[0]; q.shift(); hd = temp.hd; // Put the dequeued tree node // to Map having key as horizontal // distance. Every time we find a // node having same horizontal distance // we need to replace the data in // the map. m.set(hd, temp.data); if (temp.left != null) { temp.left.hd = hd - 1; q.push(temp.left); } if (temp.right != null) { temp.right.hd = hd + 1; q.push(temp.right); } } // Sum up all the nodes in // bottom view of the tree m.forEach((value,key)=>{ sum += value; }) return sum; } let root = newNode(20); root.left = newNode(8); root.right = newNode(22); root.left.left = newNode(5); root.left.right = newNode(3); root.right.left = newNode(4); root.right.right = newNode(25); root.left.right.left = newNode(10); root.left.right.right = newNode(14); document.write(SumOfBottomView(root));</script> |
Output
58
Time Complexity: O(N), where N is the total number of nodes in the binary tree.
Auxiliary Space: O(N)
Another Approach(Using Depth First Search):
Create a map where the key is the horizontal distance and the value is a pair(a, b) where a is the value of the node and b is the height of the node. Perform a pre-order traversal of the tree. If the current node at a horizontal distance of h is the first we’ve seen, insert it into the map. Otherwise, compare the node with the existing one in map and if the height of the new node is greater, update the Map.
Follow the below steps to solve the above problem:
1) Recursively apply Depth first search on the Tree starting from root node and keep a track of height curr and horizontal distance as hd of the current node with respect to root node as root node’s height is 0.
2) If there’s no node as value for horizontal distance hd in map then set map[hd] = make_pair(root -> data, curr). Else store the pair value of mp[hd] in p. Then If p.second <= curr then set m[hd].second = curr and m[hd].first = root -> data
3) Call depth first search for left node of root node with height curr + 1 and horizontal distance as hd – 1 and right node of root node with height curr + 1 and horizontal distance as hd + 1
4) Base case would be to return when root is NULL.
Below is the implementation of above approach:
C++
// C++ Program to print the sum of nodes in Bottom View of Binary Tree#include <bits/stdc++.h>using namespace std;// Tree node classstruct Node{ int data; int hd; Node *left; Node* right;};// Function to create a new nodeNode* newNode(int key){ Node* node = new Node(); node->left = node->right = NULL; node->data = key; return node;}void SumOfBottomViewUtil(Node * root, int curr, int hd, map <int, pair <int, int>> & m){ // Base case if (root == NULL) return; // If node for a particular horizontal distance // is not present, add to the map. if (m.find(hd) == m.end()) m[hd] = make_pair(root -> data, curr); // Compare height for already present node at similar horizontal distance else{ pair < int, int > p = m[hd]; if (p.second <= curr){ m[hd].second = curr; m[hd].first = root -> data; } } // Recur for left subtree SumOfBottomViewUtil(root -> left, curr + 1, hd - 1, m); // Recur for right subtree SumOfBottomViewUtil(root -> right, curr + 1, hd + 1, m);}int SumOfBottomView(Node * root){ // Map to store Horizontal Distance, Height and Data. map < int, pair < int, int > > m; SumOfBottomViewUtil(root, 0, 0, m); // Prints the values stored by SumOfBottomViewUtil() map < int, pair < int, int > > ::iterator it; int sum = 0; for (it = m.begin(); it != m.end(); ++it){ pair < int, int > p = it -> second; sum += p.first; } return sum;}// Main Functionint main(){ Node* root = newNode(20); root->left = newNode(8); root->right = newNode(22); root->left->left = newNode(5); root->left->right = newNode(3); root->right->left = newNode(4); root->right->right = newNode(25); root->left->right->left = newNode(10); root->left->right->right = newNode(14); cout<<SumOfBottomView(root); return 0;}// THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002) |
Output
58
Time Complexity: O(N * logN), where N is the number of nodes in 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!
