0

# Checking balance of binary trees c++

is It posible to make a c++ function that checks if a binary tree is avl without accessing the same node more than once?

16 Answers

+ 3

Yes. It is possible using DFS algorithm. Try to run dfs on root of tree and recursive check the length of subtrees. It their lengths are different only by 1 on every vertex then it is avl.
struct node {
node * left, * right;
};
int dfs(node * u) {
int r1 = 0, r2 = 0;
if (u->left)
r1 = dfs(u->left);
if (u->right)
r2 = dfs(u->right);
if (r1 == -1 || r2 == -1)
return -1;
if (abs(r1 - r2) < 2)
return max(r1, r2);
else
return -1;
}
If this function returns -1 then it is not balanced tree. Otherwise, it is balanced.

+ 2

Yes. Making a tree balanced is more difficult, but checking it is balanced shouldn't need multiple node visitations!

+ 2

Bartosz Pieszko Awesome ☺

+ 1

Xan thank you 😉

0

thank you so much, but the Code isn't working for me. It always returns that it's a balanced tree.

0

Juan Casanova Ltaif Do you have static binary tree or dynamic allocated?
If it is static then you should change the code. However, I will check it in 1 hour because I'm going to train now.

0

It's dynamic allocated, thank you for your time.

0

Can you paste the full code to SoloLearns?

0

this is what I have so far
struct rep_binario {
info_t dato;
rep_binario *izq;//left
rep_binario *der;//right
};
bool es_vacio_binario(binario_t b) {
return (b == NULL);
}
static int dfs(binario_t b){
int r1 = 0, r2 = 0;
if (b->izq)
r1 = dfs(b->izq);
if (b->der)
r2 = dfs(b->der);
if(r1==-1||r2==-1)
return -1;
if(abs(r1-r2)<2)
return max(r1,r2);
else
return -1;
}
bool es_AVL(binario_t b) {//the function I need
if (es_vacio_binario(b))
return true;
else
return (dfs(b) != -1);
}

0

Is Binario_t a pointer on rep_binario?

0

It is indeed. Sorry for the chaos, I had to copy the relevant parts. It has over 20 different functions

0

Please paste code to pastebin.com and send link there if you can. I'll try to check what is wrong in 30 minutes

0

the other functions work fine, this one is the only one that I can't seem to work arround. Mainly because of the "can't acces the same node twice" thing but I can send the rest of the Code if needed

0

You should use pointers. Try change argument to rep_binario * b

0

do you mean on dfs?