## Binary tree and its properties

##
**Binary
tree**

A tree that can have at most two children (left and
right) for each node (internal) is called binary tree.

##
**Properties
of binary tree**

- A binary tree can be either empty (without any nodes), or consists of only one node (root node), or consists of a root node with two binary sub-trees called left sub-tree and right sub-tree.

- A binary tree with no nodes is called NULL tree.

- If h is the height of a binary tree,

- The tree can have maximum of 2
^{h}leaf nodes (leaves).

- The tree can have maximum of 2
^{h+1}-1 nodes (internal+external nodes)

- The minimum number of nodes is h+1.

- Minimum number of levels of a binary tree with N nodes
is ⌊log
_{2}N⌋+1 (flooring of log_{2}N+1)

- A binary tree with
L leaves have at least ⌊log
_{2}L⌋+1 levels

**Example:**All trees given in the following picture are binary trees;

**Height**of binary tree

**(a) is 1**,

**(b) is 1**,

**(c) is 2**,

**(d) is 2**,

**(e) is 1**,

**(f) is 2**, and

**(g) is 2**.

**Minimum number of nodes of a tree of height h**is h+1. Hence, a tree of

**height 0 must have at least 1 node**(0+1), a tree of

**height 1 must have at least 2 nodes**(1+1), a tree of

**height 2 must have at least 3 nodes**(2+1). For example, trees (a) and (b) both of height 1 have two nodes, trees (c) and (d) both of height 2 and have 3 nodes etc.

**Maximum number of nodes in a binary tree**can be 2

^{h+1}-1. In our example, binary tree (e) and (g) has maximum number of nodes. For (e), height is 1, so 2

^{1+1}-1 = 3 nodes. For (g), height is 2, so 2

^{2+1}-1 = 7 nodes.

**Minimum number of levels of a binary tree**with 2 nodes (figure (a) and (b)) should be at least ⌊log

_{2}N⌋ + 1, that is, 1 level. For the example in figure (g), the minimum number of levels is ⌊log

_{2}7⌋ + 1 = ⌊1.946⌋ + 1 = 1+1 = 2. [Note: use ln function in calculator]

*************

Go to Types of Binary Tree page

binary tree and its properties

height of a binary tree

minimum levels in a binary tree

minimum number of nodes in a binary tree

maximum number of nodes in a binary tree

binary tree examples

## No comments:

## Post a Comment