fork(1) download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone{
  9. 	public static class Node{
  10. 		Node left, right;
  11. 		int data;
  12. 		Node(int data, Node left, Node right){
  13. 			this.data = data;
  14. 			this.left = left;
  15. 			this.right = right;
  16. 		}
  17. 		Node(int data){
  18. 			this(data, null, null);
  19. 		}
  20. 	}
  21.  
  22. 	public static int depthSum(Node root) {
  23. 	    Queue<Node> q = new LinkedList<Node>();
  24. 	    q.add(root);
  25. 	    int siblings = 1;
  26. 	    int totalSum = 0, levelSum = 0, level = 0;
  27.  
  28. 	    while(!q.isEmpty()) {
  29. 	        Node n = q.remove();
  30. 	        levelSum += n.data;
  31.  
  32. 	        if(n.left != null)                     // Add left child 
  33. 	            q.add(n.left);
  34.  
  35. 	        if(n.right != null)                    // Add right child
  36. 	            q.add(n.right);
  37.  
  38. 	        if(--siblings == 0){                   // All siblings have been probed
  39. 	            siblings = q.size();               // Children become siblings
  40. 	            totalSum += levelSum * level;      // increment totalSum
  41. 	            level++;                           // increment level
  42. 	            levelSum = 0;                      // reinitialize levelSum
  43. 	        }
  44. 	    }
  45.  
  46. 	    return totalSum;
  47. 	}
  48.  
  49. 	public static void main (String[] args) throws java.lang.Exception{
  50. 		Node root = new Node(1,
  51. 						new Node(2,
  52. 							null,
  53. 							new Node(5)
  54. 						), 
  55. 						new Node(3,
  56. 							new Node(6),
  57. 							new Node(7)
  58. 						)
  59. 					);
  60. 		System.out.println("Expected Answer : (1)*0 + (2 + 3)*1 + (5 + 6 + 7)*2 = 41");
  61. 		System.out.println("Actual Answer   : " + depthSum(root));
  62. 	}
  63. }
Success #stdin #stdout 0.08s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Expected Answer : (1)*0 + (2 + 3)*1 + (5 + 6 + 7)*2 = 41
Actual Answer   : 41
https://ideone.com/TJsxSJ
language:
Java (HotSpot 12)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!