// Program to test solutions to problem #5 on the cse143 final, winter 2023.
// Fill in your solution to oddPathSum, then compile and run the program

import java.util.*;

class IntTree {
    public int oddPathSum() {
        // fill in your solution here and include any private methods below
    }

    private IntTreeNode overallRoot;

    // this is the sample solution
    public int oddPathSum2() {
        return oddPathSum2(overallRoot, 0);
    }

    private int oddPathSum2(IntTreeNode root, int sum) {
        if (root == null) {
            return 0;
        } else {
            sum += root.data;
            int result =
                oddPathSum2(root.left, sum) + oddPathSum2(root.right, sum);
            if (sum % 2 != 0) {
                result++;
            }
            return result;
        }
    }
        
    // post: constructs an empty tree
    public IntTree() {
        overallRoot = null;
    }

    // pre : the tree satisfies the binary search tree property
    // post: value is added so as to preserve the binary search tree property
    public void add(int value) {
        overallRoot = add(overallRoot, value);
    }

    // pre : the tree with given root satisfies the binary search tree property
    // post: value is added so as to preserve the binary search tree property
    private IntTreeNode add(IntTreeNode root, int value) {
        if (root == null)
            root = new IntTreeNode(value);
        else if (value <= root.data)
            root.left = add(root.left, value);
        else
            root.right = add(root.right, value);
        return root;
    }

    // post: prints the data fields of the tree, one per line, following
    //       an inorder traversal and using indentation to indicate node depth;
    //       prints right to left so that it looks correct when the output is
    //       rotated.
    public void printStructure() {
        printStructure(overallRoot, 0);
    }

    // post: prints in preorder the data fields of the given tree indenting
    //       each line to the given level
    private void printStructure(IntTreeNode root, int level) {
        if (root != null) {
            printStructure(root.right, level + 1);
            for (int i = 0; i < level; i++)
                System.out.print("    ");
            System.out.println(root.data);
            printStructure(root.left, level + 1);
        }
    }

    // returns true if this tree equals other tree
    public boolean equals(IntTree other) {
        return equals(overallRoot, other.overallRoot);
    }

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

public class FinalTest5 {
    private static int testCount;
    private static int failCount;

    public static final int ERRORS_MAX = 25;

    public static void main(String[] args) {
        test(0);
        for (int i = 1; i < 30; i++)
            for (int j = 0; j < 5; j++)
                test(i);

        if (failCount == 0) {
            System.out.println("passed all " + testCount + " tests");
        } else {
            System.out.println("failed " + failCount + " of " + testCount + 
                               " tests");
        }
    }

    public static void test(int n) {
        IntTree t1 = new IntTree();
        IntTree t2 = new IntTree();
        Random r = new Random();
        for (int i = 0; i < n; i++) {
            int next = r.nextInt(100);
            t1.add(next);
            t2.add(next);
        }
        int result1 = t1.oddPathSum2();
        boolean fail = false;
        int result2 = 0;
        RuntimeException except = null;
        try {
            result2 = t2.oddPathSum();
        } catch (RuntimeException e) {
            fail = true;
            except = e;
        }
        if (!fail && (result1 != result2)) {
            fail = true;
        }
        testCount++;
        if (fail) {
            System.out.println("Testing this tree:");
            t1.printStructure();
            if (except != null) {
                int line = except.getStackTrace()[0].getLineNumber();
                System.out.println("threw " + except + " at line #" + line);
            } else {
                System.out.println("Expected result = " + result1);
                System.out.println("your result     = " + result2);
            }
            System.out.println("failed");
            System.out.println();
            failCount++;
            if (failCount > ERRORS_MAX) {
                System.out.println("exceeds " + ERRORS_MAX + " errors");
                System.out.println("with " + testCount + " correct");
                System.exit(0);
            }
        }
    }
}

class IntTreeNode {
    public int data;       // data stored at this IntTreeNode
    public IntTreeNode left;  // reference to left subtree
    public IntTreeNode right; // reference to right subtree
        
    // post: constructs a leaf node with given data
    public IntTreeNode(int data) {
        this(data, null, null);
    }
                
    // post: constructs a IntTreeNode with the given data and links
    public IntTreeNode(int data, IntTreeNode left, IntTreeNode right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}