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

Ha pasado un tiempo desde esos años escolares. Conseguí un trabajo como especialista en TI en un hospital. Tratando de moverse para hacer algo de progtwigción real ahora. Ahora estoy trabajando en árboles binarios, y me preguntaba cuál sería la mejor manera de determinar si el árbol tiene equilibrio de 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?

Tropecé con esta vieja pregunta mientras buscaba otra cosa. Noté que nunca obtuviste 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 “equilibrio de altura” si (1) está vacío, o (2) sus hijos izquierdo y derecho tienen un equilibrio de altura y la altura del árbol izquierdo está dentro de 1 de la altura del árbol derecho.

Ahora que tiene la especificación, el código es trivial de escribir. Solo sigue la especificación:

 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 progtwigción que elijas debe ser trivial.

Ejercicio de bonificación : 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 profundos en un lado y tres profundos en el otro. ¿Hay un escenario en el que este algoritmo derriba la stack? ¿Puedes arreglar la implementación para que nunca rompa la stack, incluso cuando se le da un árbol enormemente desequilibrado?

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

Uno también 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 de la ruta a un árbol vacío en cada twig difiere en no 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 una mitad o un cuarto.

Realmente no importa por lo general. El objective de cualquier algoritmo de equilibrio de árboles es garantizar que no termines en una 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 dolor que viene con un algoritmo de equilibrio de árboles que cumple con ese nivel de rigor. Los ahorros en el rendimiento generalmente no justifican el costo de implementación. Pasas mucho tiempo haciendo reordenamientos de árboles innecesarios para alcanzar un nivel de equilibrio que en la práctica hace poca diferencia. ¿A quién le importa si a veces se necesitan cuarenta twigs para llegar a la hoja más alejada en un árbol con un millón de nódulos imperfectamente balanceados cuando en teoría podría tomar solo veinte en un árbol perfectamente equilibrado? El punto es que nunca lleva un millón. Pasar del peor de un millón al peor de los casos suele ser suficiente; no tienes que llegar al caso óptimo.

El equilibrio es una propiedad verdaderamente sutil; crees que sabes lo que es, pero es tan fácil equivocarse. En particular, incluso la (buena) respuesta de Eric Lippert está apagada. Eso es porque la noción de altura no es suficiente. Necesitas tener el concepto de alturas mínima y máxima 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, obtienes la imagen). Dado eso, podemos definir el equilibrio como:

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

(Esto en realidad implica que las twigs están en equilibrio, puede elegir la misma twig tanto para el máximo como para el mínimo).

Todo lo que necesita hacer para verificar esta propiedad es un cruce de árbol simple que rastrea la profundidad actual. La primera vez que retrocedes, eso te da una profundidad de referencia. Cada vez después de eso cuando retrocede, compara la nueva profundidad con la línea de base

  • si es igual a la línea de base, entonces simplemente continúa
  • si es más de uno diferente, el árbol no está equilibrado
  • si es uno, entonces ahora conoce el rango de equilibrio, y todas las profundidades posteriores (cuando está por 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 puedes 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. Considera este árbol:

  /\ / \ / \ / \_____ /\ / \_ / \ / / \ /\ C /\ / \ / \ / \ /\ /\ ABDEFGHJ 

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

Respuesta de ejercicio adicional. La solución simple. Obviamente, en una implementación real uno podría envolver esto o algo para evitar requerir 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 

Esto solo determina si el nivel superior del árbol está equilibrado. Es decir, podrías tener un árbol con dos twigs largas en el extremo izquierdo y el derecho, sin nada en el medio, y esto volvería a ser cierto. Necesita verificar recursivamente el root.left y el root.right para ver si también están balanceados internamente antes de volver verdadero.

Realice una solicitud de solución, atraviese el árbol solo una vez. La complejidad del tiempo es O (n), el espacio es O (1), es mejor que la solución descendente. Te doy una implementación de la versión java.

 public static  boolean isBalanced(TreeNode root){ return checkBalance(root) != -1; } private static  int checkBalance(TreeNode 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 tiene un equilibrio de altura.
Un árbol binario no vacío tiene un equilibrio de altura si:

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

Considera el árbol:

  A \ B / \ CD 

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

Además, el siguiente árbol no está equilibrado en altura, aunque la altura del subárbol izquierdo y derecho sea la misma. Su código actual será verdadero para eso.

  A / \ BC / \ DG / \ EH 

Entonces la palabra cada 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); } 

Ideone Link

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

El algoritmo es como sigue:

  1. Deje A = profundidad del nodo de nivel más alto
  2. Deje B = profundidad del nodo de nivel más bajo

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

Lo que significa equilibrio depende un poco de la estructura en cuestión. Por ejemplo, A B-Tree no puede tener nodos de más de 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 deja -pero-uno de los nodos es desigual. Omitir listas No tiene ninguna noción del equilibrio, confiando en cambio en la probabilidad de lograr un rendimiento decente. Los árboles de Fibonacci caen deliberadamente fuera de balance, posponiendo el reequilibrio para lograr un rendimiento asintótico superior a cambio de actualizaciones ocasionalmente más largas. Los árboles AVL y Rojo-Negro adjuntan metadatos a cada nodo para obtener un invariante de equilibrio de profundidad.

Todas estas estructuras y más están presentes en las bibliotecas estándar de los sistemas de progtwigción más comunes (¡excepto Python, RAGE!). Implementar uno o dos es una buena práctica de progtwigción, pero probablemente no sea un buen uso del tiempo para hacer la producción propia, a menos que su problema tenga un rendimiento peculiar y no esté satisfecho con ninguna colección comercial.

Si el árbol binario está equilibrado o no puede ser verificado por el recorrido de nivel 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 queue = new Vector(); 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; } 

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

Nota 2: si el subárbol izquierdo está desequilibrado, entonces se omite el cálculo del subárbol correcto, 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 va a hacer eso por ti.

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

Si esto es para su trabajo , sugiero:

  1. no reinventar la rueda y
  2. use / compre COTS en lugar de juguetear con bits.
  3. Ahorre su 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 y probada en C # (lo siento, no soy un desarrollador de java) (solo copie y pegue en la aplicación de la consola). Sé que la definición de equilibrado varía, por lo que no todos pueden agradar los resultados de la prueba, solo mire el enfoque ligeramente diferente de verificar la profundidad / altura en un ciclo 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  #include  #include  struct node { int data; node *left; node *right; }; bool isBalanced(node *root) { if ( !root) { return true; } std::queue q1; std::queue 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; } 

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

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

En cuanto a escribir una función de height , lea: Comprender la recursión

¿De qué tipo de árbol estás hablando? Hay árboles que se equilibran por sí solos . 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 en primer lugar. Debería 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.

Todavía puede hacer que sea mucho más rápido si regresa antes si max y min están establecidos 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 ); } 
 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; } } 

Esto es lo que he intentado para el ejercicio extra de Eric. Intento relajar mis bucles recursivos y regresar tan pronto como encuentro un subárbol que 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(lr)>1) return false; else return true; } 

Un árbol vacío tiene un equilibrio de altura. Un árbol binario no vacío T 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 mayor que 1.

 /* program to check if a tree is height-balanced or not */ #include #include #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 grandes, puede guardar la altura en cada nodo, por lo que se trata de un rendimiento Vs del espacio de compensación:

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

Ejemplo de implementación de la adición y lo mismo para 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 ); 

Any unbalanced tree would always fail this.