maxsum of BSTs in BT

 public class MaxBSTSumInBT {

    public static class Node {
        int data;
        Node left, right;

        Node(int data) {
            this.data = data;
        }
    }

    public static class Info {
        int max;
        int min;
        boolean isBST;
        int sum;
        int currmax;

        Info(int m, int mi, boolean is, int s, int curr) {
            max = m;
            min = mi;
            is = isBST;
            sum = s;
            currmax = curr;
        }

        Info() {
        };
    };

    static class INT {
        int a;
    }

    public static Info MaxSumBSTutil(Node root, INT maxsum) {
        if (root == null) {
            return new Info(Integer.MIN_VALUE, Integer.MAX_VALUE, true, 0, 0);
        }
        if (root.left == null && root.right == null) {
            maxsum.a = Math.max(maxsum.a, root.data);
            return new Info(root.data, root.data, true, root.data, maxsum.a);
        }
        Info L = MaxSumBSTutil(root.left, maxsum);
        Info R = MaxSumBSTutil(root.right, maxsum);
        Info BST = new Info();

        if (L.isBST && R.isBST && L.max < root.data && R.min > root.data) {
            BST.max = Math.max(root.data, Math.max(L.max, R.max));
            BST.min = Math.min(root.data, Math.min(L.min, R.min));
            maxsum.a = Math.max(maxsum.a, R.sum + root.data + L.sum);

            BST.sum = R.sum + root.data + L.sum;
            BST.currmax = maxsum.a;
            BST.isBST = true;
            return BST;
        }
        BST.isBST = false;
        BST.currmax = maxsum.a;
        BST.sum = R.sum + root.data + L.sum;
        return BST;

    }

    static int MaxSumBST(Node root) {
        INT maxsum = new INT();
        maxsum.a = Integer.MIN_VALUE;
        return MaxSumBSTutil(root, maxsum).currmax;
    }

    public static void inorder(Node root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.data + " ");
        inorder(root.right);
    }

    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(9);
        root.left.left = new Node(6);
        root.left.left.left = new Node(8);
        root.left.left.right = new Node(7);

        root.right = new Node(2);
        root.right.right = new Node(3);
        inorder(root);
        System.out.println();
        System.out.println("The max sum of nodes of BST in the given BT: " + MaxSumBST(root));
    }

}

Step-by-Step Explanation

  1. Class Definitions:

    • Node: Represents a node in the binary tree with data, left, and right pointers.
    • Info: Holds information about a subtree, including its maximum and minimum values, whether it is a BST, its sum, and the current maximum sum of BST nodes.
    • INT: A wrapper class for an integer to hold the maximum sum found so far.

  2. MaxSumBSTutil Function:

    • Base Case: If the root is null, return an Info object indicating an empty subtree.
    • Leaf Node Case: If the node is a leaf (no children), update maxsum and return an Info object with the node’s data.
    • Recursive Case: Recursively call MaxSumBSTutil for the left and right subtrees.
    • BST Check: Check if the current node with its left and right subtrees forms a BST. If true, update the Info object accordingly and update maxsum.
    • Non-BST Case: If the current subtree is not a BST, mark it as such and return the Info object.

  3. MaxSumBST Function:

    • Initializes maxsum to the smallest possible integer value.
    • Calls MaxSumBSTutil and returns the maximum sum of BST nodes found.

  4. Inorder Traversal:

    • A helper function to print the tree nodes in inorder fashion.

  5. Main Function:

    • Constructs a binary tree.
    • Prints the inorder traversal of the tree.
    • Prints the maximum sum of BST nodes in the given binary tree.

Dry Run

Let’s dry run the code with the provided tree:

        5
       / \
      9   2
     /     \
    6       3
   / \
  8   7

  1. Inorder Traversal:

    • The inorder traversal of the tree will print: 8 6 7 9 5 2 3.

  2. MaxSumBST Calculation:

    • Starting from the leaf nodes:
      • Node 8 and 7 are BSTs with sums 8 and 7.
      • Node 6 with children 8 and 7 is not a BST because 8 is greater than 6.
    • Node 9 with left child 6 is not a BST.
    • Node 3 is a BST with sum 3.
    • Node 2 with right child 3 is a BST with sum 5.
    • Node 5 with left child 9 and right child 2 is not a BST.

Comments

Post a Comment