A tree data structure as the name suggests looks like a tree when visualized, an upturned one to be precise for that matter and provides an excellent structural framework to store non-linear hierarchical data.
This blog will discuss tree data structure at length but before that it makes sense to go back to the definition of what data structures are to better understand the importance of tree data structure.
What is a Data Structure?
Data Structures allow storage and organization of data on a computer so that they can be accessed and updated efficiently.
Benefits of Data Structures
Data structures advantages include:
- Easier organization and storage of data
- Efficient processing of data
- Better accessibility
- Secure storage of data
Learning data structure and algorithms makes one a better programmer.
Types of Data Structures
There are primarily two kinds of data structures:
- Primitive Data Structure
- Non-Primitive Data Structures
Primitive data structure
Primitive data structures operate as per the machine instructions and can hold a single value, examples include, like int, char, float, double, and pointer.
Non- Primitive data structure
They are complex data structures derived from primitive data structures and non primitive data structures are further divided into
- Linear data structures – Sequential where every element is connected to previous and the next Easy to implement and examples include List, Queue, Stack, Array etc.
- Non-linear data structures – No set sequence, multiple paths attaching to other elements, support multi level storage but aren’t easy to implement, examples include Tree, BST, Graphs.
With that background of data structures in mind, let’s progress towards understanding Tree Data Structures and their types.
What is a Tree Data Structure?
Tree Data Structure is a hierarchical data structure which has a collection of nodes where each node stores a value and a list of references to other nodes, referred to as children.
Let’s take a look at the terms often encountered in tree data structures:
Root Node– The highest node in the tree datas structure which does not have a parent node.
Child Node- The descendent of a node if called child node
Parent Node– If a node has a descendent or a sub-node it is called a parent node
Sibling Node– Nodes having the same parent node are called the sibling nodes.
Leaf Node– The bottom nodes are also called external nodes and have no child nodes.
Internal Node- Any node having even one child node is called an internal node.
Edges – The link between the two nodes.
Height of a node – The number of edges between the node in question and the leaf node or the lowest node in the hierarchy of the tree structure is called the height of a node.
Depth of a node – The number of edges between the root node and the node in question is the depth of a node.
Degree – The number of branches coming out of a node is called the degree of that node.
Forest – It is a collection of disconnected trees. If the roots of the tree are cut, disjoint trees are created and these trees make a forest.
Let’s take a look at the types of trees:
Binary Trees: Binary trees are characterized by each parent node having at least 2 children, namely the left and the right child.
There are three parts of a binary tree:
- Data
- Pointer to the left child
- Pointer to the right child
Different types of binary tree include:
- Full Binary Tree- Parent node with two or no children
- Perfect Binary Tree – Each Parent node has 2 children nodes and all the external or leaf nodes at the same level
- Complete Binary Tree – Every level is filled and the leaf elements lean towards left
- Degenerate Tree- Parent node with a single child node which is either left or right
- Balanced Binary Tree – The height difference between the left or the right child node is 0 or 1.
Binary Search Tree – Binary search trees are similar to binary trees in a manner that each node can have two children but there are a few specifications:
- Each node on the left subtree has a value smaller than the root node
- Each node of the right subtree has a value larger than the root node
- This arrangement is replicated across the tree where each node and its subtree follows the pattern
Such a pattern makes finding something far easier in the binary search tree.
Balance Factor of a Node
The difference in the height of the right subtree and the left subtree of a specific node is called the balance factor of a node.
A height balanced tree has node balance factor between -1 to 1.
If the balance factor of a node is 1, left sub-tree is one level higher than the right subtree
If the balance factor is zero, the right and the left subtree are at the same level
If the balance factor is -1, the left subtree is one level lower than the right subtree.
AVL Tree – They follow the same properties of the binary search tree and have a balance factor between 1 and -1.
B-Tree – A self balancing tree where each node can have more than one key and more than two child nodes.
Because of its ability to store multi keys it takes much shorter time to access physical storage media like a hard disk.
Some of the properties of B tree are:
- B-trees have orders or maximum number of children possible and each node of m order can have maximum of m children
- Root nodes must have two nodes
- All leaf nodes are at the same level
- A tree of X order has internal node that can have X-1 key with a pointer to every child
Traversal in a Tree Data Structure
Also known as tree search or walking the tree, it refers to the process of retrieving, updating or deleting each node of the tree data structure, exactly once.
There are several ways of traversing the tree in a tree data structure unlike linear data structures like arrays, stacks etc which have just one way.
Let’s look at some of the ways traversal in a tree data structure takes place:
In-order Traversal – First the nodes in the left subtree are visited, then the root nodes and finally the nodes on the right subtree.
Pre order Traversal – First the root node, then the nodes on the left subtree and finally the nodes on the right subtree
Post Order Traversal – Nodes on the left subtree then on the right and finally the root nodes are visited.
Operations of a Tree
Insertion – When new elements are to be inserted, it can be:
- Can be inserted in the rightmost or leftmost vacant positions
- Can be inserted in the first vacant position encountered while traversing the tree
Searching – In a binary tree, the process is simple where the current node’s value is checked vis a vis the required value and a match is searched for using a recursive algorithm checking the left and right subtrees.
Deletion – It can be done after carefully considering following situations:
- If a node is deleted, what happens to the left and right child
- If the deleted node is a leaf node
The steps involved are:
- If the root is null, we simply return the root
- Search for the item in the right and the left subtree and recurse if a match is found
- If the value is not found either in the left or the right subtree, the value is not there
While deleting the root node one may encounter three scenarios:
- If a leaf node is to be deleted, we simply delete the roof
- When the root node has a child node, the root node is replaced with the child node
- If there are two children nodes, we find the next in-order successor and replace the to be deleted note with it recursively until it is placed on the leftmost leaf node and then replace the node with null
Conclusion
Tree data structures with their hierarchical data storage allow efficient storing and organizing data while also making retrieving the data simple. Programmers need to have a detailed understanding of data structures especially tree data structures to build their logic and problem solving skills. Tree data structures find multiple usage in everyday life as well.
FunctionUp is a Y Combinator backed placement boot camp that offers outcome oriented upskilling courses like DA, Backend, PM and Sales. Learn Everything About Tree Data Structure Now.