DSA-skill-coding-ninjas/Maximum Sum BST at main · ajaykumar2pp/DSA-skill-coding-ninjas · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
code in  java **********************************************

public class Solution {

    static int subTreeSum(BinaryTreeNode<Integer> curNode) {

        if (curNode == null)
        {
            return 0;
        }

        int curSum = curNode.data;

        curSum += subTreeSum(curNode.left);

        curSum += subTreeSum(curNode.right);

        return curSum;
    }

    static int isBST(BinaryTreeNode<Integer> curNode, int low, int high) {

        if (curNode == null)
        {
            return 1;
        }


        if (curNode.data < low || curNode.data > high)
        {
            return 0;
        }

                                   // Check right child
        if(isBST(curNode.left, low, curNode.data - 1) == 1&&isBST(curNode.right, curNode.data + 1, high)==1)
        {
            return 1;
        }

        return 0;

    }

    static void traverseTree(BinaryTreeNode<Integer> curNode, int[] ans) {

        if (isBST(curNode, Integer.MIN_VALUE, Integer.MAX_VALUE)==1) {

            int maxSum = subTreeSum(curNode);

            ans[0] = Math.max(ans[0], maxSum);
        }

        if (curNode.left != null)
        {
            traverseTree(curNode.left, ans);
        }

        if (curNode.right != null)
            traverseTree(curNode.right, ans);
    }

    static int maxSumBST(BinaryTreeNode<Integer> root) {

        int[] ans = { 0 };

         traverseTree(root, ans);

        return ans[0];
    }

}