Programs

# 4 Types of Trees in Data Structure Explained: Properties & Applications

## Summary

In this article, you will learn about the Types of Trees in Data Structure with their Properties & Applications.

Take a glimpse at the types of Trees in the Data Structure.

1. Binary tree
2. Binary Search Tree
3. AVL Tree
4. B-Tree

Read the entire article to learn in detail.

## What is a Tree in Data Structure?

A tree is a type of data structure representing hierarchical data. It has a non-linear structure consisting of nodes connected by edges. Among the other types of data structures that perform operations in a linear data structure, the complexwebinarity increases with an increase in data size. However, the tree data structure provides quicker access to the data which is non-linear. Availability of the various types of data structures and the algorithms associated with them, the task performance has become an easy and efficient way. Check out our free data science courses to get an edge over the competition.

The difference between the computing field tree and the real-world tree is that it is visualized as upside down with roots at the top and leaves at the bottom. In real-world applications, the tree data structure helps to demonstrate relationships between various nodes with the parent-child hierarchy. It is alternatively known as a hierarchic data structure.

It is highly popular for streamlining and accelerating sorting and searching tasks. It is one of the resilient and most innovative data structures. It represents the non-linear data structure. It can also represent various primitive or user-defined data types. You can use classes connected lists, arrays, or other types of data structures to employ the tree. Its structure shows a group of interconnected nodes. These nodes are connected to the edges to depict the relationship. After understanding what is tree in data structure, let’s get familiar with some of its key terminologies.

A few terminologies associated with trees in data structure are:

• Node: the node is an entity in a tree data structure that contains a key or a value and pointers to its child nodes.
• Child node: A child node is the descendant of any node.
• Leaf nodes: The nodes which don’t have any child nodes and are the bottom-most node in a tree. They are also called the external nodes.
• Parent node: This node is located directly above a node. It is the principal in the hierarchy. For example, 50 is the parent node of 60, 70, and 80.
• Root: It is the topmost point of a tree.
• Internal node: The node having at least one child node.
• Edge: An edge refers to the connection between any two nodes in a tree.
• Height of a node: Number of edges from the node to the deepest leaf.
• Depth of a node: Number of edges from the root to the node. The root node’s depth is zero. Any other node’s depth is the number of edges it derives from the root node.
• Degree of a tree: It denotes the maximum of all the probable degrees of its nodes.
• Number of edges: If a tree has n nodes, the number of edges would be n-1. Excluding the root node, all other nodes in the tree possess a minimum of one incoming edge.
• Height of a tree: Height of the root node. It is the path length from a specific node to the extreme leaf node. It is always calculated from bottom to top. Hence, each leaf’s height is 0.
• Degree of a node: Total number of branches to that node.
• Forest: A collection of disjoint trees.
• Subtree: It denotes children in the tree. Every child is either a leaf node or a subtree.
• Generation: Nodes existing at the same level of the tree are called a generation. For instance, 60, 70, and 80 belong to the same generation.
• Ancestor: Suppose there are two nodes, A and B, and there is a path from A to B, then A is the ancestor of B. It is common terminology used in various trees in data structure.
• Descendent: It is the reverse of an ancestor.
• Sibling: Two nodes with the same parent are called siblings. Suppose 70, 80, and 90 are siblings and 100 is the parent.

You can also consider doing our Python Bootcamp course from upGrad to upskill your career.

• Subtree: It denotes children in the tree. Every child is either a leaf node or a subtree.
• Generation: Nodes existing at the same level of the tree are called a generation. For instance, 60, 70, and 80 belong to the same generation.
• Ancestor: Suppose there are two nodes, A and B, and there is a path from A to B, then A is the ancestor of B. It is common terminology used in various trees in data structure.
• Descendent: It is the reverse of an ancestor.
• Sibling: Two nodes with the same parent are called siblings. Suppose 70, 80, and 90 are siblings and 100 is the parent.
• Levels: The root node exists at level zero, and its children exist at level one. Level one’s children exist at level two.

## Types of tree

### 1. Binary tree

The binary tree is a type of tree data structure where every parent node has a maximum of two child nodes. As the name suggests, binary means two, therefore, each node can have 0, 1, or 2 nodes. A binary tree data structure is shown in Figure 1. Node 1 in the tree contains two pointers, one for each child node. Node 2 again has two pointers each for the two child nodes. Whereas node 3, 5, and 6 are leaf nodes and therefore, have null pointers on both left and right parts.

This type of tree data structure allows a maximum of two children for each parent. The children are known as the right kid and the left kid. A binary tree is more popular than other trees in data structure. Applying several limitations and characteristics in a Binary tree, other tree structures like BST (Binary Search Tree), AVL tree, RBT tree, etc. are also used

Figure 1:  A representation of a binary-tree

Properties of a binary tree

• Maximum number of nodes at each level of I is 2 i.
• The height of the tree in Figure 1 is 3 which means that the maximum number of nodes will be (1+2+4+8) =15.
• At height h, the maximum number of nodes possible is (20 + 21 + 22+….2h) = 2h+1 -1.
• At height h, the minimum number of nodes possible is equal to h+1.
• A minimum number of nodes will represent a tree with maximum height and vice versa.

Must read: Excel online course free!

Even the binary trees can be divided into the following types of tree:

• Full Binary tree: It is a special type of binary tree. In this tree data structure, every parent node or an internal node has either two children or no child nodes.
• Perfect binary tree: In this type of tree data structure, every internal node has exactly two child nodes and all the leaf nodes are at the same level.
• Complete binary tree: It resembles that of the full binary tree with a few differences.
• Every level is completely filled.

Must read: Data structures and algorithm free!

• The leaf nodes lean towards the left of the tree.
• It is not a requirement for the last leaf node to have the right sibling, i.e. a complete binary tree doesn’t have to be a full binary tree.
• Degenerate or Pathological Tree: These trees have a single child either to the left or right of the parent node.
• Skewed binary tree: It is a pathological or degenerate tree where the tree is dominated by either the left nodes or the right nodes. Therefore, there are two types of skewed binary trees, i.e. left-skewed or the right-skewed binary tree.
• Balanced binary tree: The difference between the height of the left and right subtree for each node is either 0 or 1.

Learn Data Science Courses online at upGrad

## Explore our Popular Data Science Courses

 Executive Post Graduate Programme in Data Science from IIITB Professional Certificate Program in Data Science for Business Decision Making Master of Science in Data Science from University of Arizona Advanced Certificate Programme in Data Science from IIITB Professional Certificate Program in Data Science and Business Analytics from University of Maryland Data Science Courses

### 2. Binary Search Tree

These tree structures are non-linear and one node is connected to a number of nodes. The node can be connected to at most two child nodes. It is called a binary search tree because:

• Each node has a maximum of two child nodes.
• It can be used to search an element in 0(log(n)) time and hence known as a search tree

Figure: An example of a Binary search tree (Example)

Properties of a binary search tree are:

• Value in all thenodes of a left subtree should be lesser than the value in the root node.
• Value in all the nodes of a right subtree should be larger than the value in the root node.

Featured Program for you: Fullstack Development Bootcamp Course

Binary Search Tree (BST) works as a binary tree extension with many optional restrictions. For example, a node’s left child value in BST must be less than or equal to the parent value.  A node’s right child must be greater than or equal to the parent’s value. It is one of those properties of tree in data structure that makes BST perfect for search operations. This is because it helps you to accurately determine whether the values exist at the right or left sub-tree.  Therefore, it is called a “Search Tree”. BST is best for the search operation because it helps you to decide where to move.

## Read our popular Data Science Articles

 Data Science Career Path: A Comprehensive Career Guide Data Science Career Growth: The Future of Work is here Why is Data Science Important? 8 Ways Data Science Brings Value to the Business Relevance of Data Science for Managers The Ultimate Data Science Cheat Sheet Every Data Scientists Should Have Top 6 Reasons Why You Should Become a Data Scientist A Day in the Life of Data Scientist: What do they do? Myth Busted: Data Science doesn’t need Coding Business Intelligence vs Data Science: What are the differences?

### 3. AVL Tree

The AVL trees are the types or variants of a binary tree. It consists of properties from both the binary as well as a binary search tree. Invented by Adelson Velsky Lindas, these trees are self-balancing which means the height of the left subtree and the right subtree is balanced. This balance is measured in terms of a balancing factor.

Also read: Learn python online free!

AVL tree is a self-balancing binary search tree. It is unique from other types of tree data structure because it was the first tree that was dynamically balanced. Each node in the AVL tree is assigned a balancing factor. This process depends on whether the tree is balanced or not.  The balancing factor is one of the prominent properties of the tree in data structure of the AVL Tree.

The precise balance factor in the AVL tree is 1, 0, and -1. In case the tree got a new node, it would be rotated to ascertain that it is balanced. Certain common operations like insertion, viewing, and removal take O(log n) time in this tree. Usually, it is employed when working with the Lookups operations.

Balancing factor:

• It is the difference between the left subtree and the right subtree.
• The value of a balancing factor must be 0, -1, or 1. Therefore, each node of an AVL tree should consist of a balancing factor value i.e. 0, -1, or 1.
• Balance Factor = (Height of Left Subtree – Height of Right Subtree)
• An AVL tree is said to be a balanced tree if the balance factor of each node is between -1 to 1.

Values of nodes other than -1, to 1 in an AVL tree will represent an unbalanced tree that needs to be balanced.

• If a node has a balance factor of 1, it means that the left subtree is one level higher than the right subtree.
• If a node has a balance factor of 0, it means that the height of the left subtree and the right subtree is equal.
• If a node has a balance factor of -1, it means that the right subtree is one level higher than the left subtree or the left subtree is one level lower than the right subtree.

upGrad’s Exclusive Data Science Webinar for you –

### 4. B-Tree

B Tree is a more generalized form of a binary search tree. It is also known as the height-balanced m way tree, where m is the order of the tree. Each node of the tree can have more than one key and more than two child nodes. In the case of a binary tree, the leaf nodes might not be at the same level. However, in the case of a B Tree, all the leaf nodes should be at the same level.

Properties of a B-tree:

• Keys are stored in increasing order for each node x.
• A Boolean value “x.leaf” exists in each node, which is true if x is a leaf.
• The internal nodes should have at most “n-1” keys, where n is the order of the tree. It should also have a pointer for each child.
• All the nodes will have at most n children and at least n/2 children, except the root node.
• The leaf nodes of the tree have the same depth.
• The root node will have a minimum of 1 key and at least two children.
• If n ≥ 1, then for any n-key B-tree of height h and minimum degree t ≥ 2, h ≥ logt (n+1)/2.

## Top Data Science Skills to Learn

 Top Data Science Skills to Learn 1 Data Analysis Course Inferential Statistics Courses 2 Hypothesis Testing Programs Logistic Regression Courses 3 Linear Regression Courses Linear Algebra for Analysis

## Applications

• Binary Search tree can be applied for searching an element in a set of elements.
• Heap trees are used for heap sort.
• Modern routers use a type of tree called Tries for storing routing information.
• The B-Trees and the T-Trees are mostly used by popular databases to store their data.
• A syntax tree is used by compilers to validate the syntax of every written program.

## Conclusion

Data structures provide an organized way of storing the data for easy management and effective handling. Various types of data structures exist for different types of data. Based on the type of data that needs to be stored, it is chosen by the user.

Trees are types of such data structures where the hierarchical type of data can be stored. The data is stored in the nodes which sometimes stores the reference for other nodes called the children nodes.

Based on the number of child nodes, trees can be classified into various types as mentioned in the article. Based on the arrangement of nodes in the tree types, each tree structure has associated properties. With the different types of operation that can be performed by the different classes of trees, this type of data structure has found applications in sorting algorithms and data storage.

An Executive PG Programme in Software Development – Specialisation in Full Stack Development, curated by upGrad & IIIT-Bangalore, can assist you in improving your profile and securing better employment opportunities as a programmer.

### State the difference between the Binary Tree and the Binary Search Tree?

Although both the Binary Tree and the Binary Search Tree seem similar at first glimpse, however, they largely differ from each other in many ways:
Binary Tree -
1. A Binary Tree can have 2 nodes at most and there is no particular order for the nodes.
2. Operations like insertion, deletion, and searching are comparatively slower since it is unordered.
3. Full binary tree, extended binary tree, and complete binary tree are examples of binary trees.
Binary Search Tree -
1. A Binary Search Tree is a special kind of binary tree where each node has a right and left subtree which are binary search trees themselves.
2. All these operations are faster since the elements are in an ordered manner.
3. AVL tree, tango tree, and splay tree are examples of binary search trees.

### What are self-balancing trees and where are they used?

The self-balancing trees are binary search trees that are structured in such a way that on insertion of a new node, these trees balance themselves.
Some examples of self-balanced trees are:
AVL tree
Splay Tree
Red-Black Tree
Self-balancing trees are used to implement several real-life applications such as database transactions, file systems, cache management, algorithms written for garbage collection, multiset implementation. ## Prepare for a Career of the Future

### Data Science Skills to Master  