Tree Data Structure & Algorithm

By | September 14, 2019

The tree is one of the most used Data Structures and there are many real-world solutions based on this data structure. Though we have Data structures like an array and linked list to store data, the time complexity of searching an element from an array and list have linear time complexity. Suppose there is a list or array with n number of elements or sets, then the number of comparisons needed to find (or not find) an element may be n. So, imagine searching for an element in a linked list (or array) with n = 106 nodes. Even on a machine that can do a million comparisons per second, searching for m items will take roughly m seconds. Therefore, we require a better data structure to store and search data. Here in this article, we have provided a brief explanation of what is a Tree Data Structure and why we use it.

What is Tree Data Structure?

A Tree is a Non-Linear, data structure and it is a collection of nodes and edges, the edges could be directed or undirected. The tree follows a hierarchical structure and does not form any closed loop.

In the tree, there is only one root node which is also known as the first or head node of the tree data structure and each node is the child node of it.

A Tree can also be defined as the recursive collection of nodes where each node has a parent node except the root node.

Tree Properties

  • If a tree has one node it would be the root node.
  • A tree does not form a closed-loop structure.
  • Every node is connected by one node.
  • Each node of a tree can have an arbitrary number of child nodes.
  • A tree with its disjoint subtree is known as a forest.

Basic Tree Terminology

Node A node is a separate data structure that contains data or value for a tree.
Root The top node in a tree.
Child A node connected to the previous node is known as the child node, each node in the tree is the child node of the root node
Parent It is opposite of the Child node; a parent node is the main node which is connected to the further child node.
Siblings Two or more than two nodes with the same parent node are the sibling’s node
Leaf / External node (not common)

 

The node in the tree data structure which has no further child node
Branch node / Internal node A node with at least one child.
Edge The connection between one node and another.
Path A sequence of nodes and edges connecting a node with a descendant.
Distance The number of edges along the shortest path between two nodes.
Depth The distance between a node and the root.
Height The number of edges on the longest path between a node and a descendant leaf.
Height of tree The height of the root node or the maximum level of any node in the tree
Sub Tree A tree T is a tree consisting of a node in T and all of its descendants in T.
Size of a tree The total number of nodes present in the tree.

Types of Tree

Here are some basic types of Tree data structure:

  • General Tree
  • Binary Tree
  • Binary Search Tree

General Tree

In General Tree, each node could have zero or more than zero child node.

Binary Tree

In the binary tree, each node could not have more than two nodes.

Binary Search Tree

A binary search tree is an ordered binary tree in which each node on the left side of the root node is less than root node and the nodes on the right side of the root node are greater than root node.

Advantages of Tree

  • In the tree, the same node shows multiple relations
  • Provides a hierarchical structure
  • Provides efficient insertion and deletion operations

Leave a Reply

Your email address will not be published. Required fields are marked *