# Finding Depth of Perfect & Complete Binary Trees

• MHB
• evinda
In summary, the conversation discusses how to find the depth of a perfect binary tree and a complete binary tree. The suggested algorithm for finding the depth of a perfect binary tree involves looking at the leftmost nodes. It is also mentioned that a complete binary tree consists of a perfect binary tree with additional leaves added at the leftmost positions. The same algorithm is suggested for finding the depth of a complete binary tree, but it is acknowledged that this may not work if the tree does not have all its leaves at the same depth. The conversation ends with questioning the correctness of the algorithm and suggesting a full traversal as an alternative.
evinda
Gold Member
MHB
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:

Code:
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)

evinda said:
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:

Code:
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
Code:
p = p->lc
, right?

## 1. What is a perfect binary tree?

A perfect binary tree is a type of binary tree in which every internal node has exactly two child nodes and all the leaves are at the same level. This means that the number of nodes at each level doubles as you move down the tree.

## 2. What is a complete binary tree?

A complete binary tree is a type of binary tree in which every level, except possibly the last, is completely filled and all the nodes are as far left as possible. The last level may not be filled from left to right, but all the nodes are filled from left to right.

## 3. How do you find the depth of a perfect binary tree?

The depth of a perfect binary tree is equal to the number of levels in the tree. Since the number of levels doubles as you move down the tree, the depth can be calculated using the formula log2n, where n is the number of nodes in the tree. For example, a perfect binary tree with 8 nodes will have a depth of 3 (log28 = 3).

## 4. How do you find the depth of a complete binary tree?

The depth of a complete binary tree can be found by counting the number of levels in the tree. Since all levels, except possibly the last, are completely filled, the depth will be equal to the number of levels. This can also be calculated using the formula log2n + 1, where n is the number of nodes in the tree.

## 5. Can a binary tree be both perfect and complete?

Yes, a binary tree can be both perfect and complete. This means that it has exactly two child nodes for every internal node and all the levels, except possibly the last, are completely filled. However, not all binary trees are perfect and complete. They are two different types of binary trees with specific characteristics.

• Programming and Computer Science
Replies
65
Views
9K
• Programming and Computer Science
Replies
4
Views
2K
• Programming and Computer Science
Replies
1
Views
1K
• Programming and Computer Science
Replies
2
Views
1K
• Programming and Computer Science
Replies
13
Views
4K
• Programming and Computer Science
Replies
40
Views
7K
• Programming and Computer Science
Replies
14
Views
3K
• Programming and Computer Science
Replies
4
Views
1K
• Programming and Computer Science
Replies
3
Views
3K
• Programming and Computer Science
Replies
1
Views
1K