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

Depth of a node in binary tree

The depth of a node in a binary tree

Depth of a node

The depth of a node A in a binary tree is the length of the unique path (number of edges) from the root of the tree to the node A.

The root node is at the depth 0.

Example:

Depth of node K – 3 [edge AB (e1), edge BF (e4), and edge FK (e7)]

Depth of node I – 2 [edge AD (e2), and edge DI (e5)]

Depth of node J – 2 [edge AD (e2), and edge DJ (e6)]

Depth of node A – 0 [root node]

***********

Go to Data structures main page  

Go to Tree Data Structure home page

Go to Binary tree and its properties page

Depth of a node in data structure

Depth of a node in binary tree

Find the depth of a binary tree node

Examples for finding the depth of a binary tree

How to calculate the depth of a binary tree