package trees;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class DeleteZeroSumSubTrees {


    /*
     * Given root of a binary tree, delete any subtrees whose nodes sum up to zero
     * Runtime Complexity:
     * Linear, O(n)
     *
     * Memory Complexity:
     * O(h)
     *
     * Do a post order traversal of the binary tree.
     * Traverse the left subtree by recursively calling the post-order function.
     * Traverse the right subtree by recursively calling the post-order function.
     * Process the data part of root element (or current element).
     *
     * For every node, if it's left or right subtree reports zero sum, delete that subtree.
     * Moreover, if the root node returns zero then we will delete the entire tree.
     *
     * */

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

        Node(int item) {
            data = item;
            left = right = null;
        }

        public int getData() {
            return data;
        }

        public Node getLeft() {
            return left;
        }

        public Node getRight() {
            return right;
        }
    }


    private Node root1;


    public static int deleteZeroSumSubtreeRec(Node root) {

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

        int sumLeft = deleteZeroSumSubtreeRec(root.left);
        int sumRight = deleteZeroSumSubtreeRec(root.right);

        if (sumLeft == 0) {
            root.left = null;
        }
        if (sumRight == 0) {
            root.right = null;
        }
        return root.data + sumLeft + sumRight;
    }



    protected void deleteZeroSumSubtree() {
        if (root1 == null) {
            return;
        }

        if (0 == deleteZeroSumSubtreeRec(root1)) {
            root1 = null;
        }
    }



    public static Node createTestTree() {
        Node head = new Node(7);
        Node curr_head = head;

        Node left = new Node(5);
        Node right = new Node(6);//
        curr_head.left = left;
        curr_head.right = right;

        curr_head = head.left;
        left = new Node(-3);
        right = new Node(-2);
        curr_head.left = left;
        curr_head.right = right;

        return head;
    }


    protected void levelOrderTraversal(Node root) {

        if (root == null) {
            return;
        }

        List<Queue<Node>> queues = new ArrayList<>();
        queues.add(new ArrayDeque<>());
        queues.add(new ArrayDeque<>());

        Queue<Node> currentQueue = queues.get(0);
        Queue<Node> nextQueue = queues.get(1);

        currentQueue.add(root);
        int levelNumber = 0;

        while (!currentQueue.isEmpty()) {
            Node temp = currentQueue.poll();
            System.out.print(temp.data + ",");

            if (temp.left != null) {
                nextQueue.add(temp.left);
            }

            if (temp.right != null) {
                nextQueue.add(temp.right);
            }

            if (currentQueue.isEmpty()) {
                System.out.println();
                ++levelNumber;
                currentQueue = queues.get(levelNumber % 2);
                nextQueue = queues.get((levelNumber + 1) % 2);
            }
        }
        System.out.println();
    }


    public static void main(String[] args) {

        DeleteZeroSumSubTrees tree = new DeleteZeroSumSubTrees();

        tree.root1 = createTestTree();
        tree.levelOrderTraversal(tree.root1);
        System.out.println();

        tree.deleteZeroSumSubtree();
        tree.levelOrderTraversal(tree.root1);
    }

}