Properties of Tree in Data Structure

Tag: Properties of Tree in Data Structure

Binary Tree | Binary Tree Properties

Data Structures

Binary Tree-

Before you go through this article, make sure that you gone through the previous article on Binary Trees.

We have discussed-

Binary tree is a special tree data structure.
In a binary tree, each node can have at most 2 children.
There are following types of binary trees-

In this article, we will discuss properties of binary trees.

Binary Tree Properties-

Important properties of binary trees are-

Property-01:

Minimum number of nodes in a binary tree of height H

= H + 1

Example-

To construct a binary tree of height = 4, we need at least 4 + 1 = 5 nodes.

Property-02:

Maximum number of nodes in a binary tree of height H

= 2^H+1 – 1

Example-

Maximum number of nodes in a binary tree of height 3

= 2³⁺¹ – 1

= 16 – 1

= 15 nodes

Thus, in a binary tree of height = 3, maximum number of nodes that can be inserted = 15.

We can not insert more number of nodes in this binary tree.

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-

Here,

Number of leaf nodes = 3
Number of nodes with 2 children = 2

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

This verifies the above relation.

NOTE

It is interesting to note that-

Number of leaf nodes in any binary tree depends only on the number of nodes with 2 children.

Property-04:

Maximum number of nodes at any level ‘L’ in a binary tree

= 2^L

Example-

Maximum number of nodes at level-2 in a binary tree

= 2²

= 4

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

To gain better understanding about Binary Tree Properties,

Watch this Video Lecture

PRACTICE PROBLEMS BASED ON BINARY TREE PROPERTIES-

Problem-01:

A binary tree T has n leaf nodes. The number of nodes of degree-2 in T is ______?

log₂n
n-1
n
2ⁿ

Solution-

Using property-3, we have-

Number of degree-2 nodes

= Number of leaf nodes – 1

= n – 1

Thus, Option (B) is correct.

Problem-02:

In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2. If the height of the tree is h > 0, then the minimum number of nodes in the tree is ______?

2^h-1
2^h-1 + 1
2^h – 1
2^h

Solution-

Let us assume any random value of h. Let h = 3.

Then the given options reduce to-

Now, consider the following binary tree with height h = 3-

This binary tree satisfies the question constraints.
It is constructed using minimum number of nodes.

Thus, Option (B) is correct.

Problem-03:

In a binary tree, the number of internal nodes of degree-1 is 5 and the number of internal nodes of degree-2 is 10. The number of leaf nodes in the binary tree is ______?

Solution-

Using property-3, we have-

Number of leaf nodes in a binary tree

= Number of degree-2 nodes + 1

= 10 + 1

= 11

Thus, Option (B) is correct.

Problem-04:

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is ______?

2^h
2^h-1 – 1
2^h+1 – 1
2^h+1

Solution-

Using property-2, Option (C) is correct.

Problem-05:

A binary tree T has 20 leaves. The number of nodes in T having 2 children is ______?

Solution-

Using property-3, correct answer is 19.

To watch video solutions and practice more problems,

Watch this Video Lecture

Download Handwritten Notes Here-

Next Article- Binary Tree Traversal

Get more notes and other study material of Data Structures.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Tree Data Structure | Tree Terminology

Data Structures

Tree Data Structure-

Tree data structure may be defined as-

Tree is a non-linear data structure which organizes data in a hierarchical structure and this is a recursive definition.

A tree is a connected graph without any circuits.

If in a graph, there is one and only one path between every pair of vertices, then graph is called as a tree.

Example-

Properties-

The important properties of tree data structure are-

There is one and only one path between every pair of vertices in a tree.
A tree with n vertices has exactly (n-1) edges.
A graph is a tree if and only if it is minimally connected.
Any connected graph with n vertices and (n-1) edges is a tree.

To gain better understanding about Tree Data Structure,

Watch this Video Lecture

Tree Terminology-

The important terms related to tree data structure are-

1. Root-

The first node from where the tree originates is called as a root node.
In any tree, there must be only one root node.
We can never have multiple root nodes in a tree data structure.

Example-

Here, node A is the only root node.

2. Edge-

The connecting link between any two nodes is called as an edge.
In a tree with n number of nodes, there are exactly (n-1) number of edges.

Example-

3. Parent-

The node which has a branch from it to any other node is called as a parent node.
In other words, the node which has one or more children is called as a parent node.
In a tree, a parent node can have any number of child nodes.

Example-

Here,

Node A is the parent of nodes B and C
Node B is the parent of nodes D, E and F
Node C is the parent of nodes G and H
Node E is the parent of nodes I and J
Node G is the parent of node K

4. Child-

The node which is a descendant of some node is called as a child node.
All the nodes except root node are child nodes.

Example-

Here,

Nodes B and C are the children of node A
Nodes D, E and F are the children of node B
Nodes G and H are the children of node C
Nodes I and J are the children of node E
Node K is the child of node G

5. Siblings-

Nodes which belong to the same parent are called as siblings.
In other words, nodes with the same parent are sibling nodes.

Example-

Here,

Nodes B and C are siblings
Nodes D, E and F are siblings
Nodes G and H are siblings
Nodes I and J are siblings

6. Degree-

Degree of a node is the total number of children of that node.
Degree of a tree is the highest degree of a node among all the nodes in the tree.

Example-

Here,

Degree of node A = 2
Degree of node B = 3
Degree of node C = 2
Degree of node D = 0
Degree of node E = 2
Degree of node F = 0
Degree of node G = 1
Degree of node H = 0
Degree of node I = 0
Degree of node J = 0
Degree of node K = 0

7. Internal Node-

The node which has at least one child is called as an internal node.
Internal nodes are also called as non-terminal nodes.
Every non-leaf node is an internal node.

Example-

Here, nodes A, B, C, E and G are internal nodes.

8. Leaf Node-

The node which does not have any child is called as a leaf node.
Leaf nodes are also called as external nodes or terminal nodes.

Example-

Here, nodes D, I, J, F, K and H are leaf nodes.

9. Level-

In a tree, each step from top to bottom is called as level of a tree.
The level count starts with 0 and increments by 1 at each level or step.

Example-

10. Height-

Total number of edges that lies on the longest path from any leaf node to a particular node is called as height of that node.
Height of a tree is the height of root node.
Height of all leaf nodes = 0

Example-

Here,

Height of node A = 3
Height of node B = 2
Height of node C = 2
Height of node D = 0
Height of node E = 1
Height of node F = 0
Height of node G = 1
Height of node H = 0
Height of node I = 0
Height of node J = 0
Height of node K = 0

11. Depth-

Total number of edges from root node to a particular node is called as depth of that node.
Depth of a tree is the total number of edges from root node to a leaf node in the longest path.
Depth of the root node = 0
The terms “level” and “depth” are used interchangeably.