Introduction to Tree – Data Structure and Algorithm

What is Tree in Data Structure and Algorithm

A tree is a nonlinear hierarchical data structure that consists of nodes connected by edges.

Tree Terminologies:

Node

A node is an entity that contains a key or value and pointers to its child nodes.

The last nodes of each path are called  leaf nodes or external nodes that do not contain a link/pointer to child nodes.

The node having at least a child node is called an  internal node.

Edge

It is the link between any two nodes.

Root

It is the topmost node of a tree.

Height of a Node

The height of a node is the number of edges from the node to the deepest leaf (ie. the longest path from the node to a leaf node).

Depth of a Node

The depth of a node is the number of edges from the root to the node.

Height of a Tree

The height of a Tree is the height of the root node or the depth of the deepest node.

Degree of a Node

The degree of a node is the total number of branches of that node.

Types of Tree

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