Simple Java recursion with explanation


  • 0
    L

    The definition is clear: the maximum allowed difference between the heights of left and right subtree is <=1. We already know how to get the height of a binary tree. The issue may be that we need both the height of a tree at each stack along with whether that particular subtree is balanced or not. One way is to use global variables to maintain left and right heights. The other option is to wrap the height and the balanace attributes into a single class and return that. Here is the code for that:

    public boolean isBalanced(TreeNode root) {
            return helper(root).balanced;
        }
        
        private Adapter helper(TreeNode root) {
            if(root == null) {
                return new Adapter(0,true);
            }
            
            Adapter left = helper(root.left);
            if(!left.balanced) {
                return new Adapter(left.height,false);
            }
            Adapter right = helper(root.right);
            if(!right.balanced) {
                return new Adapter(right.height,false);
            }
            
            if(Math.abs(left.height-right.height)>1) {
                return new Adapter(1+Math.max(left.height,right.height),false);    
            }
            else {
                return new Adapter(1+Math.max(left.height,right.height),true);
            }
        }
        
        
        private class Adapter {
            private int height;
            private boolean balanced;
            Adapter(int height, boolean balanced) {
                this.height = height;
                this.balanced = balanced;
            }
        }
    

Log in to reply
 

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