0

I am studying binary tree now and I read that the definition of complete binary tree in CLRS' book "Introduction to algorithms, 3rd edition" is "A complete k-ary tree is a k-ary tree in which all leaves have the same depth and all internal nodes have degree k." (page 1178)

This makes me confused since in wikipedia and many other books this is the definition of so called "perfect binary tree". Can someone please specify which definition is true?

Really appreciate for your answer!

disccip
  • 573
  • 3
  • 5
  • 15
  • binary -> k=2. So one sentence is more generic than the other. [What Wiki thinks about it](https://en.wikipedia.org/wiki/K-ary_tree). – sascha Mar 18 '17 at 20:51
  • Sometimes a given concept has more than one name. This tends to happen when different fields, or different people within the same field, discover the same concept, but are initially unaware of each other's work. Even more fun is when the same term means entirely different things in different fields. It can lead to fun verbal exchanges such as "...so rho is the critical factor." "Say what?! What's correlation got to do with anything here?" "Huh? I said traffic intensity, not correlation!" – pjs Mar 18 '17 at 21:09
  • Questions about terminology are inherently subjective; language is descriptive, not prescriptive. Finding out how those terms are used most commonly is best answered by [research](https://meta.stackoverflow.com/questions/261592/how-much-research-effort-is-expected-of-stack-overflow-users) with a search engine, Wikipedia etc. This question should have been closed at the time. – Karl Knechtel Aug 07 '21 at 07:10

2 Answers2

1

It's the same thing.

According to Wikipedia:
A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level. (This is ambiguously also called a complete binary tree.)

https://en.wikipedia.org/wiki/Binary_tree

Ayon Nahiyan
  • 2,140
  • 15
  • 23
0

This definition is for a perfect k-ary tree. For a binary tree, the definition will be: "A perfect binary tree is a binary tree in which all leaves have the same depth and all internal nodes have degree 2."

However, for a complete binary tree, the definition is: all internal nodes have degree 2 but all leaves may not be in same depth.

This link may help you:
Difference between "Complete binary tree", "strict binary tree","full binary Tree"?

Shakhawat Hossain
  • 696
  • 5
  • 12