Checking balance of binary trees c++

Question

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

Answer 1

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.

Answer 2

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

Answer 3

Bartosz Pieszko Awesome ☺

Answer 4

Xan thank you 😉

Answer 5

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

Answer 6

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.

Answer 7

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

Answer 8

Can you paste the full code to SoloLearns?

Answer 9

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

Answer 10

Is Binario_t a pointer on rep_binario?

Answer 11

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

Answer 12

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

Answer 13

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

Answer 14

https://pastebin.com/9714pnbc

Answer 15

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

Answer 16

do you mean on dfs?