1
\$\begingroup\$

Yet another interview question:

Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.

First off, did I understand the question correctly? In other words, we are looking for a subtree in a tree (or rotation of it) that looks like:

     root
    /    \
 leaf_1  leaf_2
  /
leaf1_1

My initial idea was to count the depth of the tree and check if maxDepth - minDepth < 2 (which requires 2 traversal) . But I think I found a more efficient solution. The trade-off is that we should keep the ref to the root. I assume n-ary tree.

Is this correct?

import java.util.LinkedList;

public class Trees {

    Node threeRoot;
    private boolean isBalanced = true;

    Trees(Node threeRoot){
        this.threeRoot = threeRoot;
    }

    static class  Node{
        public Node root;
        public LinkedList<Node> children = new LinkedList<>();        
    }

     boolean isBalanced(Node node){
       if (threeRoot == null) {
            isBalanced = true;
        }
        if (threeRoot.children == null || threeRoot.children.isEmpty()) {
            isBalanced = true;
        }

        isBalancedRed(node);          
        return isBalanced;
    }

     void isBalancedRed(Node node) {
        if (node.children.isEmpty()) {
            if (node.root != null && node.root.children.size() == 1) {
                isBalanced = false;
            }
        }
        for(Node nodeEl : node.children)
        {
            isBalancedRed(nodeEl);
        }
    }

    public static void main(String[] args){
        Trees tree = new Trees(new Node());
        Node root = tree.threeRoot;
        Node leaf1 = new Node();
        Node leaf2 = new Node();
        Node leaf11 = new Node();

        root.children.add(leaf1);
        leaf1.root = root;
        root.children.add(leaf2);
        leaf2.root = root;

        leaf2.children.add(leaf11);
        leaf11.root = leaf2;

        System.out.println(tree.isBalanced(root));           
    }        
}
\$\endgroup\$
5
\$\begingroup\$

First off, I would use something other than a LinkedList to hold the children of an n-ary tree. A LinkedList requires you to enumerate the list in order to get the reference to any child other than the leftmost, which is going to slow you down.

Second, your code is basically returning false in any situation where the Node's parent has one child that itself doesn't have any children. In your example tree, that's the exact case (you have two children of the root, one of which has another child) but the tree is balanced according to the rules, so I would expect this algorithm to return a lot of false positives (and negatives).

Finding the depth of an n-ary tree is a linear-bound operation; you traverse each branch of the tree recursively, finding the depth at each leaf node. You can find both the maximum and minimum depth in one traversal; at each level, ask each branch for its maximum and minimum depth, passing the depth of the current node. The base case is that of a leaf node (no children); the min and max is the depth of that leaf. You can store this result in a Tuple or in a more specialized MinMax struct, as you please. With those results returned to the calling level, scan them to find the lowest Min and the greatest Max, and return that to the caller.

Here's a basic implementation:

public class MinMax<T>
{
    private T minVal;
    private T maxVal;

    public MinMax(T min, T max)
    {
       minVal = min;
       maxVal = max;
    }

    public T min() {return minVal;}
    public T max() {return maxVal;}
}

private MinMax<Integer> GetMinMaxDepth(Node node, int currDepth)
{
    //base case; no children. Max and min depth at this leaf is currDepth.
    if(node.children == null || node.children.size() == 0)
       return new MinMax<Integer>(currDepth, currDepth);

    //determine the maximum and minimum depth of all child branches,
    //and track the absolute max and min across all of them.
    int min = Integer.MAX_VALUE, max = -1;
    for(Node nextNode : node.children)
    {
        MinMax<Integer> childDepth = GetMinMaxDepth(nextNode, currDepth+1);
        if(childDepth.min() < min) min = childDepth.min();
        if(childDepth.max() > max) max = childDepth.max();
    }      

    return new MinMax<Integer>(min, max);
}

boolean isBalanced()
{
    //easy cases; a tree with 0 or 1 elements.
    if(treeRoot == null || treeRoot.children == null || treeRoot.children.size() == 0)
       return true;
    //traverse the tree and find the minimum and maximum depth.
    MinMax<Integer> minMaxDepth = GetMinMaxDepth(treeRoot, 0);

    return minMaxDepth.max() - minMaxDepth.min() > 1;
}

This could probably be optimized in our case to return early if we discover that any node's child depths differ by more than 1. We could hack it by throwing an Exception, but the proper strategy is almost as easy to implement:

private MinMax<Integer> GetMinMaxDepth(Node node, int currDepth)
{
    //base case; no children. max and min depth at this leaf is currDepth.
    if(node.children == null || node.children.size() == 0)
       return new MinMax<Integer>(currDepth, currDepth);

    //determine the maximum and minimum depth of all child branches,
    //and track the absolute max and absolute minimum.
    int min = Integer.MIN_VALUE, max = -1;
    for(Node nextNode : node.children)
    {
        MinMax<Integer> childDepth = GetMinMaxDepth(nextNode, currDepth+1);
        //Exit now if child is unbalanced
        if(childDepth.max() - childDepth.min() > 1) return childDepth;
        if(childDepth.min() < min) min = childDepth.min();
        if(childDepth.max() > max) max = childDepth.max();
        //Exit now if current node is unbalanced
        if(max-min > 1) break;
    }      

    return new MinMax<Integer>(min, max);
}

The upside is that we quit as soon as we know the answer to the question (is the tree unbalanced?), which will increase the average performance (but not the worst-case performance on a tree that is balanced or is unbalanced at its furthest extremities). The downside is that we no longer know how unbalanced the tree is; the MaxMin returned to the top level will always have a Max and Min that differ by the first detected difference greater than the threshold (probably 2), not the absolute difference in depth of leaf nodes in the tree.

The one case that is difficult to determine in an n-ary tree is that of a tree that never forks. This algorithm will find a depth difference between any two or more branches, but when there is only one branch, the maximum and minimum depths of the tree are the same and there's nothing to use for comparison. Technically, it would have only one "leaf" node (usually defined as a node with no children) and so by the given definition all (one) of the leaves are the same distance from the root, however if you looked at the map of an N-ary tree that was more like a linked list (or even a V or Y shape) and went deeper than two levels, you wouldn't call it balanced.

Perhaps a change in definition may be required; a node is a "leaf" node if it does not have N child nodes (where N is the order of the N-ary tree). So, in a quaternary tree (4 children per node), if any node has fewer than 4 children, then the depth of the current node is considered as a "minimum" depth and will almost certainly be the minimum depth at that level. That's another easy change:

private MinMax<Integer> GetMinMaxDepth(Node node, int currDepth)
{
    //base case; no children. max and min depth at this leaf is currDepth.
    if(node.children == null || node.children.size() == 0)
       return new MinMax<Integer>(currDepth, currDepth);

    //determine the maximum and minimum depth of all child branches,
    //and track the absolute max and absolute minimum.
    //Exit as soon as we know that this or any child node is unbalanced.
    int min = Integer.MIN_VALUE, max = -1;

    //If this node isn't "full", its depth is the minimum depth for this branch
    if(node.children.size < max_children) min = currDepth;      

    for(Node nextNode : node.children)
    {
        MinMax<Integer> childDepth = GetMinMaxDepth(nextNode, currDepth+1);
        //check if child is already unbalanced
        if(childDepth.max() - childDepth.min() > 1) return childDepth;
        if(childDepth.min() < min) min = childDepth.min();
        if(childDepth.max() > max) max = childDepth.max();
        //check if current node is unbalanced
        if(max-min > 1) break;
    }      

    return new MinMax<Integer>(min, max);
}
\$\endgroup\$
  • \$\begingroup\$ thx for the input. 1. LinkedList - sure. If I optimize for performance I'd use ArrayList. Not only for fast random access, but also CPU cache usage. The odds that next element of an array will be in cache is very high comparing to odds that next element of a linked list will be in cache(close to 0). 2. LindkeList is implemented as a double linked list do getFirst() and getLast() should be O(1) and the rest O(n) ofc. 3. you prolly mean public class MinMax<T> not struct and return minValue. 4. Seems I didn't understand the problem correctly. \$\endgroup\$ – Lukasz Madon Jun 18 '12 at 18:14
  • \$\begingroup\$ Yes, I probably mean public class MinMax<T>; I'm a C# developer by trade, and in that language generic structs are allowed. In this simple example you could just make all Ts ints and remove the generic parameter, but of course a struct like MinMax could have value elsewhere so I tried to make it more useful. Edits coming. \$\endgroup\$ – KeithS Jun 18 '12 at 18:50
-1
\$\begingroup\$

To check if a binary tree is balanced or not we need to check if both its left and right children are balance and difference between their heights is atmost 1. Here instead of computing the height for each node multiple times we can store the height in a hashmap i.e for each node its corresponding height. We can even store the height of a node as a property in the node itself. rest of the code is straight forward.

/**
 * Definition for a binary tree node.
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

// first we will get the left height and right height of the node
// and compute the height difference.if it is > 1 we will return false
// hashtable to maintain height of each node to reduce the no of redundant
// height computations
static Hashtable<TreeNode, Integer> haTab = new Hashtable<>();
public static boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        int leftHeight, rightHeight;
        leftHeight = height(root.left);
        rightHeight = height(root.right);
        // if left child and right child are balanced and the difference in
        // their heights is < 2
        // then it is balanced
        if (isBalanced(root.left) && isBalanced(root.right)
                && Math.abs(leftHeight - rightHeight) < 2) {
            return true;
        }
        return false;
    }

public static void main(String[] args) {
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(-2);
    root.right = new TreeNode(-3);
    root.left.left = new TreeNode(1);
    root.left.right = new TreeNode(3);
    root.right.right = new TreeNode(-1);
    System.out.println(isBalanced(root));
}
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and how it improves upon the original) so that the author can learn from your thought process. \$\endgroup\$ – Pimgd Apr 7 '16 at 14:47
-2
\$\begingroup\$

The return statement in isBalanced() should be:

return !( minMaxDepth.max() - minMaxDepth.min() > 1);
\$\endgroup\$
  • 1
    \$\begingroup\$ Would you mind explaining why? Also this answer isn't much of a review but a rather radical change to the code-behavior. While it may be helpful to criticize and improve the implementation / algorithms of a question, it should not happen without an explanation, why your algorithm is better. \$\endgroup\$ – Vogel612 May 20 '14 at 7:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.