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 odpowiedzi
+ 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?