Java Iterative and Recursive
The recursive version uses -1 to signal imbalance, which means the rest of the tree need not be examined. This will help reduce runtime from O(N^2) to O(N). \n\
The recursive version uses -1 to signal imbalance, which means the rest of the tree need not be examined. This will help reduce runtime from O(N^2) to O(N). \n\n```\nclass Solution {\n    public boolean isBalanced(TreeNode root) {\n        return getDepth(root) != -1;\n    }\n    \n    private int getDepth(TreeNode root){\n        if(root == null) return 0;\n        \n        int leftHeight = getDepth(root.left);\n        if(leftHeight == -1) return -1;\n        \n        int rightHeight = getDepth(root.right);\n        if(rightHeight == -1) return -1;\n        \n        if(Math.abs(leftHeight - rightHeight) > 1) return -1;\n        \n        return 1 + Math.max(leftHeight, rightHeight);\n    }\n    \n}\n```\nFor iterative solution, we will use postorder traversal. \nWe move left, store heights of all nodes in a map. Then move right, store heights of all nodes in a map again. Then compare height of stack\'s peek\'s left and right nodes(which have been stored in our map), and proceed accordingly.\n```\nclass Solution{\n    public boolean isBalanced(TreeNode root){\n        if(root == null) return true;\n        Map<TreeNode, Integer> heights = new HashMap<>();\n        ArrayDeque<TreeNode> stack = new ArrayDeque<>();\n        stack.push(root);\n        while(!stack.isEmpty()){\n            TreeNode curr = stack.peek();\n            if(curr.left != null && !heights.containsKey(curr.left)){\n                curr = curr.left;\n                stack.push(curr);\n            }\n            else if(curr.right != null && !heights.containsKey(curr.right)){\n                curr = curr.right;\n                stack.push(curr);\n            }\n            else{\n                int leftHeight = curr.left == null? 0: heights.get(curr.left);\n                int rightHeight = curr.right == null? 0: heights.get(curr.right);\n                if(Math.abs(leftHeight - rightHeight) > 1) return false;\n                heights.put(curr, 1 + Math.max(leftHeight, rightHeight));\n                stack.pop();\n            }\n        }\n        return true;\n    }\n}\n```\n\nNote, the recursive version beats 100%, but the iterative version is much slower.\nI reckon this is because of the overhead of using a Map. \nI didn\'t find any solution in the Discussion having an iterative version without a map, so suggestions are welcome.\nHope this helps.
[]