DataStructures Series #10 – The Tree ADT

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.


Tree diagram showing some of the terminologies
Image Source: http://www.tutorialspoint.com

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.

Sample Tree Structure

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:

This image has an empty alt attribute; its file name is image-7.png

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