Max Path Sum in BST

Given a binary search tree, find the maximum path sum where the path may start and end at any node in the tree. A path is defined as a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. The maximum path sum is the largest sum of values of the nodes in any such path. Input format: The first line contains the integer N, the number of nodes in the BST. The next N lines each contain an integer value, where the first value is the root, followed by its children in level order. Output format: Print a single integer which is the maximum path sum. Example: Input: 5 10 5 15 3 7 Output: 25