Search

# Binary Tree | Introduction

Updated: Jun 29

A tree in which each node has at most two children, which are referred to as the left child and the right child.

There we can say that a binary tree node contains the following parts:

• Data

• Pointer to the left child

• Pointer to the right child

Properties of Binary Tree:

1. Property_01: Minimum number of nodes in the binary tree of height H = H+1

Property_1(Binary Tree)

2. Property_02:

Maximum no of nodes in a binary tree of height H = 2^(H+1)-1

Example:

Maximum number of nodes in a binary tree of height 2

= 2^(2+1) - 1

= 8 - 1

= 7

Thus, in a Binary tree of height = 2, the maximum number of nodes that can be inserted = 7.

Property_2 (Binary Tree)

3. Property_03:

Total number of leaf nodes in a Binary Tree

= Total number of nodes with 2 children + 1

Example:

Consider the following binary tree-

Property_3 (Binary Tree)

Here,

Number of leaf nodes = 4

Number of nodes with 2 children = 3

Clearly, the number of leaf nodes is greater than the number of nodes with 2 children.

4. Property_04:

Maximum number of nodes at any level 'L' in a binary tree = 2^L

Example:

The maximum number of nodes at level 2 in a binary tree.

= 2^2

= 4

Thus, in a binary tree, the maximum number of nodes that can be present at level 2 = 4

Property_4 (Binary Tree)

Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.

12 views

See All