Iterative Solution to finding if a tree is balanced

Question

So someone posted their solution to this, but I found that it didn't seem to work, I posted this there but I wanted to make it more accessible to others.

The question is in "Cracking the Code Interview" and it is the first tree question, feel free to make other suggestions (or prove me wrong!)

Answer 1

The key here is that it is difficult to keep track of the eventual paths and their heights with one stack.

What I ended up doing is pushing both the left and right child's height on a stack, checking if they are within one of one another, adding one to the max and then pushing that onto the stack after popping the left and right off.

I have commented so I hope it's clear enough

 /* Returns true if binary tree with root as root is height-balanced */
        boolean isBalanced(Node root) {
            if(root == null) return false;

            Deque<Integer> heights = new LinkedList<>();
            Deque<Node> trail = new LinkedList<>();
            trail.push(root);

            Node prev = root; //set to root not null to not confuse when root is misisng children

            while(!trail.isEmpty()) {
                Node curr = trail.peek(); //get the next node to process, peek because we need to maintain trail until we return

                //if we just returned from left child
                if (curr.left == prev) {
                    if(curr.right != null) trail.push(curr.right); //if we can go right go
                    else {
                        heights.push(-1); //otherwise right height is -1 does not exist and combine heights
                        if(!combineHeights(heights)) return false;
                        trail.pop(); //back to parent
                    }
                }
                //if we just returned from right child
                else if (curr.right == prev) {
                    if(!combineHeights(heights)) return false;
                    trail.pop(); //up to parent
                }
                //this came from a parent, first thing is to visit the left child, or right if no left
                else {
                    if(curr.left != null) trail.push(curr.left);
                    else {
                        if (curr.right != null) {
                            heights.push(-1); //no left so when we combine this node left is 0
                            trail.push(curr.right); //since we never go left above logic does not go right, so we must here
                        }
                        else { //no children set height to 1
                            heights.push(0);
                            trail.pop(); //back to parent
                        }
                    }
                }

                prev = curr;
            }

            return true;
        }

        //pop both previous heights and make sure they are balanced, if not return false, if so return true and push the greater plus 1
        private boolean combineHeights(Deque<Integer> heights) {
            int rightHeight = heights.pop();
            int leftHeight = heights.pop();

            if(Math.abs(leftHeight - rightHeight) > 1) return false;
            else heights.push(Math.max(leftHeight, rightHeight) + 1);
            return true;
        }