using System;
class BinarySearchTree
{
private int max = int.MinValue;
Node root;
public class Node
{
public int data;
public Node right, left;
public Node(int d)
{
data = d;
right = null;
left = null;
}

} public int maxPathSum(Node root) { int rd = dfs(root); return rd > max ? rd : max; } private int dfs(Node root) { if (root.left == null && root.right == null) { return root.data; } if (root.left == null && root.right != null) { int roPathMax = dfs(root.right); max = roPathMax > max ? roPathMax : max; return Math.Max(root.data, roPathMax + root.data); } if (root.right == null && root.left != null) { int loPathMax = dfs(root.left); max = loPathMax > max ? loPathMax : max; return Math.Max(root.data, loPathMax + root.data); } int lPathMax = dfs(root.left); int rPathMax = dfs(root.right); int closePathMax = lPathMax + rPathMax + root.data; int innerMax = Math.Max(closePathMax, Math.Max(lPathMax, rPathMax)); max = innerMax > max ? innerMax : max; return Math.Max(root.data, Math.Max(lPathMax + root.data, rPathMax + root.data)); } static void Main() { BinarySearchTree BST = new BinarySearchTree(); BST.Insert(0); BST.Insert(5); BST.Insert(-4); BST.Insert(-2); BST.Insert(7); BST.Insert(8); BST.Insert(6); //find max sum and the subtree path Console.WriteLine("Max pathSum of the given binary tree is " + BST.maxPathSum(BST.root)); Console.ReadKey(); } public void Insert(int New) { Node N = new Node(New); if(root==null) { root = N; } else { Node current = root; Node parent; while(true) { parent = current; if(current.data > N.data) { current = current.left; if(current==null) { parent.left = N; break; } } else { current = current.right; if(current ==null) { parent.right = N; break; } } } } }

}