# What is a Tree?

Written by

**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.