/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minCameraCover(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;

        debugMark(root, 1);

        debugTree(root);

        TreeNode current;
        LinkedList<TreeNode> path;

        for (int i = 0; i < 1; i++) {
            // descend from root the first time
            current = root;
            path = new LinkedList<>();

            while (current != null) {
                path.addLast(current);
                if (current.left != null) {
                    current = current.left;
                }
                else if (current.right != null) {
                    current = current.right;
                }
                else break;
            }

            // enumerate all paths
            for (;;) {
                debugPath(path);

                // choose next path
                while (path.size() >= 2) {
                    current = path.get(path.size()  - 2);
                    if (current.left == path.getLast()) {
                        path.removeLast();
                        break;
                    }
                    path.removeLast();
                }
                // descend
                if (current == null) break;

                current = current.right;
                while (current != null) {
                    path.addLast(current);
                    current = current.left;
                }
            }
        }

        return 0;
    }

    private int debugMark(TreeNode root, int next) {
        root.val = next++;
        if (root.left != null) {
            next = debugMark(root.left, next);
        }
        if (root.right != null) {
            next = debugMark(root.right, next);
        }
        return next;
    }

    private void debugTree(TreeNode root) {
        System.out.print("Tree: ");
        debugTreeInt(root);
        System.out.println();
    }

    private void debugTreeInt(TreeNode root) {
        if (root == null) {
            System.out.print(".");
            return;
        }
        System.out.print(root.val);
        System.out.print("L");
        debugTreeInt(root.left);
        System.out.print("R");
        debugTreeInt(root.right);
    }

    private void debugPath(LinkedList<TreeNode> path) {
        System.out.print("Path: ");
        for (TreeNode node: path) {
            System.out.print(node.val + ", ");
        }
        System.out.println();
    }
}