Sum of all vertical levels of a Binary Tree
Given a binary tree consisting of either 1 or 0 as its node values, the task is to find the sum of all vertical levels of the Binary Tree, considering each value to be a binary representation.
Examples:
Input: 1
/ \
1 0
/ \ / \
1 0 1 0
Output: 7
Explanation:
Taking vertical levels from left to right:
For vertical level 1: (1)2 = 1
For vertical level 2: (1)2 = 1
For vertical level 3: (101)2 = 5
For vertical level 4: (0)2 = 0
For vertical level 5: (0)2 = 0
Total sum = 1+1+5+0+0 = 7Input: 0
/ \
1 0
/ \ \
1 1 0
/ \ \ / \
1 1 1 0 0
Output: 8
Explanation:
Taking vertical levels from left to right:
For vertical level 1: (1)2 = 1
For vertical level 2: (1)2 = 1
For vertical level 3: (11)2 = 3
For vertical level 4: (01)2 = 1
For vertical level 5: (010)2 = 2
For vertical level 6: (0)2 = 0
For vertical level 7: (0)2 = 0
Total sum = 1+1+3+1+2+0+0 = 8
Approach: Follow the steps below to solve the problem:
- Perform a tree traversal while keeping track of the horizontal and vertical distance from the root node
- Store the node value corresponding to its horizontal distance in a Hashmap.
- Initialize a variable, say ans, to store the required result.
- Create a Hashmap, say M, to store horizontal distance as key and an array of pairs {node value, distance of the node from the root}.
- The height for each node is also stored as the vertical level is needed to be in a sorted order (from top to bottom), to get the correct decimal value of its binary representation.
- Perform preorder tree traversal and also pass vertical height and horizontal distances as parameters.
- If the root is not NULL, perform the following operations:
- Append the pair {node value, vertical height in the horizontal distance} in M.
- Traverse the left subtree, decrementing the horizontal distance by 1.
- Traverse the right subtree, incrementing the horizontal distance by 1.
- Increment the vertical height by 1 for both of the recursive calls.
- If the root is not NULL, perform the following operations:
- Now, traverse the Hashmap, say M and for every key, perform the following steps:
- Sort the values on the basis of their height from the root node and then convert the binary number obtained to its decimal equivalent and store it in a variable, say B.
- Add the value of B to ans.
- Print the value of ans
Below is the implementation of the above approach:
C++
// C++ program for super ugly number #include<bits/stdc++.h> using namespace std; // Structure of a Tree node struct TreeNode { int val = 0; TreeNode *left; TreeNode *right; TreeNode( int x) { val = x; left = right = NULL; } }; // Function to convert // binary number to decimal int getDecimal(vector<pair< int , int > > arr) { // Sort the array on // the basis of the // first index i.e, height sort(arr.begin(), arr.end()); // Store the required // decimal equivalent // of the number int ans = 0; // Traverse the array for ( int i = 0; i < arr.size(); i++) { ans <<= 1; ans |= arr[i].second; } // Return the answer return ans; } // Function to traverse the tree void Traverse(TreeNode *root, int hd, int ht, map< int , vector<pair< int , int > > > &mp) { // If root is NULL, return if (!root) return ; mp[hd].push_back({ht, root->val}); // Make recursive calls to the left and // right subtree Traverse(root->left, hd - 1, ht + 1, mp); Traverse(root->right, hd + 1, ht + 1, mp); } // Function to calculate // sum of vertical levels // of a Binary Tree void getSum(TreeNode *root) { // Dictionary to store the // vertical level as key and // its corresponding // binary number as value map< int ,vector<pair< int , int > > > mp; // Function Call to perform traverse the tree Traverse(root, 0, 0, mp); // Store the required answer int ans = 0; // Get decimal values for each vertical level // and add it to ans for ( auto i:mp) ans += getDecimal(i.second); // Print the answer cout<<(ans); } /* Driver program to test above functions */ int main() { TreeNode *root = new TreeNode(1); root->left = new TreeNode(1); root->right = new TreeNode(0); root->left->left = new TreeNode(1); root->left->right = new TreeNode(0); root->right->left = new TreeNode(1); root->right->right = new TreeNode(0); // Function call to get the // sum of vertical level // of the tree getSum(root); return 0; } // This code is contributed by mohit kumar 29. |
Java
// Java program for super ugly number import java.io.*; import java.util.*; // Structure of a Tree node class TreeNode { int val = 0 ; TreeNode left; TreeNode right; TreeNode( int x) { val = x; left = right = null ; } } class GFG { static Map<Integer, ArrayList<ArrayList<Integer>>> mp = new HashMap<Integer, ArrayList<ArrayList<Integer>>>(); // Function to convert // binary number to decimal static int getDecimal(ArrayList<ArrayList<Integer> > arr) { // Sort the array on // the basis of the // first index i.e, height Collections.sort(arr, new Comparator<ArrayList<Integer>>() { @Override public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) { return o1.get( 0 ).compareTo(o2.get( 0 )); } }); // Store the required // decimal equivalent // of the number int ans = 0 ; // Traverse the array for ( int i = 0 ; i < arr.size(); i++) { ans <<= 1 ; ans |= arr.get(i).get( 1 ); } // Return the answer return ans; } // Function to traverse the tree static void Traverse(TreeNode root, int hd, int ht) { // If root is NULL, return if (root == null ) return ; if (mp.containsKey(hd)) { mp.get(hd).add( new ArrayList<Integer>(Arrays.asList(ht, root.val))); } else { mp.put(hd, new ArrayList<ArrayList<Integer>>()); mp.get(hd).add( new ArrayList<Integer>(Arrays.asList(ht, root.val))); } // Make recursive calls to the left and // right subtree Traverse(root.left, hd - 1 , ht + 1 ); Traverse(root.right, hd + 1 , ht + 1 ); } // Function to calculate // sum of vertical levels // of a Binary Tree static void getSum(TreeNode root) { // Function Call to perform traverse the tree Traverse(root, 0 , 0 ); // Store the required answer int ans = 0 ; // Get decimal values for each vertical level // and add it to ans for (Integer key : mp.keySet()) { ans += getDecimal(mp.get(key)); } // Print the answer System.out.print(ans); } // Driver code public static void main (String[] args) { TreeNode root = new TreeNode( 1 ); root.left = new TreeNode( 1 ); root.right = new TreeNode( 0 ); root.left.left = new TreeNode( 1 ); root.left.right = new TreeNode( 0 ); root.right.left = new TreeNode( 1 ); root.right.right = new TreeNode( 0 ); // Function call to get the // sum of vertical level // of the tree getSum(root); } } // This code is contributed by avanitrachhadiya2155 |
Python3
# Python program # for the above approach # Structure of a Tree node class TreeNode: def __init__( self , val = '', left = None , right = None ): self .val = val self .left = left self .right = right # Function to convert # binary number to decimal def getDecimal(arr): # Sort the array on # the basis of the # first index i.e, height arr.sort() # Store the required # decimal equivalent # of the number ans = 0 # Traverse the array for i in range ( len (arr)): ans << = 1 ans | = arr[i][ 1 ] # Return the answer return ans # Function to calculate # sum of vertical levels # of a Binary Tree def getSum(root): # Dictionary to store the # vertical level as key and # its corresponding # binary number as value mp = {} # Function to traverse the tree def Traverse(root, hd, ht): # If root is NULL, return if not root: return # Store the value in the map if hd not in mp: mp[hd] = [[ht, root.val]] else : mp[hd].append([ht, root.val]) # Make recursive calls to the left and # right subtree Traverse(root.left, hd - 1 , ht + 1 ) Traverse(root.right, hd + 1 , ht + 1 ) # Function Call to perform traverse the tree Traverse(root, 0 , 0 ) # Store the required answer ans = 0 # Get decimal values for each vertical level # and add it to ans for i in mp: ans + = getDecimal(mp[i]) # Print the answer print (ans) # Driver Code # Given Tree root = TreeNode( 1 ) root.left = TreeNode( 1 ) root.right = TreeNode( 0 ) root.left.left = TreeNode( 1 ) root.left.right = TreeNode( 0 ) root.right.left = TreeNode( 1 ) root.right.right = TreeNode( 0 ) # Function call to get the # sum of vertical level # of the tree getSum(root) |
C#
// C# program for super ugly number using System; using System.Linq; using System.Collections.Generic; // Structure of a Tree node public class TreeNode { public int val = 0; public TreeNode left, right; public TreeNode( int x) { val = x; left = right = null ; } } public class GFG { static Dictionary< int ,List<List< int >>> mp = new Dictionary< int ,List<List< int >>>(); // Function to convert // binary number to decimal static int getDecimal(List<List< int > > arr) { // Sort the array on // the basis of the // first index i.e, height arr.OrderBy( l => l[0]); // Store the required // decimal equivalent // of the number int ans = 0; // Traverse the array for ( int i = 0; i < arr.Count; i++) { ans <<= 1; ans |= arr[i][1]; } // Return the answer return ans; } // Function to traverse the tree static void Traverse(TreeNode root, int hd, int ht) { // If root is NULL, return if (root == null ) return ; if (mp.ContainsKey(hd)) { mp[hd].Add( new List< int >(){ht, root.val}); } else { mp.Add(hd, new List<List< int >>()); mp[hd].Add( new List< int >(){ht, root.val}); } // Make recursive calls to the left and // right subtree Traverse(root.left, hd - 1, ht + 1); Traverse(root.right, hd + 1, ht + 1); } // Function to calculate // sum of vertical levels // of a Binary Tree static void getSum(TreeNode root) { // Function Call to perform traverse the tree Traverse(root, 0, 0); // Store the required answer int ans = 0; // Get decimal values for each vertical level // and add it to ans foreach ( int key in mp.Keys) { ans += getDecimal(mp[key]); } // Print the answer Console.Write(ans); } // Driver code static public void Main () { TreeNode root = new TreeNode(1); root.left = new TreeNode(1); root.right = new TreeNode(0); root.left.left = new TreeNode(1); root.left.right = new TreeNode(0); root.right.left = new TreeNode(1); root.right.right = new TreeNode(0); // Function call to get the // sum of vertical level // of the tree getSum(root); } } // This code is contributed by rag2127 |
Javascript
<script> // Javascript program for super ugly number // Structure of a Tree node class TreeNode { constructor(x) { this .val = x; this .left = this .right = null ; } } let mp = new Map(); // Function to convert // binary number to decimal function getDecimal(arr) { arr.sort( function (a,b){ return a[0]-b[0]}); // Store the required // decimal equivalent // of the number let ans = 0; // Traverse the array for (let i = 0; i < arr.length; i++) { ans <<= 1; ans |= arr[i][1]; } // Return the answer return ans; } // Function to traverse the tree function Traverse(root, hd, ht) { // If root is NULL, return if (root == null ) return ; if (mp.has(hd)) { mp.get(hd).push([ht, root.val]); } else { mp.set(hd,[]); mp.get(hd).push([ht, root.val]); } // Make recursive calls to the left and // right subtree Traverse(root.left, hd - 1, ht + 1); Traverse(root.right, hd + 1, ht + 1); } // Function to calculate // sum of vertical levels // of a Binary Tree function getSum(root) { // Function Call to perform traverse the tree Traverse(root, 0, 0); // Store the required answer let ans = 0; // Get decimal values for each vertical level // and add it to ans for (let [key, value] of mp.entries()) { ans += getDecimal(value); } // Print the answer document.write(ans); } // Driver code let root = new TreeNode(1); root.left = new TreeNode(1); root.right = new TreeNode(0); root.left.left = new TreeNode(1); root.left.right = new TreeNode(0); root.right.left = new TreeNode(1); root.right.right = new TreeNode(0); // Function call to get the // sum of vertical level // of the tree getSum(root); // This code is contributed by unknown2108 </script> |
7
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)
Contact Us