Skip to content

Instantly share code, notes, and snippets.

@ramannanda9
Created July 31, 2017 19:58
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ramannanda9/601d77ffa9b85eb4ecaf95579e43851b to your computer and use it in GitHub Desktop.
Save ramannanda9/601d77ffa9b85eb4ecaf95579e43851b to your computer and use it in GitHub Desktop.
Get maximum independent branch sum
public class MaxSumInTree{
int left(int i) {
return (2 * i + 1);
}
int right(int i) {
return (2 * i + 2);
}
long findMax(int n, String tree) {
String[] data = tree.split("\\s+");
Arrays.stream(data).forEach(System.out::println);
return findMaxRecursive(data, 0, data[0]);
}
long findMaxRecursive(String[] data, int i, String parent) {
if (parent.equals("#")) {
return 0;
}
if (left(i) >= data.length) {
return Long.parseLong(parent);
}
long a = findMaxRecursive(data, left(i), data[i]);
long b = findMaxRecursive(data, right(i), data[i]);
if (i == 0) {
return a + b;
} else {
return Math.max(a, b);
}
}
public static void main(String[] args) {
String data = "3 4 5 1 3 # 1";
System.out.println(" The max independent sum in binary tree is " + new MaxSumInTree().findMax(6, data));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment