// Program to test solutions to problem #7 on the cse143 final, summer 2022.
// Fill in your solution to trimTo, then compile and run the program.
// Note: This testing program does not check for the IllegalArgumentException.

class IntTree {
    private IntTreeNode overallRoot;

    public void trimTo(int level) {
        if (level < 1) {
            throw new IllegalArgumentException();
        }
        overallRoot = trimTo(overallRoot, 1, level);
    }

    private IntTreeNode trimTo(IntTreeNode root, int curr, int level) {
        if (curr <= level && root != null) {
            if (root.left == null && root.right == null) {
                root = null;
            } else {
                root.left = trimTo(root.left, curr + 1, level);
                root.right = trimTo(root.right, curr + 1, level);
            }
        }
        return root;
    }

    // Define any private helper methods here

    public IntTree() {
        overallRoot = null;
    }

    public IntTree(IntTreeNode root) {
        overallRoot = copy(root);
    }

    private IntTreeNode copy(IntTreeNode root) {
        if (root == null) {
            return null;
        } else {
            return new IntTreeNode(root.data, copy(root.left), copy(root.right));
        }
    }

    public boolean equals(Object o) {
        if (o == null || !(o instanceof IntTree)) {
            return false;
        }

        IntTree other = (IntTree) o;
        return equals(this.overallRoot, other.overallRoot);
    }

    private boolean equals(IntTreeNode r1, IntTreeNode r2) {
        if (r1 == null || r2 == null) {
            return r1 == r2;
        } else {
            return r1.data == r2.data && equals(r1.left, r2.left) && equals(r1.right, r2.right);
        }
    }

    public void printSideways() {
        String overallPrefix = "overallRoot -> ";
        if (overallRoot == null) {
            System.out.println(overallPrefix + "null");
        } else {
            printSideways(overallRoot, overallPrefix);
        }
    }

    private void printSideways(IntTreeNode root, String prefix) {
        if (root != null) {
            String nextPrefix = prefix.replaceAll(".", " ") + "    ";
            printSideways(root.right, nextPrefix);
            System.out.println(prefix + root.data);
            printSideways(root.left, nextPrefix);
        }
    }

    public void trimToSolution(int level) {
        if (level < 1) {
            throw new IllegalArgumentException();
        }
        overallRoot = trimToSolution(overallRoot, 1, level);
    }

    private IntTreeNode trimToSolution(IntTreeNode root, int curr, int level) {
        if (curr <= level) {
            if (root == null) {
                return null;
            } else if (root.left == null && root.right == null) {
                return null;
            } else {
                root.left = trimToSolution(root.left, curr + 1, level);
                root.right = trimToSolution(root.right, curr + 1, level);
                return root;
            }
        }
        return root;
    }

}

class IntTreeNode {
    public int data;
    public IntTreeNode left;
    public IntTreeNode right;

    public IntTreeNode() {
        this(0);
    }

    public IntTreeNode(int data) {
        this(data, null, null);
    }

    public IntTreeNode(int data, IntTreeNode left, IntTreeNode right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}

public class FinalTest7 {
    public static void main(String[] args) {
        System.out.println("All trees printed in this program are printed \"sideways\" "
                + "in the sense that if you tilt your head left, you will see the tree structure "
                + "where nodes that were \"above\" a node mean they are in that node's right subtree "
                + "and nodes that were \"below\" a node mean they are in that node's left subtree.");
        System.out.println();

        IntTreeNode t1 = null;
        test(1, t1);
        test(4, t1);

        IntTreeNode t2 = new IntTreeNode(1);
        test(1, t2);
        test(4, t2);

        IntTreeNode t3= new IntTreeNode(0,
                    new IntTreeNode(3),
                    new IntTreeNode(0,
                        new IntTreeNode(5,
                            new IntTreeNode(1),
                            new IntTreeNode(8)),
                        new IntTreeNode(9)));
        test(1, t3);
        test(2, t3);
        test(3, t3);
    }

    public static void test(int level, IntTreeNode root) {
        IntTree solution = new IntTree(root);

        System.out.println("=== Test ===");
        System.out.println("Calling trimTo(" + level + ") on the following tree:");
        System.out.println();
        solution.printSideways();
        System.out.println();

        solution.trimToSolution(level);
        try {
            IntTree student = new IntTree(root);
            student.trimTo(level);

            if (solution.equals(student)) {
                System.out.println("Passed!");
            } else {
                System.out.println("Trees did not match! Expected:");
                System.out.println();
                solution.printSideways();
                System.out.println();
                System.out.println("But received:");
                System.out.println();
                student.printSideways();
            }
        } catch (Exception e) {
                System.out.println("Threw exception: " + e + " @ " + e.getStackTrace()[0]);
        }

        System.out.println();
    }
}