recursivo - recorrido por niveles arbol binario java
¿Cómo determinar si el árbol binario está equilibrado? (25)
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 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 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?
¿De qué tipo de árbol estás hablando? Hay árboles que se self-balancing . Verifique sus algoritmos donde determinan si necesitan reordenar el árbol para mantener el equilibrio.
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);
}
}
}
}
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 );
}
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
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 rama no es más que la altura mínima de cualquier rama.
(Esto en realidad implica que las ramas están en equilibrio, 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 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 // / /
/ / / / // //
A B D E F G H J
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 rama izquierda es 2 (recuerde que la altura disminuye a medida que atraviesa la rama), la altura de la rama 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).
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.
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
}
Esto se está haciendo mucho más complicado de lo que realmente es.
El algoritmo es como sigue:
- Deje A = profundidad del nodo de nivel más alto
Deje B = profundidad del nodo de nivel más bajo
Si abs (AB) <= 1, entonces el árbol está equilibrado
Esto solo determina si el nivel superior del árbol está equilibrado. Es decir, podrías tener un árbol con dos ramas 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.
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:
- Su subárbol izquierdo está equilibrado en altura.
- Su subárbol derecho tiene un equilibrio de altura.
- La diferencia entre las alturas del subárbol izquierdo y derecho no es mayor que 1.
Considera el árbol:
A
/
B
/ /
C D
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
/ /
B C
/ /
D G
/ /
E H
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);
}
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 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 hacer la producción propia, a menos que su problema tenga un rendimiento peculiar y no esté satisfecho con ninguna colección comercial.
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;
}
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;
}
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 <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);
}
}
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
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<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;
}
Si esto es para su trabajo , sugiero:
- no reinventar la rueda y
- use / compre COTS en lugar de juguetear con bits.
- Ahorre su tiempo / energía para resolver problemas comerciales.
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 programació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 pila? ¿Puedes arreglar la implementación para que nunca rompa la pila, 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 rama 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 objetivo 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 ramas 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.
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<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)
¿No funcionaría esto?
return ( ( Math.abs( size( root.left ) - size( root.right ) ) < 2 );
Cualquier árbol desequilibrado siempre fallaría esto.
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;
}
}
}
#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;
}
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;
}
}
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));
}
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;
}