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.