a binary tree is a special tree where each

Question

A binary tree is a special tree where each non-leaf node can have atmost two child nodes. Most important types of trees which are used to model yes/no, on/off, higher/lower, i.e., binary decisions are binary trees.

Recursive Definition: A binary tree is either empty or a node that has left and right sub-trees that are binary trees. Empty trees are represented as boxes (but we will almost always omit the boxes).

In a formal way, we can described binary tree as a finite set of nodes which is either empty or partitioned in to sets of T₀, T_l, T_r , where T₀ is the root and T_l and T_r are left and right binary trees, respectively.

Properties of a binary tree are following

• If a binary tree contains n nodes, then it have exactly n - 1 edges;
• A Binary tree of height h contains 2h - 1nodes or less.
• If we have a binary tree having n nodes, then the height of the tree is at most n and at least ceiling log₂(n + 1).
• If a binary tree contain n nodes at a level l then, it has at most 2n nodes at a level l+1
• The total number of nodes in binary tree with depth d (root has depth zero) is

                       N = 2⁰ + 2¹ + 2² + .......+ 2d = 2^d+1 - 1