Code to tell if a binary tree is balanced

Code to tell if a binary tree is balanced

I have heard people say it is easy but it took me some time to get this… 🙁

 

public class BalancedTree {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            int[] lh = _isBalanced(root);
            return lh == null ? false : true;
        }
    }

    private int[] _isBalanced(TreeNode root) {
        int[] def = new int[2];
        def[0] = 0;
        def[1] = 0;
        if (root.left != null) {
            int[] tmp = _isBalanced(root.left);
            if (tmp != null) {
                def[0] = Math.max(tmp[0], tmp[1]) + 1;
            } else {
                return null;
            }
        }
        if (root.right != null) {
            int[] tmp = _isBalanced(root.right);
            if (tmp != null) {
                def[1] = Math.max(tmp[0], tmp[1]) + 1;
            } else {
                return null;
            }
        }
        if (def == null || Math.abs(def[0] - def[1]) > 1) {
            return null;
        } else {
            return def;
        }
    }
}
Advertisements
READ  Script to git clone all repositories of a user from bitbucket

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Terms of Use | Privacy Policy 
2018-2019 © eXitDiscount