Java check if binary tree is balanced

Question

This is a question from "Cracking the Coding Interview":

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.

The book only gives a recursive solution. I came up with an iterative solution using BFS, and just wanted to share it. I did dry-run it, but wanted to make sure I made no mistake. I would also like to see how other people think they might be able to improve it.

Thanks!

sarora · Accepted Answer · 2015-01-20 02:22:04Z

1

class Node
{
int data;
LinkedList<Node> children;
}

public static boolean isBalanced(Node root)
{
LinkedList<Node> queue = new LinkedList<Node>();
queue.offer(root);

int currentLevel = -1, toNextLevel = 0, toNextLevelTemp = 1;

int minLevel = Integer.MAX_VALUE, maxLevel = Integer.MIN_VALUE;

while(!queue.isEmpty())
{
    if(toNextLevel == 0)
    {
        currentLevel++;
        toNextLevel = toNextLevelTemp;
        toNextLevelTemp = 0;
    }

    Node temp = queue.poll();
    toNextLevel--;

    //if temp is a leaf, record its depth
    if(temp.children.size() == 0)   
    {
        if(currentLevel < minLevel)
            minLevel = currentLevel;

        if(currentLevel > maxLevel)
            maxLevel = currentLevel;
    }

    //do whatever with temp
    for(Node child: temp.children)
    {
        queue.add(child);
        toNextLevelTemp++;
    }
}

//if difference between minLevel and maxLevel is more than 1
if(maxLevel - minLevel > 1)
    return false;

return true;
}

answered Jan 20, 2015 at 2:22

sarora

5195 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

sarora Over a year ago

The variable "toNextLevel" keeps track of how many nodes till next level. "toNextLevelTemp" counts the number of nodes being added to the queue while still in the current level, and gives its value to "toNextLevel" when the level increments.

Brandon Ross Pollack Over a year ago

I don't think this will work, think about if you dont have a child on one side, it will be ignored, this only considers leaves, if one of a node's children is null, then the other is not allowed to have children in a balanced tree, ill mess with it and see if i can find an intuitive way to integrate that into this solution

Brandon Ross Pollack · Accepted Answer · 2016-03-18 14:48:09Z

took me longer than I expected, but this solution works, feel free to make my code prettier, after I got it working i did minimal touching up

/* Returns true if binary tree with root as root is height-balanced */
    boolean isBalanced(Node root) {
        if(root == null) return false;

        Deque<Integer> heights = new LinkedList<>();
        Deque<Node> trail = new LinkedList<>();
        trail.push(root);

        Node prev = root; //set to root not null to not confuse when root is misisng children

        while(!trail.isEmpty()) {
            Node curr = trail.peek(); //get the next node to process, peek because we need to maintain trail until we return

            //if we just returned from left child
            if (curr.left == prev) {
                if(curr.right != null) trail.push(curr.right); //if we can go right go
                else {
                    heights.push(-1); //otherwise right height is -1 does not exist and combine heights
                    if(!combineHeights(heights)) return false;
                    trail.pop(); //back to parent
                }
            }
            //if we just returned from right child
            else if (curr.right == prev) {
                if(!combineHeights(heights)) return false;
                trail.pop(); //up to parent
            }
            //this came from a parent, first thing is to visit the left child, or right if no left
            else {
                if(curr.left != null) trail.push(curr.left);
                else {
                    if (curr.right != null) {
                        heights.push(-1); //no left so when we combine this node left is 0
                        trail.push(curr.right); //since we never go left above logic does not go right, so we must here
                    }
                    else { //no children set height to 1
                        heights.push(0);
                        trail.pop(); //back to parent
                    }
                }
            }

            prev = curr;
        }

        return true;
    }

    //pop both previous heights and make sure they are balanced, if not return false, if so return true and push the greater plus 1
    private boolean combineHeights(Deque<Integer> heights) {
        int rightHeight = heights.pop();
        int leftHeight = heights.pop();

        if(Math.abs(leftHeight - rightHeight) > 1) return false;
        else heights.push(Math.max(leftHeight, rightHeight) + 1);
        return true;
    }

Collectives™ on Stack Overflow

Java check if binary tree is balanced

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related