¿Cómo determinar si el árbol binario está equilibrado?

Ha pasado un tiempo desde esos años escolares. Conseguí un trabajo como especialista en informática en un hospital. Tratando de moverme para hacer una programación real ahora. Ahora estoy trabajando en árboles binarios y me preguntaba cuál sería la mejor manera de determinar si el árbol está equilibrado en altura.

Estaba pensando en algo a lo largo de esto:

public boolean isBalanced(Node root){
    if(root==null){
        return true;  //tree is empty
    }
    else{
        int lh = root.left.height();
        int rh = root.right.height();
        if(lh - rh > 1 || rh - lh > 1){
            return false;
        }
    }
    return true;
}

¿Es esta una buena implementación? ¿O me estoy perdiendo algo?

Me encontré con esta vieja pregunta mientras buscaba algo más. Noto que nunca obtuvo una respuesta completa.

La forma de resolver este problema es comenzar escribiendo una especificación para la función que está intentando escribir.

Especificación: Se dice que un árbol binario bien formado tiene "altura equilibrada" si (1) está vacío, o (2) sus elementos secundarios izquierdo y derecho están equilibrados en altura y la altura del árbol de la izquierda está dentro de 1 del altura del árbol de la derecha.

Ahora que tiene la especificación, el código es trivial de escribir. Simplemente siga las especificaciones:

IsHeightBalanced(tree)
    return (tree is empty) or 
           (IsHeightBalanced(tree.left) and
            IsHeightBalanced(tree.right) and
            abs(Height(tree.left) - Height(tree.right)) <= 1)

Traducir eso al lenguaje de programación de su elección debería ser trivial.

Ejercicio adicional : este boceto de código ingenuo atraviesa el árbol demasiadas veces al calcular las alturas. ¿Puedes hacerlo más eficiente?

Ejercicio de súper bonificación : supongamos que el árbol está enormemente desequilibrado. Como, un millón de nodos de profundidad en un lado y tres de profundidad en el otro. ¿Existe un escenario en el que este algoritmo arruine la pila? ¿Puede arreglar la implementación para que nunca arruine la pila, incluso cuando se le da un árbol enormemente desequilibrado?

ACTUALIZACIÓN : Donal Fellows señala en su respuesta que existen diferentes definiciones de "equilibrado" que se pueden elegir. Por ejemplo, se podría tomar una definición más estricta de "altura equilibrada", y requerir que la longitud del camino al niño vacío más cercano esté dentro de uno de los caminos al niño vacío más lejano . Mi definición es menos estricta que eso y, por lo tanto, admite más árboles.

También se puede ser menos estricto que mi definición; se podría decir que un árbol equilibrado es aquel en el que la longitud máxima del camino a un árbol vacío en cada rama no difiere en más de dos, tres o alguna otra constante. O que la longitud máxima de la ruta es una fracción de la longitud mínima de la ruta, como la mitad o un cuarto.

Realmente no importa por lo general. El objetivo de cualquier algoritmo de equilibrio de árboles es garantizar que no termines en la situación en la que tienes un millón de nodos en un lado y tres en el otro. La definición de Donal está bien en teoría, pero en la práctica es un fastidio crear un algoritmo de equilibrio de árboles que cumpla con ese nivel de rigor. Los ahorros de rendimiento generalmente no justifican el costo de implementación. Pasas mucho tiempo haciendo reordenamientos innecesarios de los árboles para lograr un nivel de equilibrio que en la práctica hace poca diferencia. ¿A quién le importa si a veces se necesitan cuarenta ramas para llegar a la hoja más lejana de un árbol con un equilibrio imperfecto de un millón de nodos cuando, en teoría, sólo podrían tomar veinte en un árbol perfectamente equilibrado? El caso es que nunca se necesita un millón. Pasar del peor de los casos de un millón al peor de los cuarenta suele ser suficiente; no tiene que ir hasta el caso óptimo.

El equilibrio es una propiedad verdaderamente sutil; cree que sabe lo que es, pero es muy fácil equivocarse. En particular, incluso la (buena) respuesta de Eric Lippert es incorrecta. Eso es porque la noción de altura no es suficiente. Necesitas tener el concepto de alturas mínimas y máximas de un árbol (donde la altura mínima es el menor número de pasos desde la raíz hasta una hoja, y el máximo es ... bueno, te haces una idea). Dado eso, podemos definir el equilibrio como:

Un árbol donde la altura máxima de cualquier rama no es más de uno más que la altura mínima de cualquier rama.

(En realidad, esto implica que las ramas están equilibradas; puede elegir la misma rama tanto para el máximo como para el mínimo).

Todo lo que necesita hacer para verificar esta propiedad es un simple recorrido de árbol que realiza un seguimiento de la profundidad actual. La primera vez que retrocede, eso le da una profundidad de referencia. Cada vez que retrocede, compara la nueva profundidad con la línea de base

• si es igual a la línea de base, entonces continúe
• si es más de uno diferente, el árbol no está equilibrado
• si es único, ahora conoce el rango para el equilibrio, y todas las profundidades posteriores (cuando esté a punto de retroceder) deben ser el primer o el segundo valor.

En codigo:

class Tree {
    Tree left, right;
    static interface Observer {
        public void before();
        public void after();
        public boolean end();
    }
    static boolean traverse(Tree t, Observer o) {
        if (t == null) {
            return o.end();
        } else {
            o.before();
            try {
                if (traverse(left, o))
                    return traverse(right, o);
                return false;
            } finally {
                o.after();
            }
        }
    }
    boolean balanced() {
        final Integer[] heights = new Integer[2];
        return traverse(this, new Observer() {
            int h;
            public void before() { h++; }
            public void after() { h--; }
            public boolean end() {
                if (heights[0] == null) {
                    heights[0] = h;
                } else if (Math.abs(heights[0] - h) > 1) {
                    return false;
                } else if (heights[0] != h) {
                    if (heights[1] == null) {
                        heights[1] = h;
                    } else if (heights[1] != h) {
                        return false;
                    }
                }
                return true;
            }
        });
    }
}

Supongo que podrías hacer esto sin usar el patrón Observer, pero me resulta más fácil razonar de esta manera.

[EDITAR]: Por qué no puedes simplemente tomar la altura de cada lado. Considere este árbol:

        /\
       /  \
      /    \
     /      \_____
    /\      /     \_
   /  \    /      / \
  /\   C  /\     /   \
 /  \    /  \   /\   /\
A    B  D    E F  G H  J

OK, un desordenado poco, pero cada lado de la raíz es equilibrado: Ces la profundidad 2, A, B, D, Eson la profundidad de 3, y F, G, H, Json la profundidad 4. La altura de la rama izquierda es 2 (recuerde la altura disminuye a medida que atraviesan la rama), la altura de la rama derecha es 3. Sin embargo, el árbol en general no está equilibrado ya que hay una diferencia de altura de 2 entre Cy F. Necesita una especificación minimax (aunque el algoritmo real puede ser menos complejo, ya que solo debería haber dos alturas permitidas).

Esto solo determina si el nivel superior del árbol está equilibrado. Es decir, podría tener un árbol con dos ramas largas en el extremo izquierdo y el extremo derecho, sin nada en el medio, y esto volvería a ser cierto. Debe comprobar de forma recursiva los root.lefty root.rightpara ver si también están equilibrados internamente antes de volver a verdadero.

Respuesta adicional al ejercicio. La solución simple. Obviamente, en una implementación real, uno podría ajustar esto o algo para evitar que el usuario incluya la altura en su respuesta.

IsHeightBalanced(tree, out height)
    if (tree is empty)
        height = 0
        return true
    balance = IsHeightBalanced(tree.left, heightleft) and IsHeightBalanced(tree.right, heightright)
    height = max(heightleft, heightright)+1
    return balance and abs(heightleft - heightright) <= 1     

Solución posterior al pedido, atraviesa el árbol solo una vez. La complejidad del tiempo es O (n), el espacio es O (1), es mejor que la solución de arriba hacia abajo. Te doy una implementación de la versión java.

public static <T> boolean isBalanced(TreeNode<T> root){
    return checkBalance(root) != -1;
}

private static <T> int checkBalance(TreeNode<T> node){
    if(node == null) return 0;
    int left = checkBalance(node.getLeft());

    if(left == -1) return -1;

    int right = checkBalance(node.getRight());

    if(right == -1) return -1;

    if(Math.abs(left - right) > 1){
        return -1;
    }else{
        return 1 + Math.max(left, right);
    }
}

La definición de un árbol binario de altura equilibrada es:

Árbol binario en el que la altura de los dos subárboles de cada nodo nunca difiere en más de 1.

Entonces, un árbol binario vacío siempre está equilibrado en altura.
Un árbol binario no vacío está equilibrado en altura si:

1. Su subárbol izquierdo está equilibrado en altura.
2. Su subárbol derecho está equilibrado en altura.
3. La diferencia entre las alturas del subárbol izquierdo y derecho no es mayor que 1.

Considere el árbol:

    A
     \ 
      B
     / \
    C   D

Como se ve, el subárbol izquierdo de Aestá equilibrado en altura (ya que está vacío) y también su subárbol derecho. Pero aún así, el árbol no está equilibrado en altura, ya que no se cumple la condición 3, ya que la altura del subárbol izquierdo es 0y la altura del subárbol derecho 2.

Además, el siguiente árbol no está equilibrado en altura a pesar de que la altura del subárbol izquierdo y derecho son iguales. Su código existente devolverá verdadero para él.

       A
     /  \ 
    B    C
   /      \
  D        G
 /          \
E            H

Así que la palabra todos en la definición es muy importante.

Esto funcionará:

int height(treeNodePtr root) {
        return (!root) ? 0: 1 + MAX(height(root->left),height(root->right));
}

bool isHeightBalanced(treeNodePtr root) {
        return (root == NULL) ||
                (isHeightBalanced(root->left) &&
                isHeightBalanced(root->right) &&
                abs(height(root->left) - height(root->right)) <=1);
}

Enlace ideone

Si el árbol binario está equilibrado o no, se puede verificar mediante el cruce de orden de nivel:

private boolean isLeaf(TreeNode root) {
    if (root.left == null && root.right == null)
        return true;
    return false;
}

private boolean isBalanced(TreeNode root) {
    if (root == null)
        return true;
    Vector<TreeNode> queue = new Vector<TreeNode>();
    int level = 1, minLevel = Integer.MAX_VALUE, maxLevel = Integer.MIN_VALUE;
    queue.add(root);
    while (!queue.isEmpty()) {
        int elementCount = queue.size();
        while (elementCount > 0) {
            TreeNode node = queue.remove(0);
            if (isLeaf(node)) {
                if (minLevel > level)
                    minLevel = level;
                if (maxLevel < level)
                    maxLevel = level;
            } else {
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
            elementCount--;
        }
        if (abs(maxLevel - minLevel) > 1) {
            return false;
        }
        level++;
    }

    return true;
}

Esto se está volviendo mucho más complicado de lo que realmente es.

El algoritmo es como sigue:

1. Sea A = profundidad del nodo de nivel más alto

2. Sea B = profundidad del nodo de nivel más bajo

3. Si abs (AB) <= 1, entonces el árbol está equilibrado

Lo que significa equilibrado depende un poco de la estructura en cuestión. Por ejemplo, un árbol B no puede tener nodos a más de una cierta profundidad desde la raíz, o menos, todos los datos viven a una profundidad fija desde la raíz, pero puede estar desequilibrado si la distribución de hojas a hojas -pero uno de los nodos es desigual. Listas de omisión No tienen ninguna noción de equilibrio, confiando en cambio en la probabilidad para lograr un desempeño decente. Los árboles de Fibonacci se desequilibran a propósito, posponiendo el reequilibrio para lograr un rendimiento asintótico superior a cambio de actualizaciones ocasionalmente más largas. Los árboles AVL y Red-Black adjuntan metadatos a cada nodo para lograr un invariante de equilibrio de profundidad.

Todas estas estructuras y más están presentes en las bibliotecas estándar de los sistemas de programación más comunes (¡excepto python, RAGE!). Implementar uno o dos es una buena práctica de programación, pero probablemente no sea un buen uso del tiempo para lanzar el suyo propio para la producción, a menos que su problema tenga un rendimiento peculiar que no necesite ser satisfecho por ninguna colección estándar.

Nota 1: La altura de cualquier subárbol se calcula solo una vez.

Nota 2: Si el subárbol izquierdo no está equilibrado, se omite el cálculo del subárbol derecho, que potencialmente contiene millones de elementos.

// return height of tree rooted at "tn" if, and only if, it is a balanced subtree
// else return -1
int maxHeight( TreeNode const * tn ) {
    if( tn ) {
        int const lh = maxHeight( tn->left );
        if( lh == -1 ) return -1;
        int const rh = maxHeight( tn->right );
        if( rh == -1 ) return -1;
        if( abs( lh - rh ) > 1 ) return -1;
        return 1 + max( lh, rh );
    }
    return 0;
}

bool isBalanced( TreeNode const * root ) {
    // Unless the maxHeight is -1, the subtree under "root" is balanced
    return maxHeight( root ) != -1;
}

El equilibrio generalmente depende de la longitud del camino más largo en cada dirección. El algoritmo anterior no lo hará por usted.

¿Qué estás intentando implementar? Hay árboles que se equilibran a sí mismos alrededor (AVL / Rojo-negro). De hecho, los árboles de Java están equilibrados.

Si esto es por su trabajo , sugiero:

1. no reinventes la rueda y
2. usar / comprar CUNAS lugar de jugar con bits.
3. Ahorre tiempo / energía para resolver problemas comerciales.

public boolean isBalanced(TreeNode root)
{
    return (maxDepth(root) - minDepth(root) <= 1);
}

public int maxDepth(TreeNode root)
{
    if (root == null) return 0;

    return 1 + max(maxDepth(root.left), maxDepth(root.right));
}

public int minDepth (TreeNode root)
{
    if (root == null) return 0;

    return 1 + min(minDepth(root.left), minDepth(root.right));
}

Aquí hay una solución completa probada resuelta en C # (lo siento, no soy un desarrollador de Java) (solo copie y pegue en la aplicación de consola). Sé que la definición de equilibrado varía, por lo que no a todos les pueden gustar los resultados de mi prueba, pero solo mire el enfoque ligeramente diferente de verificar la profundidad / altura en un bucle recursivo y salir en la primera discrepancia sin guardar la altura / nivel / profundidad del nodo en cada nodo (solo manteniéndolo en una llamada de función).

using System;
using System.Linq;
using System.Text;

namespace BalancedTree
{
    class Program
    {
        public static void Main()
        {
            //Value Gathering
            Console.WriteLine(RunTreeTests(new[] { 0 }));
            Console.WriteLine(RunTreeTests(new int[] { }));

            Console.WriteLine(RunTreeTests(new[] { 0, 1, 2, 3, 4, -1, -4, -3, -2 }));
            Console.WriteLine(RunTreeTests(null));
            Console.WriteLine(RunTreeTests(new[] { 10, 8, 12, 8, 4, 14, 8, 10 }));
            Console.WriteLine(RunTreeTests(new int[] { 20, 10, 30, 5, 15, 25, 35, 3, 8, 12, 17, 22, 27, 32, 37 }));

            Console.ReadKey();
        }

        static string RunTreeTests(int[] scores)
        {
            if (scores == null || scores.Count() == 0)
            {
                return null;
            }

            var tree = new BinarySearchTree();

            foreach (var score in scores)
            {
                tree.InsertScore(score);
            }

            Console.WriteLine(tree.IsBalanced());

            var sb = tree.GetBreadthWardsTraversedNodes();

            return sb.ToString(0, sb.Length - 1);
        }
    }

    public class Node
    {
        public int Value { get; set; }
        public int Count { get; set; }
        public Node RightChild { get; set; }
        public Node LeftChild { get; set; }
        public Node(int value)
        {
            Value = value;
            Count = 1;
        }

        public override string ToString()
        {
            return Value + ":" + Count;
        }

        public bool IsLeafNode()
        {
            return LeftChild == null && RightChild == null;
        }

        public void AddValue(int value)
        {
            if (value == Value)
            {
                Count++;
            }
            else
            {
                if (value > Value)
                {
                    if (RightChild == null)
                    {
                        RightChild = new Node(value);
                    }
                    else
                    {
                        RightChild.AddValue(value);
                    }
                }
                else
                {
                    if (LeftChild == null)
                    {
                        LeftChild = new Node(value);
                    }
                    else
                    {
                        LeftChild.AddValue(value);
                    }
                }
            }
        }
    }

    public class BinarySearchTree
    {
        public Node Root { get; set; }

        public void InsertScore(int score)
        {
            if (Root == null)
            {
                Root = new Node(score);
            }
            else
            {
                Root.AddValue(score);
            }
        }

        private static int _heightCheck;
        public bool IsBalanced()
        {
            _heightCheck = 0;
            var height = 0;
            if (Root == null) return true;
            var result = CheckHeight(Root, ref height);
            height--;
            return (result && height == 0);
        }

        private static bool CheckHeight(Node node, ref int height)
        {
            height++;
            if (node.LeftChild == null)
            {
                if (node.RightChild != null) return false;
                if (_heightCheck != 0) return _heightCheck == height;
                _heightCheck = height;
                return true;
            }
            if (node.RightChild == null)
            {
                return false;
            }

            var leftCheck = CheckHeight(node.LeftChild, ref height);
            if (!leftCheck) return false;
            height--;
            var rightCheck = CheckHeight(node.RightChild, ref height);
            if (!rightCheck) return false;
            height--;
            return true;
        }


        public StringBuilder GetBreadthWardsTraversedNodes()
        {
            if (Root == null) return null;
            var traversQueue = new StringBuilder();
            traversQueue.Append(Root + ",");
            if (Root.IsLeafNode()) return traversQueue;
            TraversBreadthWards(traversQueue, Root);
            return traversQueue;
        }

        private static void TraversBreadthWards(StringBuilder sb, Node node)
        {
            if (node == null) return;
            sb.Append(node.LeftChild + ",");
            sb.Append(node.RightChild + ",");
            if (node.LeftChild != null && !node.LeftChild.IsLeafNode())
            {
                TraversBreadthWards(sb, node.LeftChild);
            }
            if (node.RightChild != null && !node.RightChild.IsLeafNode())
            {
                TraversBreadthWards(sb, node.RightChild);
            }
        }
    }
}

#include <iostream>
#include <deque>
#include <queue>

struct node
{
    int data;
    node *left;
    node *right;
};

bool isBalanced(node *root)
{
    if ( !root)
    {
        return true;
    }

    std::queue<node *> q1;
    std::queue<int>  q2;
    int level = 0, last_level = -1, node_count = 0;

    q1.push(root);
    q2.push(level);

    while ( !q1.empty() )
    {
        node *current = q1.front();
        level = q2.front();

        q1.pop();
        q2.pop();

        if ( level )
        {
            ++node_count;
        }

                if ( current->left )
                {
                        q1.push(current->left);
                        q2.push(level + 1);
                }

                if ( current->right )
                {
                        q1.push(current->right);
                        q2.push(level + 1);
                }

        if ( level != last_level )
        {
            std::cout << "Check: " << (node_count ? node_count - 1 : 1) << ", Level: " << level << ", Old level: " << last_level << std::endl;
            if ( level && (node_count - 1) != (1 << (level-1)) )
            {
                return false;
            }

            last_level = q2.front();
            if ( level ) node_count = 1;
        }
    }

    return true;
}

int main()
{
    node tree[15];

    tree[0].left  = &tree[1];
    tree[0].right = &tree[2];
    tree[1].left  = &tree[3];
    tree[1].right = &tree[4];
    tree[2].left  = &tree[5];
    tree[2].right = &tree[6];
    tree[3].left  = &tree[7];
    tree[3].right = &tree[8];
    tree[4].left  = &tree[9];   // NULL;
    tree[4].right = &tree[10];  // NULL;
    tree[5].left  = &tree[11];  // NULL;
    tree[5].right = &tree[12];  // NULL;
    tree[6].left  = &tree[13];
    tree[6].right = &tree[14];
    tree[7].left  = &tree[11];
    tree[7].right = &tree[12];
    tree[8].left  = NULL;
    tree[8].right = &tree[10];
    tree[9].left  = NULL;
    tree[9].right = &tree[10];
    tree[10].left = NULL;
    tree[10].right= NULL;
    tree[11].left = NULL;
    tree[11].right= NULL;
    tree[12].left = NULL;
    tree[12].right= NULL;
    tree[13].left = NULL;
    tree[13].right= NULL;
    tree[14].left = NULL;
    tree[14].right= NULL;

    std::cout << "Result: " << isBalanced(tree) << std::endl;

    return 0;
}

RE: La solución de @ lucky usa un BFS para hacer un recorrido de orden de nivel.

Atravesamos el árbol y mantenemos una referencia a vars min / max-level que describen el nivel mínimo en el que un nodo es una hoja.

Creo que la solución @lucky requiere una modificación. Como lo sugiere @codaddict, en lugar de verificar si un nodo es una hoja, debemos verificar si el hijo izquierdo o derecho es nulo (no ambos). De lo contrario, el algoritmo consideraría esto como un árbol equilibrado válido:

     1
    / \
   2   4
    \   \
     3   1

En Python:

def is_bal(root):
    if root is None:
        return True

    import queue

    Q = queue.Queue()
    Q.put(root)

    level = 0
    min_level, max_level = sys.maxsize, sys.minsize

    while not Q.empty():
        level_size = Q.qsize()

        for i in range(level_size):
            node = Q.get()

            if not node.left or node.right:
                min_level, max_level = min(min_level, level), max(max_level, level)

            if node.left:
                Q.put(node.left)
            if node.right:
                Q.put(node.right)

        level += 1

        if abs(max_level - min_level) > 1:
            return False

    return True

Esta solución debe satisfacer todas las estipulaciones provistas en la pregunta inicial, operando en O (n) tiempo y O (n) espacio. El desbordamiento de memoria se dirigiría al montón en lugar de soplar una pila de llamadas recursiva.

Alternativamente, podríamos atravesar inicialmente el árbol para calcular + las alturas máximas de caché para cada subárbol raíz de forma iterativa. Luego, en otra ejecución iterativa, verifique si las alturas en caché de los subárboles izquierdo y derecho para cada raíz nunca difieren en más de uno. Esto también se ejecutaría en el tiempo O (n) y el espacio O (n), pero de forma iterativa para no causar un desbordamiento de la pila.

Bueno, necesita una forma de determinar las alturas de la izquierda y la derecha, y si la izquierda y la derecha están equilibradas.

Y yo solo return height(node->left) == height(node->right);

En cuanto a escribir una heightfunción, lea: Comprendiendo la recursividad

¿De qué tipo de árbol estás hablando? Hay árboles que se equilibran por sí mismos . Verifique sus algoritmos donde determinan si necesitan reordenar el árbol para mantener el equilibrio.

Aquí hay una versión basada en un recorrido genérico de profundidad primero. Debe ser más rápido que la otra respuesta correcta y manejar todos los "desafíos" mencionados. Disculpas por el estilo, realmente no conozco Java.

Aún puede hacerlo mucho más rápido si regresa temprano si el máximo y el mínimo están configurados y tienen una diferencia> 1.

public boolean isBalanced( Node root ) {
    int curDepth = 0, maxLeaf = 0, minLeaf = INT_MAX;
    if ( root == null ) return true;
    while ( root != null ) {
        if ( root.left == null || root.right == null ) {
            maxLeaf = max( maxLeaf, curDepth );
            minLeaf = min( minLeaf, curDepth );
        }
        if ( root.left != null ) {
            curDepth += 1;
            root = root.left;
        } else {
            Node last = root;
            while ( root != null
             && ( root.right == null || root.right == last ) ) {
                curDepth -= 1;
                last = root;
                root = root.parent;
            }
            if ( root != null ) {
                curDepth += 1;
                root = root.right;
            }
        }
    }
    return ( maxLeaf - minLeaf <= 1 );
}

/* Returns true if Tree is balanced, i.e. if the difference between the longest path and the shortest path from the root to a leaf node is no more than than 1. This difference can be changed to any arbitrary positive number. */
boolean isBalanced(Node root) {
    if (longestPath(root) - shortestPath(root) > 1)
        return false;
    else
        return true;
}


int longestPath(Node root) {
    if (root == null);
        return 0;
    else {
        int leftPathLength = longestPath(root.left);
        int rightPathLength = longestPath(root.right);
        if (leftPathLength >= rightPathLength)
            return leftPathLength + 1;
        else
            return rightPathLength + 1;
    }
}

int shortestPath(Node root) {
    if (root == null);
        return 0;
    else {
        int leftPathLength = shortestPath(root.left);
        int rightPathLength = shortestPath(root.right);
        if (leftPathLength <= rightPathLength)
            return leftPathLength + 1;
        else
            return rightPathLength + 1;
    }
}

class Node {
    int data;
    Node left;
    Node right;

    // assign variable with constructor
    public Node(int data) {
        this.data = data;
    }
}

public class BinaryTree {

    Node root;

    // get max depth
    public static int maxDepth(Node node) {
        if (node == null)
            return 0;

        return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
    }

    // get min depth
    public static int minDepth(Node node) {
        if (node == null)
            return 0;

        return 1 + Math.min(minDepth(node.left), minDepth(node.right));
    }

    // return max-min<=1 to check if tree balanced
    public boolean isBalanced(Node node) {

        if (Math.abs(maxDepth(node) - minDepth(node)) <= 1)
            return true;

        return false;
    }

    public static void main(String... strings) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);


        if (tree.isBalanced(tree.root))
            System.out.println("Tree is balanced");
        else
            System.out.println("Tree is not balanced");
    }
}

Esto es lo que he probado para el ejercicio extra de Eric. Intento deshacerme de mis bucles recursivos y regresar tan pronto como encuentro que un subárbol no está equilibrado.

int heightBalanced(node *root){
    int i = 1;
    heightBalancedRecursive(root, &i);
    return i; 
} 

int heightBalancedRecursive(node *root, int *i){

    int lb = 0, rb = 0;

    if(!root || ! *i)  // if node is null or a subtree is not height balanced
           return 0;  

    lb = heightBalancedRecursive(root -> left,i);

    if (!*i)         // subtree is not balanced. Skip traversing the tree anymore
        return 0;

    rb = heightBalancedRecursive(root -> right,i)

    if (abs(lb - rb) > 1)  // not balanced. Make i zero.
        *i = 0;

    return ( lb > rb ? lb +1 : rb + 1); // return the current height of the subtree
}

public int height(Node node){
    if(node==null)return 0;
    else{
        int l=height(node.leftChild);
        int r=height(node.rightChild);
       return(l>r?l+1:r+1);

}}
public boolean balanced(Node n){

    int l= height(n.leftChild);
    int r= height(n.rightChild);

    System.out.println(l + " " +r);
    if(Math.abs(l-r)>1)
        return false;
    else 
        return true;
    }

Un árbol vacío tiene una altura equilibrada. Un árbol binario T no vacío se equilibra si:

1) El subárbol izquierdo de T está equilibrado

2) El subárbol derecho de T está equilibrado

3) La diferencia entre las alturas del subárbol izquierdo y el subárbol derecho no es más de 1.

/* program to check if a tree is height-balanced or not */
#include<stdio.h>
#include<stdlib.h>
#define bool int

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
  int data;
  struct node* left;
  struct node* right;
};

/* The function returns true if root is balanced else false
   The second parameter is to store the height of tree.  
   Initially, we need to pass a pointer to a location with value 
   as 0. We can also write a wrapper over this function */
bool isBalanced(struct node *root, int* height)
{
  /* lh --> Height of left subtree 
     rh --> Height of right subtree */   
  int lh = 0, rh = 0;  

  /* l will be true if left subtree is balanced 
    and r will be true if right subtree is balanced */
  int l = 0, r = 0;

  if(root == NULL)
  {
    *height = 0;
     return 1;
  }

  /* Get the heights of left and right subtrees in lh and rh 
    And store the returned values in l and r */   
  l = isBalanced(root->left, &lh);
  r = isBalanced(root->right,&rh);

  /* Height of current node is max of heights of left and 
     right subtrees plus 1*/   
  *height = (lh > rh? lh: rh) + 1;

  /* If difference between heights of left and right 
     subtrees is more than 2 then this node is not balanced
     so return 0 */
  if((lh - rh >= 2) || (rh - lh >= 2))
    return 0;

  /* If this node is balanced and left and right subtrees 
    are balanced then return true */
  else return l&&r;
}


/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */

/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
    struct node* node = (struct node*)
                                malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return(node);
}

int main()
{
  int height = 0;

  /* Constructed binary tree is
             1
           /   \
         2      3
       /  \    /
     4     5  6
    /
   7
  */   
  struct node *root = newNode(1);  
  root->left = newNode(2);
  root->right = newNode(3);
  root->left->left = newNode(4);
  root->left->right = newNode(5);
  root->right->left = newNode(6);
  root->left->left->left = newNode(7);

  if(isBalanced(root, &height))
    printf("Tree is balanced");
  else
    printf("Tree is not balanced");    

  getchar();
  return 0;
}

Complejidad del tiempo: O (n)

Para tener un mejor rendimiento, especialmente en árboles enormes, puede guardar la altura en cada nodo, por lo que es una compensación entre el espacio y el rendimiento:

class Node {
    Node left;
    Node right;
    int value;
    int height;
}

Ejemplo de implementación de la adición y lo mismo para la eliminación

void addNode(Node root,int v)
{    int height =0;
     while(root != null)
     {
         // Since we are adding new node so the height 
         // will increase by one in each node we will pass by
         root.height += 1;
         height++;
         else if(v > root.value){
            root = root.left();
            }
         else{
         root = root.right();
         }

     }

         height++;
         Node n = new Node(v , height);
         root = n;         
}
int treeMaxHeight(Node root)
{
 return Math.Max(root.left.height,root.right.height);
}

int treeMinHeight(Node root)
{
 return Math.Min(root.left.height,root.right.height);

}

Boolean isNodeBlanced(Node root)
{
   if (treeMaxHeight(root) - treeMinHeight(root) > 2)
       return false;

  return true;
}

Boolean isTreeBlanced (Node root)
{
    if(root == null || isTreeBalanced(root.left) && isTreeBalanced(root.right) && isNodeBlanced(root))
    return true;

  return false;

}

    static boolean isBalanced(Node root) {
    //check in the depth of left and right subtree
    int diff = depth(root.getLeft()) - depth(root.getRight());
    if (diff < 0) {
        diff = diff * -1;
    }
    if (diff > 1) {
        return false;
    }
    //go to child nodes
    else {
        if (root.getLeft() == null && root.getRight() == null) {
            return true;
        } else if (root.getLeft() == null) {
            if (depth(root.getRight()) > 1) {
                return false;
            } else {
                return true;
            }
        } else if (root.getRight() == null) {
            if (depth(root.getLeft()) > 1) {
                return false;
            } else {
                return true;
            }
        } else if (root.getLeft() != null && root.getRight() != null && isBalanced(root.getLeft()) && isBalanced(root.getRight())) {
            return true;
        } else {
            return false;
        }
    }
}

¿No funcionaría esto?

return ( ( Math.abs( size( root.left ) - size( root.right ) ) < 2 );

Cualquier árbol desequilibrado siempre fallaría en esto.