Analysis

The first thing to do when approaching this problem is to clarify what a balanced tree is as doing this can often help prevent mistakes. A balanced tree is defined as a tree where the depth of all leaf nodes or nodes with single children differ by no more than one.

So the solution should get the node with the minimum depth and the node with the maximum depth and ensure they only differ by 0 or 1.

So let’s create separate functions to retrieve the minimum and maximum as it won’t affect the time complexity or the solution since O(cn) = O(n) for some constant c.

Recursive functions to determine the minimum and maximum depth of the tree are fairly trivial to implement. First define the base case; when the node is null return 0. The Recursive case for maxDepth will return the larger of itself called on the left and right children plus 1.

For minDepth it will return the smaller of itself called on the left and right children plus 1.

Complexity

Both minDepth and maxDepth are called for the tree, each of which traverses each node exactly once. So the time complexity is O(2n) = O(n).

Code

public class Solution {
    /**
     * Determines whether a binary tree is balanced.
     *
     * @param {BinaryTreeNode} root The root of the tree.
     * @returns Whether the tree is balanced.
     */
    public static boolean isBinaryTreeBalanced(BinaryTreeNode root) {
        if (root == null) {
            throw new IllegalArgumentException(
                    "The tree root must be non null");
        }
        return maxDepth(root) - minDepth(root) <= 1;
    }

    /**
     * Determines the minimum depth of a binary tree node.
     *
     * @param node The node to check.
     * @return The minimum depth of a binary tree node.
     */
    private static int minDepth(BinaryTreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.min(minDepth(node.left), minDepth(node.right));
    }

    /**
     * Determines the maximum depth of a binary tree node.
     *
     * @param node The node to check.
     * @return The maximum depth of a binary tree node.
     */
    private static int maxDepth(BinaryTreeNode node) {
      if (node == null) {
          return 0;
      }
      return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
    }
}



public class BinaryTreeNode {
    public Object data;
    public BinaryTreeNode left;
    public BinaryTreeNode right;

    public BinaryTreeNode(Object data, BinaryTreeNode left,
            BinaryTreeNode right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}

/**
 * Creates a binary tree node.
 *
 * @constructor
 * @param {Object} data The data associated with this node.
 * @param {BinaryTreeNode} left The left child node.
 * @param {BinaryTreeNode} right The right child node.
 */
function BinaryTreeNode(data, left, right) {
  this.data = data;
  this.left = left;
  this.right = right;
}

/**
 * Determines the minimum depth of a binary tree node.
 *
 * @param {BinaryTreeNode} node The node to check.
 * @return The minimum depth of a binary tree node.
 */
function minDepth(node) {
  if (typeof node === 'undefined') {
    return 0;
  }
  return 1 + Math.min(minDepth(node.left), minDepth(node.right));
}

/**
 * Determines the maximum depth of a binary tree node.
 *
 * @param {BinaryTreeNode} node The node to check.
 * @return The maximum depth of a binary tree node.
 */
function maxDepth(node) {
  if (typeof node === 'undefined') {
    return 0;
  }
  return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}

/**
 * Determines whether a binary tree is balanced.
 *
 * @param {BinaryTreeNode} root The root of the tree.
 * @returns Whether the tree is balanced.
 */
function isBinaryTreeBalanced(root) {
  if (typeof root === 'undefined') {
    return undefined;
  }
  return maxDepth(root) - minDepth(root) <= 1;
}

Textbooks

Here are two textbooks that provide many Q&A's like this post that I personally recommend, both were invaluable to me when I was studying for my interviews.

 

More posts tagged Interview question