## What is a Binary Tree?

A binary tree is a type of non-linear data structure. Each node has a maximum of two child nodes in this type of structure. The lines connecting the nodes are the branches of a binary tree. The two child nodes also have a name, i.e., left subtree and right subtree. A binary tree is a special case of an ordered binary tree, where k is 2. In the representation of a binary tree, one important thing is that no node can have two duplicative values.## Types of Binary Tree

Along with the ways of representation of a binary tree, there are three different types of binary trees. An explanation of those three types is below.### Complete Tree

The first type of binary tree is a complete binary tree. A binary tree is complete if it follows the things mentioned below.- All its levels, except possibly the last level, have the most number of nodes
- All the nodes at the last level of the tree appear as much as possible at the far left

Sometimes, the term full binary tree is also used to represent a complete binary tree. There is always confusion about how many nodes should be present in a binary tree. There is a simple formula to calculate this. If there are T levels in a binary tree, nodes will be 2T -1. In case of any problem in understanding the formula, you can hire assignment writing services UK.

### Degenerate Binary Tree

A binary can also have a single child instead of two children. The degenerate tree is also a type of this kind of tree. If all the tree nodes have only one child, it is a degenerate binary tree. Performance-wise, such trees are similar to a linked list. One important thing to remember is that such trees do not have left or right child nodes. The single child node can either be on the right or the left side of the root.### Balanced Binary Tree

A binary tree is ‘balanced’ if the tree height is O(logN), where ‘N’ is the number of nodes. In this type of binary tree, the size of each node’s left and the right children should vary by at most one. An AVL Tree and a Red-Black Tree are some most widely used balanced binary trees.## Different Ways of Representation of Binary Tree

Having discussed the binary tree, it is time to explain different ways of representation of a binary tree. Basically, there are two ways of doing this and below are the names of those two methods.- Link representation of a binary tree
- Sequential representation of a binary tree

### What is Link Representation?

In the linked representation, the data scientists use double-linked presentations. In a double linked representation, each node consists of three fields. Each node in linked representation stores data at the centre. The right and left wings of the node are for storing left child and right child nodes addresses, respectively. Consider a binary tree S. Now, think that the tree S will be represented using the link representation. Remember, the link representation contains three fields. The INFO about the node is at the centre, and addresses are on the left and right limbs. In a binary tree, k represents the location of each node.- LEFT (k) = Contains the information about the location of the left child node
- INFO (k) = Contains the actual data of the node
- RIGHT (k) = Contains the information about the location of the right child node

This is how a link representation moves forward. If any child node is empty, the corresponding contains the null value. But if the tree itself is empty, then the ROOT will have the null value.

What is Sequential Representation?

The sequential or array representation is the most widely used way of representation of a binary tree. It uses a one-dimensional array to represent a binary tree. The location of the left and right children nodes changes using some factors. Let’s explain it with the help of an example. Consider that you have a binary tree S. As explained earlier, the sequential representation uses only a liner array. The formulae for representing the information in this type of representation is as follows.

- The root R of the tree S is stored in the Tree itself.
- If a node resides in Tree [k], then its left child is stored in Tree [2 * k], and its right child is held into Tree [2 * k + 1].

## 0 comments:

## Post a Comment