Tree

Concepts

Complete Binary Tree: A complete binary tree is a binary tree in which every level of the tree is fully filled, except for perhaps the last level. To the extent that the last level is filled, it is filled left to right.

Full Binary Tree: A full binary tree is a binary tree in which every node has either 0 or 2 children.

Perfect Binary Tree: A perfect binary tree is one that is both full and complete. Every node has exactly 2 children.

Min-Heap: A min-heap is a complete binary tree where each node is smaller than its children.

Width of a level

662 Maximum Width of Binary Tree

                                0
                            -1     0
                          -3  -2 -1  0
KEY POINT        cur          = x
KEY POINT        leftChild    = x * 2 - 1
KEY POINT        rightChild   = x * 2
                 width = (rightChild - leftChild) + 1