Trees-Data Structure

What is Tree?

A tree data structure is a non-linear data structure because it does not store in a sequential manner. It is a hierarchical structure consisting of a collection of nodes such that each node of the tree stores a value and a list of references to other nodes (the “children”).

Why we need Tree as Data-Structure?

Other data structures such as arrays, linked list, stack, and queue are linear data structures that store data sequentially. In order to perform any operation in a linear data structure, the time complexity increases with the increase in the data size. But, it is not acceptable in today’s computational world.

Different tree data structures allow quicker and easier access to the data as it is a non-linear data structure.

Why Tree is considered a non-linear Data-Structure?

The data in a tree are not stored in a sequential manner i.e., they are not stored linearly. Instead, they are arranged on multiple levels or we can say it is a hierarchical structure. For this reason, the tree is considered to be a non-linear data structure.

Basic Terminologies in Tree Data-Structure:

Child Node: If the node is a descendant of any node, then the node is known as a child node. Like E, F, G are the children of L.

Root Node: The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node. Example: P is the root node.

Edge: It is the link between any two nodes.

Leaf Node: The node which does not have any child node is called the leaf node.

Sub-tree: Sub tree represents the descendants of a node.

Descendant: The immediate successor of the given node is known as a descendant of a node. Like descendants of L are E, F, and G.

Sibling: Children of the same parent node are called siblings.

Example of Tree Data-Structure

Here,

Node A is the root node

D is the parent of H and I

F and G are the siblings

H, I, F and G are the leaf nodes

Binary Search Tree Representation

Binary Search tree exhibits a special behavior. A node’s left child must have a value less than its parent’s value and the node’s right child must have a value greater than its parent value.

Implementation of Tree Node

(JAVA)

import java.util.ArrayList;

public class TreeNode<T>{

public T data ;

public ArrayList<TreeNode<T>> children;

public TreeNode( T data){

this.data=data;

children=new ArrayList<>();

}

}

Basic Operations

The basic operations that can be performed on a binary search tree data structure, are the following −

Insert − Inserts an element in a tree/create a tree.

Search − Searches an element in a tree.

Preorder Traversal − Traverses a tree in a pre-order manner.

In-order Traversal − Traverses a tree in an in-order manner.

Post-order Traversal − Traverses a tree in a post-order manner.

Types of Tree Data-Structures

The different types of tree data structures are as follows:

General tree

A general tree data structure has no restriction on the number of nodes. It means that a parent node can have any number of child nodes.

Binary tree

Here, binary name itself suggests two numbers, i.e., 0 and 1. In a binary tree, each node in a tree can have utmost two child nodes.

Balanced tree

If the height of the left sub-tree and the right sub-tree is equal or differs at most by 1, the tree is known as a balanced tree.

Properties of Tree Data-Structure

I. Recursive data structure: The tree is also known as a recursive data structure. A tree can be defined as recursively because the distinguished node in a tree data structure is known as a root node.

II. Number of edges: If there are n nodes, then there would n-1 edges. Each arrow in the structure represents the link or path.

III. Depth of node x: The depth of a node is the number of edges from the root to the node.

IV. Height of node x: The height of a node is the number of edges from the node to the deepest leaf (that is the longest path from the node to a leaf node).

Applications of Tree Data-Structure:

The applications of tree data structures are as follows:

Spanning trees: It is the shortest path tree used in the routers to direct the packets to the destination.

Binary Search Tree: It is a type of tree data structure that helps in maintaining a sorted stream of data.

Heap: It is also a tree data structure implemented using arrays. It is used to implement priority queues.

Tries: It is a special kind of tree that is used to store the dictionary. It is a fast and efficient way for dynamic spell checking.

Organize data: It is used to organize data for efficient insertion, deletion and searching. For example, a binary tree has a log N time for searching an element.

I hope this blog gives you a clear understanding about trees in data structures. If this blog helps you understand the concept so share it with your friends and feel free to share your views and drop feedback about the blog. Drop the claps if you liked the blog.
Hit the follow button for more such content and stay connected to know about more data structures.