Trusted answers to developer questions

AKASH BAJWA

A **binary tree** is a tree whose element or node can have a maximum of two children. Let’s look at this special case of trees and learn about their properties.

The following are the properties of the binary trees:

`h`

:In any binary tree, the minimum number of nodes will be one more than the value of `height`

. This is the number of nodes required to construct a tree.

**Formula**:

- Height =
`h`

. - The minimum number of nodes =
`h+1`

. - If
`h=3`

, then nodes will be`3+1= 4`

.

`h`

:The maximum number of nodes that can be inserted in any binary tree of height

will be equal to 2**h**^{h}- 1.

**Formula**:

- Height =
`h`

. - Maximum nodes to inserted = 2
^{h}- 1. - If
`h= 3`

, then 2^{3}- 1. `8 -1= 7`

.

Therefore, the maximum number of nodes to be inserted for the height of `h=3`

will be

.**7**

The number of leaf nodes in a binary tree is equal to the nodes with degree two, plus one. Say a binary tree has two children. Then the total number of leaf nodes of that binary tree will be one greater than the nodes having two children.

Total number of leaf nodes = Nodes with 2 children + 1

Here, the total number of leaf nodes (no child or a successor) is 3, and the leaf nodes are E, F, and G.

Whereas the nodes with two children are 2. Node A and** **B have 2 children. Hence, this proves the property.

Binary tree

In a binary tree, the maximum number of nodes gained by any level is equal to the power of 2 for that level.

In a simpler words, the level is donated by n. Then, maximum nodes of that binary tree will be 2^{n}.

**Example**:

n** = **2 then 2^{2}**= **4.

Level 2 coverts the nodes (D, E, F, and G).

Binary tree with maximum number of nodes at any level

This property says that the minimum number of levels or a height of a binary tree is the Log_{2} of (N+1). Here N represents the maximum number of nodes possessed by a binary tree at the height `h`

.

We have already discussed property 2 along with the example. Let's use that answer to calculate the height `h`

.

- N = 7 (Using Property#2)
- Log
_{2}of (N+1) = Log_{2}of (7+1) - Log
_{2}(8) = 3

It is equal to the height chosen in the example of property 2.

RELATED TAGS

properties

binary trees

communitycreator

CONTRIBUTOR

AKASH BAJWA

RELATED COURSES

View all Courses

Keep Exploring

Related Courses