Category: Data Structures

Binary Tree | Types of Binary Trees

Data Structures

Tree Data Structure-

 

Before you go through this article, make sure that you have gone through the previous article on Tree Data Structure.

 

We have discussed-

  • Tree is a non-linear data structure.
  • In a tree data structure, a node can have any number of child nodes.

 

In this article, we will discuss about Binary Trees.

 

Binary Tree-

 

Binary tree is a special tree data structure in which each node can have at most 2 children.

Thus, in a binary tree,

Each node has either 0 child or 1 child or 2 children.

 

Example-

 

 

Unlabeled Binary Tree-

 

A binary tree is unlabeled if its nodes are not assigned any label.

 

 

 

Example-

 

Consider we want to draw all the binary trees possible with 3 unlabeled nodes.

Using the above formula, we have-

 

Number of binary trees possible with 3 unlabeled nodes

= 2 x 3C3 / (3 + 1)

= 6C3 / 4

= 5

 

Thus,

  • With 3 unlabeled nodes, 5 unlabeled binary trees are possible.
  • These unlabeled binary trees are as follows-

 

 

Labeled Binary Tree-

 

A binary tree is labeled if all its nodes are assigned a label.

 

 

 

Example-

 

Consider we want to draw all the binary trees possible with 3 labeled nodes.

Using the above formula, we have-

 

Number of binary trees possible with 3 labeled nodes

= { 2 x 3C3 / (3 + 1) } x 3!

= { 6C3 / 4 } x 6

= 5 x 6

= 30

 

Thus,

  • With 3 labeled nodes, 30 labeled binary trees are possible.
  • Each unlabeled structure gives rise to 3! = 6 different labeled structures.

 

 

Similarly,

  • Every other unlabeled structure gives rise to 6 different labeled structures.
  • Thus, in total 30 different labeled binary trees are possible.

 

Types of Binary Trees-

 

Binary trees can be of the following types-

 

 

  1. Rooted Binary Tree
  2. Full / Strictly Binary Tree
  3. Complete / Perfect Binary Tree
  4. Almost Complete Binary Tree
  5. Skewed Binary Tree

 

1. Rooted Binary Tree-

 

A rooted binary tree is a binary tree that satisfies the following 2 properties-

  • It has a root node.
  • Each node has at most 2 children.

 

Example-

 

 

2. Full / Strictly Binary Tree-

 

  • A binary tree in which every node has either 0 or 2 children is called as a Full binary tree.
  • Full binary tree is also called as Strictly binary tree.

 

Example-

 

 

Here,

  • First binary tree is not a full binary tree.
  • This is because node C has only 1 child.

 

3. Complete / Perfect Binary Tree-

 

A complete binary tree is a binary tree that satisfies the following 2 properties-

  • Every internal node has exactly 2 children.
  • All the leaf nodes are at the same level.

 

Complete binary tree is also called as Perfect binary tree.

 

Example-

 

 

Here,

  • First binary tree is not a complete binary tree.
  • This is because all the leaf nodes are not at the same level.

 

4. Almost Complete Binary Tree-

 

An almost complete binary tree is a binary tree that satisfies the following 2 properties-

  • All the levels are completely filled except possibly the last level.
  • The last level must be strictly filled from left to right.

 

Example-

 

 

Here,

  • First binary tree is not an almost complete binary tree.
  • This is because the last level is not filled from left to right.

 

5. Skewed Binary Tree-

 

A skewed binary tree is a binary tree that satisfies the following 2 properties-

  • All the nodes except one node has one and only one child.
  • The remaining node has no child.

OR

A skewed binary tree is a binary tree of n nodes such that its depth is (n-1).

 

Example-

 

 

To gain better understanding about Binary Tree and its types-

Watch this Video Lecture

 

Also Read- Binary Tree Traversal

 

Download Handwritten Notes Here-

 

 

Next Article- Binary Tree Properties

 

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.

OR

A tree is a connected graph without any circuits.

OR

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.

 

Example-

 

 

Here,

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

 

12. Subtree-

 

  • In a tree, each child from a node forms a subtree recursively.
  • Every child node forms a subtree on its parent node.

 

Example-

 

 

13. Forest-

 

A forest is a set of disjoint trees.

 

Example-

 

 

To gain better understanding about Tree Terminology,

Watch this Video Lecture

 

Download Handwritten Notes Here-

 

 

Next Article- Binary Tree | Types of Binary Trees

 

Get more notes and other study material of Data Structures.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Separate Chaining Vs Open Addressing

Data Structures

Collision Resolution Techniques-

 

In Hashing, collision resolution techniques are classified as-

 

 

  1. Separate Chaining
  2. Open Addressing

 

In this article, we will compare separate chaining and open addressing.

 

Separate Chaining Vs Open Addressing-

 

Separate Chaining

Open Addressing
Keys are stored inside the hash table as well as outside the hash table. All the keys are stored only inside the hash table.

No key is present outside the hash table.
The number of keys to be stored in the hash table can even exceed the size of the hash table. The number of keys to be stored in the hash table can never exceed the size of the hash table.
Deletion is easier. Deletion is difficult.
Extra space is required for the pointers to store the keys outside the hash table. No extra space is required.

Cache performance is poor.

This is because of linked lists which store the keys outside the hash table.

Cache performance is better.

This is because here no linked lists are used.

Some buckets of the hash table are never used which leads to wastage of space.

 Buckets may be used even if no key maps to those particular buckets.

 

Which is the Preferred Technique?

 

The performance of both the techniques depend on the kind of operations that are required to be performed on the keys stored in the hash table-

 

Separate Chaining-

 

Separate Chaining is advantageous when it is required to perform all the following operations on the keys stored in the hash table-

  • Insertion Operation
  • Deletion Operation
  • Searching Operation

 

NOTE-

 

  • Deletion is easier in separate chaining.
  • This is because deleting a key from the hash table does not affect the other keys stored in the hash table.

 

Open Addressing-

 

Open addressing is advantageous when it is required to perform only the following operations on the keys stored in the hash table-

  • Insertion Operation
  • Searching Operation

 

NOTE-

 

  • Deletion is difficult in open addressing.
  • This is because deleting a key from the hash table requires some extra efforts.
  • After deleting a key, certain keys have to be rearranged.

 

To gain better understanding about Separate Chaining Vs Open Addressing,

Watch this Video Lecture

 

Get more notes and other study material of Data Structures.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Open Addressing | Linear Probing | Collision

Data Structures

Collision Resolution Techniques-

 

Before you go through this article, make sure that you have gone through the previous article on Collision Resolution Techniques.

 

We have discussed-

  • Hashing is a well-known searching technique.
  • Collision occurs when hash value of the new key maps to an occupied bucket of the hash table.
  • Collision resolution techniques are classified as-

 

 

In this article, we will discuss about Open Addressing.

 

Open Addressing-

 

In open addressing,

  • Unlike separate chaining, all the keys are stored inside the hash table.
  • No key is stored outside the hash table.

 

Techniques used for open addressing are-

  • Linear Probing
  • Quadratic Probing
  • Double Hashing

 

Operations in Open Addressing-

 

Let us discuss how operations are performed in open addressing-

 

Insert Operation-

 

  • Hash function is used to compute the hash value for a key to be inserted.
  • Hash value is then used as an index to store the key in the hash table.

 

In case of collision,

  • Probing is performed until an empty bucket is found.
  • Once an empty bucket is found, the key is inserted.
  • Probing is performed in accordance with the technique used for open addressing.

 

Search Operation-

 

To search any particular key,

  • Its hash value is obtained using the hash function used.
  • Using the hash value, that bucket of the hash table is checked.
  • If the required key is found, the key is searched.
  • Otherwise, the subsequent buckets are checked until the required key or an empty bucket is found.
  • The empty bucket indicates that the key is not present in the hash table.

 

Delete Operation-

 

  • The key is first searched and then deleted.
  • After deleting the key, that particular bucket is marked as “deleted”.

 

NOTE-

 

  • During insertion, the buckets marked as “deleted” are treated like any other empty bucket.
  • During searching, the search is not terminated on encountering the bucket marked as “deleted”.
  • The search terminates only after the required key or an empty bucket is found.

 

Open Addressing Techniques-

 

Techniques used for open addressing are-

 

1. Linear Probing-

 

In linear probing,

  • When collision occurs, we linearly probe for the next bucket.
  • We keep probing until an empty bucket is found.

 

Advantage-

 

  • It is easy to compute.

 

Disadvantage-

 

  • The main problem with linear probing is clustering.
  • Many consecutive elements form groups.
  • Then, it takes time to search an element or to find an empty bucket.

 

Time Complexity-

 

Worst time to search an element in linear probing is O (table size).

 

This is because-

  • Even if there is only one element present and all other elements are deleted.
  • Then, “deleted” markers present in the hash table makes search the entire table.

 

2. Quadratic Probing-

 

In quadratic probing,

  • When collision occurs, we probe for i2‘th bucket in ith iteration.
  • We keep probing until an empty bucket is found.

 

3. Double Hashing-

 

In double hashing,

  • We use another hash function hash2(x) and look for i * hash2(x) bucket in ith iteration.
  • It requires more computation time as two hash functions need to be computed.

 

Comparison of Open Addressing Techniques-

 

Linear Probing
Quadratic Probing
Double Hashing
Primary Clustering
 Yes No No
Secondary Clustering
 Yes Yes No
Number of Probe Sequence
(m = size of table)
 m m m2
Cache performance
 Best Lies between the two Poor

 

Conclusions-

 

  • Linear Probing has the best cache performance but suffers from clustering.
  • Quadratic probing lies between the two in terms of cache performance and clustering.
  • Double caching has poor cache performance but no clustering.

 

Load Factor (α)-

 

Load factor (α) is defined as-

 

 

In open addressing, the value of load factor always lie between 0 and 1.

 

This is because-

  • In open addressing, all the keys are stored inside the hash table.
  • So, size of the table is always greater or at least equal to the number of keys stored in the table.

 

PRACTICE PROBLEM BASED ON OPEN ADDRESSING-

 

Problem-

 

Using the hash function ‘key mod 7’, insert the following sequence of keys in the hash table-

50, 700, 76, 85, 92, 73 and 101

 

Use linear probing technique for collision resolution.

 

Solution-

 

The given sequence of keys will be inserted in the hash table as-

 

Step-01:

 

  • Draw an empty hash table.
  • For the given hash function, the possible range of hash values is [0, 6].
  • So, draw an empty hash table consisting of 7 buckets as-

 

 

Step-02:

 

  • Insert the given keys in the hash table one by one.
  • The first key to be inserted in the hash table = 50.
  • Bucket of the hash table to which key 50 maps = 50 mod 7 = 1.
  • So, key 50 will be inserted in bucket-1 of the hash table as-

 

 

Step-03:

 

  • The next key to be inserted in the hash table = 700.
  • Bucket of the hash table to which key 700 maps = 700 mod 7 = 0.
  • So, key 700 will be inserted in bucket-0 of the hash table as-

 

 

Step-04:

 

  • The next key to be inserted in the hash table = 76.
  • Bucket of the hash table to which key 76 maps = 76 mod 7 = 6.
  • So, key 76 will be inserted in bucket-6 of the hash table as-

 

 

Step-05:

 

  • The next key to be inserted in the hash table = 85.
  • Bucket of the hash table to which key 85 maps = 85 mod 7 = 1.
  • Since bucket-1 is already occupied, so collision occurs.
  • To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
  • The first empty bucket is bucket-2.
  • So, key 85 will be inserted in bucket-2 of the hash table as-

 

 

Step-06:

 

  • The next key to be inserted in the hash table = 92.
  • Bucket of the hash table to which key 92 maps = 92 mod 7 = 1.
  • Since bucket-1 is already occupied, so collision occurs.
  • To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
  • The first empty bucket is bucket-3.
  • So, key 92 will be inserted in bucket-3 of the hash table as-

 

 

Step-07:

 

  • The next key to be inserted in the hash table = 73.
  • Bucket of the hash table to which key 73 maps = 73 mod 7 = 3.
  • Since bucket-3 is already occupied, so collision occurs.
  • To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
  • The first empty bucket is bucket-4.
  • So, key 73 will be inserted in bucket-4 of the hash table as-

 

 

Step-08:

 

  • The next key to be inserted in the hash table = 101.
  • Bucket of the hash table to which key 101 maps = 101 mod 7 = 3.
  • Since bucket-3 is already occupied, so collision occurs.
  • To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
  • The first empty bucket is bucket-5.
  • So, key 101 will be inserted in bucket-5 of the hash table as-

 

 

To gain better understanding about Open Addressing,

Watch this Video Lecture

 

Next Article- Separate Chaining Vs Open Addressing

 

Get more notes and other study material of Data Structures.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Separate Chaining | Collision Resolution Techniques

Data Structures

Hashing in Data Structure-

 

Before you go through this article, make sure that you have gone through the previous article on Hashing.

 

We have discussed-

  • Hashing is a well-known searching technique.
  • It minimizes the number of comparisons while performing the search.
  • It completes the search with constant time complexity O(1).

 

In this article, we will discuss about Collisions in Hashing.

 

Collision in Hashing-

 

In hashing,

  • Hash function is used to compute the hash value for a key.
  • Hash value is then used as an index to store the key in the hash table.
  • Hash function may return the same hash value for two or more keys.

 

When the hash value of a key maps to an already occupied bucket of the hash table,

it is called as a Collision.

 

Collision Resolution Techniques-

 

Collision Resolution Techniques are the techniques used for resolving or handling the collision.

 

Collision resolution techniques are classified as-

 

 

  1. Separate Chaining
  2. Open Addressing

 

In this article, we will discuss about separate chaining.

 

Separate Chaining-

 

To handle the collision,

  • This technique creates a linked list to the slot for which collision occurs.
  • The new key is then inserted in the linked list.
  • These linked lists to the slots appear like chains.
  • That is why, this technique is called as separate chaining.

 

Time Complexity-

 

For Searching-

 

  • In worst case, all the keys might map to the same bucket of the hash table.
  • In such a case, all the keys will be present in a single linked list.
  • Sequential search will have to be performed on the linked list to perform the search.
  • So, time taken for searching in worst case is O(n).

 

For Deletion-

 

  • In worst case, the key might have to be searched first and then deleted.
  • In worst case, time taken for searching is O(n).
  • So, time taken for deletion in worst case is O(n).

 

Load Factor (α)-

 

Load factor (α) is defined as-

 

 

If Load factor (α) = constant, then time complexity of Insert, Search, Delete = Θ(1)

 

PRACTICE PROBLEM BASED ON SEPARATE CHAINING-

 

Problem-

 

Using the hash function ‘key mod 7’, insert the following sequence of keys in the hash table-

50, 700, 76, 85, 92, 73 and 101

 

Use separate chaining technique for collision resolution.

 

Solution-

 

The given sequence of keys will be inserted in the hash table as-

 

Step-01:

 

  • Draw an empty hash table.
  • For the given hash function, the possible range of hash values is [0, 6].
  • So, draw an empty hash table consisting of 7 buckets as-

 

 

Step-02:

 

  • Insert the given keys in the hash table one by one.
  • The first key to be inserted in the hash table = 50.
  • Bucket of the hash table to which key 50 maps = 50 mod 7 = 1.
  • So, key 50 will be inserted in bucket-1 of the hash table as-

 

 

Step-03:

 

  • The next key to be inserted in the hash table = 700.
  • Bucket of the hash table to which key 700 maps = 700 mod 7 = 0.
  • So, key 700 will be inserted in bucket-0 of the hash table as-

 

 

Step-04:

 

  • The next key to be inserted in the hash table = 76.
  • Bucket of the hash table to which key 76 maps = 76 mod 7 = 6.
  • So, key 76 will be inserted in bucket-6 of the hash table as-

 

 

Step-05:

 

  • The next key to be inserted in the hash table = 85.
  • Bucket of the hash table to which key 85 maps = 85 mod 7 = 1.
  • Since bucket-1 is already occupied, so collision occurs.
  • Separate chaining handles the collision by creating a linked list to bucket-1.
  • So, key 85 will be inserted in bucket-1 of the hash table as-

 

 

Step-06:

 

  • The next key to be inserted in the hash table = 92.
  • Bucket of the hash table to which key 92 maps = 92 mod 7 = 1.
  • Since bucket-1 is already occupied, so collision occurs.
  • Separate chaining handles the collision by creating a linked list to bucket-1.
  • So, key 92 will be inserted in bucket-1 of the hash table as-

 

 

Step-07:

 

  • The next key to be inserted in the hash table = 73.
  • Bucket of the hash table to which key 73 maps = 73 mod 7 = 3.
  • So, key 73 will be inserted in bucket-3 of the hash table as-

 

 

Step-08:

 

  • The next key to be inserted in the hash table = 101.
  • Bucket of the hash table to which key 101 maps = 101 mod 7 = 3.
  • Since bucket-3 is already occupied, so collision occurs.
  • Separate chaining handles the collision by creating a linked list to bucket-3.
  • So, key 101 will be inserted in bucket-3 of the hash table as-

 

 

To gain better understanding about Separate Chaining,

Watch this Video Lecture

 

Next Article- Open Addressing

 

Get more notes and other study material of Data Structures.

Watch video lectures by visiting our YouTube channel LearnVidFun.