Originally posted on my medium page: https://medium.com/@otarutunde

**The Tree ADT**

A tree is a data structure made up of nodes (or vertices) connected by edges without having any cycle. All Images below are not trees because you can find at least one cycle in all of them.

The tree with no nodes is called the null or empty tree. A tree that is not empty consists of a root node and potentially many levels of additional nodes that form a hierarchy.

**Tree Terminologies:**

**Root**: The top node in the tree**Child**: A node directly connected to another node above it**Parent**: A node connected to other node(s) below it**Siblings**: A group of node having the same parent**Leaf**: A node with no children**Degree**: The number of children of a given node, A**leaf**has a zero degree**Edge**: The connection between one node and another**Path**: A sequence of nodes and edges connecting a node and another node**Level**: The level of a node is defined as 1 + the number of edges between the node and the root**Height of a node**: The height of a node is the number of edges on the longest path between the node and the leaf.**Height of a tree**: The height of a tree is the height of its root node.**Depth of a node**: The depth of a node is the number of edges from the tree’s root node to the node.

It is good to note that there are various variants of the Tree ADT : Binary Search Tree ADT, B Tree ADT etc.

**Tree Main Operations:**

- Insertion
- Deletion
- Traversal / Search

**Implementation**

The approach here is to create a class representing a node with its following properties.

Below is a pseudocode implementation for tree structure shown in the image above:

Class Node { List<Node> Children = new List; class_constructor(Children) { this.Children = Children; } } List<Node> emptyList = new List; Node C = new Node(emptyList); Node D = new Node(emptyList); Node E = new Node(emptyList); List<Node> BChildren = new List; BChildren.Insert(C); BChildren.Insert(D); BChildren.Insert(E); Node B = new Node(BChildren); Node F = new Node(emptyList); List<Node> AChildren = new List; AChildren.Insert(B); AChildren.Insert(F); Node A = new Node(AChildren);

Insert two nodes G and H under F so the tree structure looks like this:

**Insertion**

List<Node> emptyList = new List; Node G = new Node(emptyList); Node H = new Node(emptyList); F.Children.Insert(G); F.Children.Insert(H);

Delete node D from B so that the new tree structure becomes:

**Deletion**

B.Children.Delete(D);

Traversing a tree involves iterating over all nodes in some manner. Because from a given node there is more than one possible next node (it is not a linear data structure). There are two major ways of iterating through a tree structure: **Breadth** First or **Depth** First

*For the sake of simplicity, we will be using a tree structure with at most two children (left and right). *

**Breadth** First approach visits all nodes on the same level before going to a level below until there are no more nodes to be visited.

**Depth** First approach goes deep into a node as much as possible on each child before going to the next sibling. There are three ways to perform depth first traversal: **Pre**-Order, **In**-Order and **Post**-Order

**Pre-Order**approach is to start at the root node, access the data of the current node, traverse the left subtree of the root node by recursively calling the pre-order function, then, traverse the right subtree by recursively calling the pre-order function.

**In-Order**approach is to traverse the left subtree of the root node by recursively calling the in-0rder function, access the data of the current node, traverse the right subtree by recursively calling the in-order function.

**Post-Order**approach is traverse the left subtree of the root node by recursively calling the post-order function, traverse the right subtree by recursively calling the post-order function, access the data of the current node.

Using this diagram below to explain the traversal for breadth and depth first traversals:

**Breadth** First : A -> B -> F -> C -> E -> G -> H

**Depth** First

- Pre Order : A -> B -> C -> E -> F -> G -> H
- In Order : C -> B -> E -> A -> G -> F -> H
- Post Order: C -> E -> B -> G -> H -> F -> A

**Traversal**

Breadth First

LevelOrder (root) Queue queue = new Queue; queue.EnQueue(root); while queue is not Empty: node = queue.DeQueue() print nodeData if node.left != null then queue.EnQueue(node.left); if node.right != null then queue.EnQueue(node.right);

Depth First (Pre Order)

PreOrder (root) if (node == null) return; print nodeData Preorder (node.left) Preorde (node.right)

Depth First (In Order)

InOrder (root) if (node == null) return; InOrder (node.left) print nodeData InOrder (node.right)

Depth First (Post Order)

PostOrder (root) if (node == null) return; PostOrder (node.left) PostOrder (node.right) print nodeData

This approach can be extended to cater for a tree structure with nodes having more than two children, the extra step will be to iterate through a node’s children and keep track of the nodes that have been visited/unvisited.

**Real life Applications**

- A filesystem on a computer

REFERENCES