// Definition for a binary tree node.
// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }

public class Solution {

    public int maxDepth(TreeNode root) {
        if (root == null) { return 0; }
        int maxDepth = 1;
        Stack<NodeWithDepth> stack = new Stack<>();
        stack.push(new NodeWithDepth(1, root));

        while (!stack.isEmpty()) {
            NodeWithDepth curr = stack.pop();
            if (curr.node.left == null && curr.node.right == null) {
                maxDepth = Math.max(curr.depth, maxDepth);
            } else {
                if (curr.node.right != null) {
                    stack.push(new NodeWithDepth(curr.depth + 1, curr.node.right));
                }
                if (curr.node.left != null) {
                    stack.push(new NodeWithDepth(curr.depth + 1, curr.node.left));
                }
            }
        }

        return maxDepth;
    }

    private class NodeWithDepth {
        int depth;
        TreeNode node;

        public NodeWithDepth(int depth, TreeNode node) {
            this.depth = depth;
            this.node = node;       
        }
    }
}