fork download 
  1. function getTreeDepth(tree) {
  2. 	if (tree.length == 0 || tree.length == 1) {
  3. 		return tree.length;
  4. 	}
  5.  
  6. 	depth = 1;
  7. 	increment = 1;
  8. 	maxIndex = 1;
  9.  
  10. 	while(maxIndex < tree.length) {
  11. 		increment ++;
  12. 		maxIndex += increment;
  13. 		depth ++;
  14. 	}
  15.  
  16. 	return depth;
  17. }
  18.  
  19. function maxSum(tree, treeDepth, rootIndex, rootDepth) {
  20. 	if (rootDepth == treeDepth) {
  21. 		return tree[rootIndex];
  22. 	}
  23.  
  24. 	// Recursive step:
  25. 	var leftSubTreeSum = maxSum(tree, treeDepth, rootIndex + rootDepth, rootDepth + 1);
  26. 	var rightSubTreeSum = maxSum(tree, treeDepth, rootIndex + rootDepth + 1, rootDepth + 1);
  27. 	var maxSubTreeSum;
  28.  
  29. 	if (rightSubTreeSum > leftSubTreeSum) {
  30. 		maxSubTreeSum = rightSubTreeSum;
  31. 	} else {
  32. 		maxSubTreeSum = leftSubTreeSum;
  33. 	}
  34.  
  35. 	return tree[rootIndex] + maxSubTreeSum;
  36. }
  37.  
  38. //NOTE: children of tree[n] are tree[n + depthOfN] and tree[n + depthOfN + 1]
  39. var tree = [75, 95, 64, 17, 47, 82, 18, 35, 87, 10, 20, 04, 82, 47, 65, 19, 01, 23, 75, 03, 34, 88, 02, 77, 73, 07, 63, 67, 99, 65, 04, 28, 06, 16, 70, 92, 41, 41, 26, 56, 83, 40, 80, 70, 33, 41, 48, 72, 33, 47, 32, 37, 16, 94, 29, 53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14, 70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57, 91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48, 63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31, 04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23];
  40. var treeDepth = getTreeDepth(tree);
  41. document.writeln("Max sum of traversal = " + maxSum(tree, treeDepth, 0, 1));
Runtime error #stdin #stdout 0.31s 213184KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/mUZ74
language:
JavaScript (rhino 1.7.9)
created:
14 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!