Como determinar se a tree binária está balanceada?

Já faz um tempo desde aqueles anos de escola. Consegui um emprego como especialista em TI em um hospital. Tentando se mover para fazer alguma programação real agora. Estou trabalhando em trees binárias agora, e fiquei me perguntando qual seria a melhor maneira de determinar se a tree é equilibrada em altura.

Eu estava pensando em algo ao longo disto:

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; } 

Esta é uma boa implementação? Ou eu estou esquecendo de alguma coisa?

Tropeçou nesta velha pergunta enquanto procurava por outra coisa. Percebo que você nunca recebeu uma resposta completa.

A maneira de resolver esse problema é começar escrevendo uma especificação para a function que você está tentando escrever.

Especificação: Diz-se que uma tree binária bem formada é “balanceada em altura” se (1) está vazia, ou (2) seus filhos esquerdo e direito são balanceados em altura e a altura da tree da esquerda está dentro de 1 altura da tree certa.

Agora que você tem a especificação, o código é trivial para escrever. Basta seguir a especificação:

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

Traduzir isso na linguagem de programação de sua escolha deve ser trivial.

Exercício bônus : este esboço de código ingênuo atravessa a tree muitas vezes ao calcular as alturas. Você pode torná-lo mais eficiente?

Super bônus : suponha que a tree esteja desequilibrada em massa . Tipo, um milhão de nós no fundo de um lado e três no fundo do outro. Existe um cenário em que esse algoritmo explode a pilha? Você pode consertar a implementação para que ela nunca estrague a pilha, mesmo quando for dada uma tree maciçamente desequilibrada?

UPDATE : Donal Fellows aponta em sua resposta que existem diferentes definições de 'equilíbrio' que se pode escolher. Por exemplo, pode-se ter uma definição mais estrita de "altura equilibrada" e exigir que o comprimento do caminho para o filho vazio mais próximo esteja dentro de um dos caminhos para o filho vazio mais distante . Minha definição é menos rigorosa do que isso e, portanto, admite mais trees.

Pode-se também ser menos estrito que minha definição; Pode-se dizer que uma tree balanceada é aquela em que o comprimento máximo do caminho para uma tree vazia em cada ramo difere em não mais do que duas, ou três, ou alguma outra constante. Ou que o comprimento máximo do caminho é uma fração do comprimento mínimo do caminho, como meio ou quarto.

Isso realmente não importa normalmente. O ponto de qualquer algoritmo de balanceamento de tree é garantir que você não acabe na situação em que você tem um milhão de nós em um lado e três no outro. A definição de Donal é boa na teoria, mas na prática é uma dor surgir com um algoritmo de balanceamento de tree que atende a esse nível de rigidez. A economia de desempenho geralmente não justifica o custo de implementação. Você gasta muito tempo fazendo rearranjos desnecessários de trees para atingir um nível de equilíbrio que, na prática, faz pouca diferença. Quem se importa se, às vezes, são necessários quarenta ramos para chegar à folha mais distante de uma tree equilibrada imperfeitamente com um milhão de nós, quando, em teoria, ela poderia levar apenas vinte em uma tree perfeitamente equilibrada? O ponto é que nunca leva um milhão. Começar do pior caso de um milhão até o pior dos quarenta é geralmente bom o suficiente; você não precisa ir até o ótimo caso.

O equilíbrio é uma propriedade verdadeiramente sutil; Você acha que sabe o que é, mas é tão fácil errar. Em particular, até mesmo a resposta (boa) de Eric Lippert está desligada. Isso porque a noção de altura não é suficiente. Você precisa ter o conceito de altura mínima e máxima de uma tree (onde a altura mínima é o menor número de passos da raiz até a folha, e o máximo é … bem, você obtém a imagem). Dado que podemos definir o equilíbrio como:

Uma tree na qual a altura máxima de qualquer ramificação não é maior do que a altura mínima de qualquer ramificação.

(Isso realmente implica que os ramos estão equilibrados; você pode escolher o mesmo ramo tanto para o máximo quanto para o mínimo.)

Tudo o que você precisa fazer para verificar essa propriedade é uma simples travessia de tree, mantendo o controle da profundidade atual. A primeira vez que você voltar, isso lhe dá uma profundidade de linha de base. Cada vez que você recuar, compare a nova profundidade com a linha de base

  • se é igual à linha de base, então você continua
  • se é mais do que um diferente, a tree não é balanceada
  • se estiver desativado, você saberá o intervalo de equilíbrio e todas as profundidades subsequentes (quando estiver prestes a voltar atrás) devem ser o primeiro ou o segundo valor.

Em código:

 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; } }); } } 

Eu suponho que você poderia fazer isso sem usar o padrão Observer, mas acho mais fácil raciocinar dessa maneira.


[EDIT]: Por que você não pode simplesmente pegar a altura de cada lado. Considere esta tree:

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

OK, um pouco confuso, mas cada lado da raiz é equilibrado: C é profundidade 2, A , B , D , E são profundidade 3, e F , G , H , J são profundidade 4. A altura do ramo esquerdo é 2 (lembre-se que a altura diminui à medida que você atravessa o twig), a altura do twig direito é 3. Ainda assim, a tree geral não está equilibrada, pois há uma diferença na altura de 2 entre C e F Você precisa de uma especificação minimax (embora o algoritmo real possa ser menos complexo, pois deve haver apenas duas alturas permitidas).

Resposta ao exercício bônus. A solução simples. Obviamente, em uma implementação real, pode-se envolver isso ou algo para evitar que o usuário inclua altura em sua resposta.

 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 

Isso só determina se o nível superior da tree está balanceado. Ou seja, você poderia ter uma tree com dois twigs longos longe da esquerda e da extrema direita, sem nada no meio, e isso retornaria verdadeiro. Você precisa verificar recursivamente o root.left e o root.right para ver se eles também são balanceados internamente antes de retornar true.

Pós solução de pedido, percorra a tree apenas uma vez. A complexidade do tempo é O (n), o espaço é O (1), é melhor que a solução de cima para baixo. Eu dou a você uma implementação da versão 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); } } 

A definição de uma tree binária com equilíbrio de altura é:

Árvore binária na qual a altura das duas subtrees de cada nó nunca difere em mais de 1.

Então, uma tree binária vazia é sempre equilibrada em altura.
Uma tree binária não vazia é equilibrada em altura se:

  1. Sua subtree esquerda é equilibrada em altura.
  2. Sua subtree direita é balanceada em altura.
  3. A diferença entre as alturas da subtree esquerda e direita não é maior que 1.

Considere a tree:

  A \ B / \ CD 

Como visto, a subtree esquerda de A é equilibrada em altura (como está vazia) e assim é sua subtree direita. Mas ainda assim a tree não é balanceada em altura, pois a condição 3 não é atendida, pois a altura da subtree esquerda é 0 e a altura da subtree direita é 2 .

Além disso, a tree a seguir não tem altura equilibrada, embora a altura da subtree esquerda e direita seja igual. Seu código existente retornará verdadeiro para ele.

  A / \ BC / \ DG / \ EH 

Então a palavra todo na def é muito importante.

Isso vai 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); } 

Link Ideone

Isso está sendo muito mais complicado do que realmente é.

O algoritmo é o seguinte:

  1. Seja A = profundidade do nó de nível mais alto
  2. Seja B = profundidade do nó de nível mais baixo

  3. Se abs (AB) <= 1, então a árvore está balanceada

O que significa equilibrado depende um pouco da estrutura em mãos. Por exemplo, Uma Árvore B não pode ter nós a mais de uma certa profundidade da raiz, ou menos, todos os dados vivem a uma profundidade fixa a partir da raiz, mas pode estar desequilibrado se a distribuição das folhas às folhas Mas um nós é desigual. Listas de pulos Não têm noção de equilíbrio, confiando na probabilidade de alcançar um desempenho decente. As trees de Fibonacci propositalmente desequilibram, adiando o reequilíbrio para alcançar um desempenho assintótico superior em troca de atualizações ocasionalmente mais longas. As trees AVL e Red-Black anexam metadados a cada nó para obter uma invariante de balanço de profundidade.

Todas essas estruturas e mais estão presentes nas bibliotecas padrão dos sistemas de programação mais comuns (exceto python, RAGE!). A implementação de uma ou duas é uma boa prática de programação, mas provavelmente não é um bom uso do tempo para criar a sua própria para produção, a menos que seu problema tenha algum desempenho peculiar que não precise ser atendido por nenhuma coleção disponível no mercado.

Se a tree binária estiver balanceada ou não puder ser verificada por meio da passagem de ordem de nível:

 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: A altura de qualquer sub-tree é calculada apenas uma vez.

Nota 2: Se a subtree esquerda estiver desequilibrada, o cálculo da subtree direita, potencialmente contendo milhões de elementos, será ignorado.

 // 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; } 

O balanceamento geralmente depende do comprimento do caminho mais longo em cada direção. O algoritmo acima não vai fazer isso por você.

O que você está tentando implementar? Existem trees de auto-equilíbrio ao redor (AVL / Vermelho-preto). Na verdade, as trees Java são balanceadas.

Se isso é para o seu trabalho , sugiro:

  1. não reinventar a roda e
  2. use / compre COTS em vez de mexer nos bits.
  3. Economize seu tempo / energia para resolver problemas de negócios.
 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)); } 

Aqui está uma solução completa testada em C # (desculpe, eu não sou java dev) (apenas copie e cole no aplicativo de console). Eu sei que a definição de balanceamento varia, então nem todos podem gostar dos resultados dos testes, mas por favor, olhem a abordagem ligeiramente diferente de verificar profundidade / altura em um loop recursivo e sair na primeira incompatibilidade sem salvar a altura / nível / profundidade do nó em cada nó (somente mantendo-o em uma chamada de function).

 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[] scolors) { if (scolors == null || scolors.Count() == 0) { return null; } var tree = new BinarySearchTree(); foreach (var score in scolors) { 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; } 

Bem, você precisa de uma maneira de determinar as alturas esquerda e direita, e se esquerda e direita estão equilibradas.

E eu acabei de return height(node->left) == height(node->right);

Quanto a escrever uma function de height , leia: Entendendo a recursion

De que tipo de tree você está falando? Existem trees de auto-equilíbrio por aí. Verifique seus algoritmos onde eles determinam se precisam reordenar a tree para manter o equilíbrio.

Aqui está uma versão baseada em uma travessia genérica em profundidade. Deve ser mais rápido que a outra resposta correta e lidar com todos os “desafios” mencionados. Desculpas pelo estilo, eu realmente não conheço o Java.

Você ainda pode fazer isso muito mais rápido retornando mais cedo se max e min estiverem definidos e tiverem uma diferença> 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; } } 

Aqui está o que eu tentei para o exercício de bônus de Eric. Eu tento desanuviar meus loops recursivos e retornar assim que encontro uma subtree para não estar equilibrada.

 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; } 

Uma tree vazia é equilibrada em altura. Uma tree binária não vazia T é balanceada se:

1) A subtree esquerda de T é balanceada

2) A subtree direita de T é balanceada

3) A diferença entre as alturas da subtree esquerda e da subtree direita não é maior 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; } 

Complexidade do Tempo: O (n)

Para ter um desempenho melhor, especialmente em trees enormes, você pode salvar a altura em cada nó, por isso, é um desempenho de troca de espaço vs.

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

Exemplo de implementação da adição e da mesma para exclusão

 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; } } } 

Wouldn’t this work?

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

Any unbalanced tree would always fail this.