Binary Tree

Properties of a binary tree

• If a binary tree contains n nodes, then it contains exactly n – 1 edges;
• A Binary tree of height h has 2h – 1nodes or less.
• If we have a binary tree containing n nodes, then the height of the tree is at most

  n and at least ceiling log2(n + 1).

• If a binary tree has n nodes at a level l then, it has at most 2n nodes at a level l+1
• The total number of nodes in a binary tree with depth d (root has depth zero) is N = 20 + 21 + 22 + …….+ 2d = 2d+1 – 1

  Full Binary Trees: A binary tree of height h which had 2h –1 elements is called a Full Binary Tree.

  Complete Binary Trees: A binary tree whereby if the height is d, and all levels, except possibly level d, are completely full. If the bottom level is incomplete, then it has all nodes to the left side. That is the tree has been filled in the level order from left to right.