Binary tree and its properties in data structures

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₂N⌋+1 (flooring of log₂N+1)

• A binary tree with L leaves have at least ⌊log₂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 = 3 nodes. For (g), height is 2, so 2²⁺¹-1 = 7 nodes.

Minimum number of levels of a binary tree with 2 nodes (figure (a) and (b)) should be at least ⌊log₂N⌋ + 1, that is, 1 level. For the example in figure (g), the minimum number of levels is ⌊log₂7⌋ + 1 = ⌊1.946⌋ + 1 = 1+1 = 2. [Note: use ln function in calculator]

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

Go to Types of Binary Tree page

Go to Data structures main page  

Go to Tree Data Structure home 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