Accepted - Iterative Java Solution


  • 0
    R

    Iterative solution. Basically keeping track of the node and its height using a map and then making decisions based on that.

    public boolean isBalanced(TreeNode root) {
             if(root == null){
                return true;
            }
            Stack<TreeNode> nodeStack = new Stack<>();
            // This keeps a track of the height calculated for each node.
            // The height of a node in a tree is the length of a longest path from the node to a leaf.
            // If it has two paths of leafs with different heights. The max of them is the height of the node in this tree.
            Map<TreeNode,Integer> nodeHeightMap= new HashMap<>();
            nodeStack.push(root);
            while (!nodeStack.isEmpty()){
    
                TreeNode node = nodeStack.peek();
                // The reason we are checking the map is we are looking if the height of a node has been calculated previously.
                if(node.left!=null && !nodeHeightMap.containsKey(node.left)){
                    nodeStack.push(node.left);
                }
                else if( node.right!=null && !nodeHeightMap.containsKey(node.right)){
                    nodeStack.push(node.right);
                }
                else {
                    TreeNode nodePopped = nodeStack.pop();
                    int leftSubTreeHeight = (nodePopped.left == null)?0:nodeHeightMap.get(nodePopped.left);
                    int rightSubTreeHeight = (nodePopped.right == null)?0:nodeHeightMap.get(nodePopped.right);
                    // Absolute value of the difference between the left and right subtree heights.
                    int resultantHeightofNode = Math.abs(leftSubTreeHeight-rightSubTreeHeight);
                    // If the left & right subtree heights differ by more than 1 then it's not balanced binary tree.
                    if(resultantHeightofNode > 1){
                        return false;
                    }
                    nodeHeightMap.put(nodePopped,Math.max(leftSubTreeHeight,rightSubTreeHeight)+1);
                }
            }
            return true;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.