Tree - Introduction

Motivation:

In real life there are scenarios where collection of data share hierarchical relationship among them. To represent such type of data and relationship among them, Tree data structure is used. For example data of employees and relationship among them based on who reports to whom.

Definition:

A tree is a user defined, non liner and hierarchical data structure used to represent data and relationship among them. It's composed of nodes connected by edges, forming a structure that resembles an inverted tree. Below is an example of a tree.

Component of a tree:

Below are the component of a tree.

Node: A basic unit of a tree that contains data and link(address to children nodes) .
Edge: A connection between two nodes is called edge.
Parent node: This is a node which has one or more children nodes.
Child node: A node that is a descendant of parent node.
Root node: The node which doesn't have any parent is called root node. This is the starting point of tree for any traversal.
Leaf: A node that does not have any children.
Intermediate node- A node which has a parent and at least one child node.
Subtree: A subset of tree which fulfills all condition of tree.
Height: The length of the longest path from the root node to a leaf node.
Depth: The length of the path from the root node to a particular node.
Level: Set of positions forming virtual line where nodes are at the same distance from the .root node is called Level.

Types of Trees

Binary Tree: This is a tree where any node can have maximum 2 children. Children nodes are known as left child and right child.
Binary Search Tree (BST): A binary tree where key value of all parent nodes is greater than all key values of its left subtree and lesser than key values of all right sub trees or vice versa.

a. (All data in the left subtree)<=Parent Node(data)<= (All data in the right subtree) or

b. (All data in the left subtree)>=Parent Node(data)>= (All data in the right subtree)
Balanced Tree: A tree where the height difference between the left and right subtrees of any node is at most one.
Complete Binary Tree: A binary tree in which all levels except last level have maximum possible number of nodes. At last level if maximum leaf noes are not present then the leftmost side of the leaf node must always be filled first.
Full Binary Tree: A binary tree where all nodes have either 0 or 2 children.
AVL Tree: A binary search tree which fulfills all property of balanced tree is called AVL tree.
Red-Black Tree: A self-balancing binary search tree with additional properties that ensure the tree remains balanced.
B-Tree: A self-balancing tree data structure which holds n number of data in one node that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.

Common Operations

Insertion: Adding a new node to the tree.
Deletion: Removing an existing node from the tree.
Traversal: Visiting all nodes in the tree in a specific order to process data present on nodes:

In-order Traversal: For a given node, here Left subtree is traversed recursively first then data present at root is processed and then right subtree is traversed recursively. Here order of traversal is LEFT SUBTREE->ROOT->RIGHT SUBTREE. We will cover it in the next chapter in details.
Pre-order Traversal: For a given node, here data present at root is processed first then Left subtree is traversed recursively and then right subtree is traversed recursively. Here order of traversal is ROOT->LEFT SUBTREE->RIGHT SUBTREE.. We will cover it in the next chapter in details.
Post-order Traversal: For a given node, here Left subtree is traversed recursively first then right subtree is traversed recursively and then data present at root is processed. Here order of traversal is LEFT SUBTREE->RIGHT SUBTREE->ROOT. We will cover it in the next chapter in details.
Level-order Traversal: Visiting nodes level by level from top to bottom. We will cover it in the next chapter in details.

Tree Representation methods

A tree is represented below in graphical format. We are going to discuss techniques suitable for programming languages to store it using user defined data structure.

There are many methods available to represent a tree. But below two are widely used to represent a tree which is easily used in programming languages.

Adjacency List: Here each node has its own list of children in an array or array list. Below is the representation for above mentioned tree.
a:[b,c]
b:[d,e,f]
c:[g]
Adjacency Matrix: Here a two dimensional matrix is used to represent parent child relationship among nodes. Here nodes are indexed and based on node index a two dimension matrix of size n*n is prepared to store edge among nodes where n is total number of nodes. If any entry (row,col) in matrix has value 1 it means there is edge from node index row to node index col otherwise no edge. This representation needs more memory space to allocate compared to Adjacency List representation. Below are representation for above mentioned tree.
Suppose tree data is represented as data=[a,b,c,d,e,f,g] and first index start with 0
Then adjacency matrix representation for above tree will be as following

Below is the java code implementation of the above mentioned tree representations

import java.util.ArrayList;

import java.util.List;

public class TreeRepresentationTest {

/**

* @param args

public static void main(String[] args) {

// TODO Auto-generated method stub

TreeRepresentation treeRep=new TreeRepresentation();

treeRep.treeByAdjList();

System.out.println();

treeRep.treeByAdjMatrix();

}

class TreeRepresentation

{

private char []data={'a','b','c','d','e','f','g'};

//This method shows how to implement tree using adjacency list.

public void treeByAdjList(){

List<List<Integer>> adjTree=new ArrayList<List<Integer>>();

adjTree.add(0,new ArrayList<Integer>());

adjTree.add(1,new ArrayList<Integer>());

adjTree.add(2,new ArrayList<Integer>());

adjTree.get(0).add(1);

adjTree.get(0).add(2);

adjTree.get(1).add(3);

adjTree.get(1).add(4);

adjTree.get(1).add(5);

adjTree.get(2).add(6);

System.out.println("===========Items in ADJ LIST representation-starts===============");

for(int i=0;i<adjTree.size();i++){

char parent=data[i];

String children="";

for(int itemIndex:adjTree.get(i))

{

children=children+data[itemIndex]+" ";

}

System.out.println("Children of node "+parent+" :"+children);

}

System.out.println("===========Items in ADJ LIST representation-ends===============");

}

//This method shows how to implement tree using adjacency matrix.

public void treeByAdjMatrix(){

int[][] parentIndex=new int[data.length][data.length];

parentIndex[1][0]=1;

parentIndex[2][0]=1;

parentIndex[3][1]=1;

parentIndex[4][1]=1;

parentIndex[5][1]=1;

parentIndex[6][2]=1;

System.out.println("===========Items in ADJ MATRIX representation-starts===============");

for(int i=0;i<data.length;i++)

{

for(int j=0;j<data.length;j++)

{

if(parentIndex[i][j]==1)

{

System.out.println("Parent of node :"+data[i]+" is :"+data[j]);

}

System.out.println("===========Items in ADJ MATRIX representation-ends===============");

}