What is a Tree?

As we already know about linear data structures, trees, on the other hand, are an example of a non-linear data structure.

Non-linear data structures can express more complex relations. Since a tree is also a type of data structure, it should be understood that it is also a way of organizing data and has similar operations being performed on it like any other linear data structure.

It is a method of storing, accessing and sorting the information; hence, traversal, search, insertion, and deletion are the operations that are generally performed on a tree.

A tree consists of a finite set of elements known as nodes and finite set of directed lines called branches that connects the nodes. The number of branches associated with a node is called the degree of the node.

# Terminologies of a Tree

Root: the unique node with no predecessor. It is the top-most node in the tree and there can be only one root node in a tree.

Leaf node: A node that has no successor or child.

Child node: The successor of a node is called the child node. There can be multiple children nodes to a tree.

Parent node: A node that is connected by branches is a parent node. A parent node may/may not have children nodes.

Sibling nodes: nodes that have the same parent are called sibling nodes. In the above illustration, “High school & senior” are the sibling nodes. “Grad & Job” are also sibling nodes.

Sub Tree: it is the descendant of a node where the root node is not null.

Keys: it is the value of the node.

Levels: It represents the generation of the node. The root node is level 0, and then its child node is level 1 and so on.

Path: It is a sequence of successive edges; in the above illustration path to senior is home-🡪school-🡪senior.

Degree: a degree of a node is the number of children it has.

Types of trees

Binary Tree: These trees are special cases where every node in the tree has a maximum of two children.

Binary Search Tree: An ordered type of binary tree is called a Binary Search Tree or BST. In a BST, nodes to the left are less than the root node while nodes to the right are either equal to greater to the root node.

A tree is a hierarchical data structure that saves data in a natural hierarchy. There are many ways to traverse a tree making it efficient than the linear counterparts.