MHB Finding Depth of Perfect & Complete Binary Trees

[evinda]

Hi! (Wave)

How can we find the depth of a perfect binary tree and how of a complete one? (Thinking)

Since a perfect binary tree is a full binary tree, at which the leaves have the same depth, I thought that we can find the depth, by just looking at the leftmost nodes, like that:

Algorithm(NODE *tree){
pointer p=tree;
int depth=0;
while (p!=NULL){
         p=p->next;
         depth++;
} 
return depth;
}

A complete binary tree of height $h$ consists of a perfect binary tree of height $h-1$, at which, one or more leaves with height $h$, have been added.
The leaves have been placed at the leftmost positions of the tree.

I thought that we could use again the above algorithm.

Am I right or have I done someething wrong? (Thinking)

 

[Ackbach]

Hi! (Wave)

How can we find the depth of a perfect binary tree and how of a complete one? (Thinking)

Since a perfect binary tree is a full binary tree, at which the leaves have the same depth, I thought that we can find the depth, by just looking at the leftmost nodes, like that:

Algorithm(NODE *tree){
pointer p=tree;
int depth=0;
while (p!=NULL){
         p=p->next;
         depth++;
} 
return depth;
}

A complete binary tree of height $h$ consists of a perfect binary tree of height $h-1$, at which, one or more leaves with height $h$, have been added.
The leaves have been placed at the leftmost positions of the tree.

I thought that we could use again the above algorithm.

Am I right or have I done someething wrong? (Thinking)

If the tree truly does have all its leaves at the same depth, this algorithm should work fine.

On the other hand, if you're not guaranteed a tree where all leaves are at the same depth, I don't see any way of computing the depth of the tree other than a full traversal.

[EDIT] You did mean

p = p->lc

, right?