222. Count Complete Tree Nodes
https://leetcode.com/problems/count-complete-tree-nodes/
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes at the last level h.[18] An alternative definition is a perfect tree whose rightmost leaves (perhaps all) have been removed. Some authors use the term complete to refer instead to a perfect binary tree as defined below, in which case they call this type of tree (with a possibly not filled last level) an almost complete binary tree or nearly complete binary tree.[19][20] A complete binary tree can be efficiently represented using an array.[18]
A complete binary tree (that is not full)
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.[21] An example of a perfect binary tree is the (non-incestuous) ancestry chart of a person to a given depth, as each person has exactly two biological parents (one mother and one father). Provided the ancestry chart always displays the mother and the father on the same side for a given node, their sex can be seen as an analogy of left and right children, children being understood here as an algorithmic term. A perfect tree is therefore always complete but a complete tree is not necessarily perfect.
Last updated
Was this helpful?