The question is, going from the value at the top to the bottom by choosing to go down the path of either left or right, what is the maximum sum among all possible paths?

## The Approach

## Thought Process

A node hold value as its data, has a left Node, and a right Node. An head/top Node can be initialized to represent the whole triangular set of values as seen in the main() below.

The maximum sum among all paths starting from a given node is the max of its value plus either the maximum sum among all paths starting from either its left node or right node.

## Code Snippet

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Node{

public int data;

public Node left;

public Node right;

public Node(int value){

data = value;

}

public static int maxPathSum(Node n){

if (n == null){ // ending condition

return 0;

}

return Math.max(n.data + maxPathSum(n.left), n.data + maxPathSum(n.right));

}

public static void main(String[] args){

Node head = new Node(5);

head.left = new Node(3);

head.right = new Node(7);

head.left.left = new Node(2);

head.left.right = new Node(9);

head.right.right = new Node(15);

head.left.left.left = new Node(99);

head.left.left.right = new Node(4);

head.left.right.right = new Node(2);

head.right.right.right = new Node(8);

System.out.print(Node.maxPathSum(head));

}

}

## The Performance

1 level -> 1 path

2 levels -> 2 paths

3 levels -> 4 paths

4 levels -> 8 paths

5 levels -> 16 paths

Therefore, the big O notation of the above recursive algorithm is the number of paths which is

**2^n**where n is the number of level of the triangular set of values.