What is a Generic Tree in Java

Generic Tree is a type of Hierarchical data structure called Trees. There are Different types of Tree Data Structures like Binary Tree, Binary Search Tree ( BST ), AVL Tree, etc.  Similarly a Generic tree is also a tree data structure.

Now, See this example of a generic tree with real life example, this is how files are stored in your computer system :

What is a Generic Tree

With the above example we can say that, 

A Generic tree is a collection of nodes in which each node acts as a data structure consisting of its own value and list of references to its children. Unlike Linkedlist it stores the address of multiple nodes. Address of the first node is stored in a pointer called node and every node contains the address to its children. 

Generic trees are also known as N-ary Trees or K-ary Trees. Generics have these following properties:

  • 1 , 2 or more children at every node.
  • Number of children at each node are dynamic or not known in advance.

EXAMPLE:

Now, lets see the representation of the node class in java –

// Node representation
   private class Node{
       int data;
       ArrayList<Node> children = new ArrayList<>();
   }

Here, we use Dynamic arrays to store children as the number of children a node has is not predefined. In the case of Java we use ArrayLists from collections and similarly in C++ we can use vector STL.

// Node representation in C++
  class Node{
	int data;
	vector<Node*> children;
  }

Some terminologies used :

  1. Leaf node : Nodes without any child. 

E.g: In the above fig. Node K, L, N, I, J and H are leaf nodes.

  1. Parent node : the previous to which the current child node is connected.

E.g. C is the parent of K, L and N. Similarly, G is parent of H and A is parent of B, C, D, E and F nodes.

  1.  Child node: the current will be called the child of the parent node.

E.g. node K, L and N are the children of node C.

  1. Ancestor : All the parent nodes to which any node is connected are called its ancestor.

E.g. The ancestor nodes of K are node C and node A.

  1. Root : The top most node without any parent is called the root node. E.g. Here A is the root node.

Constructing the Generic Tree

Lets construct this above generic tree. To generate this tree you first need to understand the euler path of the tree. The input of constructing this generic tree will be given by the euler path of the tree. 

This is the euler path for this tree :

Input of this tree is given according to the euler path. -1 is passed whenever the euler reaches the right part of the node (see in the above fig.).

Input array will be accordingly this,

int arr[] = { 10,20,50,-1,60,-1,-1,30,70,-1,80,110,-1,120,-1,-1,90,-1,-1,40,100,-1,-1,-1 };

Now, 

ALGORITHM :

  1. Initialize a stack of nodes , pass the element from the array , make a node and initialize its value.
  2. If the stack is empty , push the node in stack and mark the node as root.
  3. Pass another element, check if it is not -1 then make a new node with that element, call top of the stack and add the new node as top element’s child and push the new node in the stack.
  4. If -1 is the element then we pop from the stack and repeat.

If the above algorithm is not clear, don’t worry see the following code it will be crystal clear and generic tree we become one of your strong topic.

Let’s Dive into the code :

/* Generic tree construction */

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
	// Node representation
	private class Node{
			int data;
			ArrayList<Node> children = new ArrayList<>();
		}
		
	public static void main (String[] args) throws java.lang.Exception
	{
		//Input
		int arr[] = {10,20,50,-1,60,-1,-1,30,70,-1,80,110,-1,120,-1,-1,90,-1,-1,40,100,-1,-1,-1};
		
		Node root; // initializing root node
		Stack<Node> stack = new Stack<>(); // creating the stack

		// Traversing the given array
		
		for(int i=0 ; i<arr.length ; i++){
			
			if(arr[i] == -1){
				stack.pop();
			} else {
				
				Node treeNode = new Node();//creating new node
				treeNode.data = arr[i];
				// stack is not empty 
				if( stack.size() > 0 ){
					Node top = stack.peek();
					top.children.add(treeNode); // making the new node top node’s child
					stack.push(treeNode); // pushing the new node in stack
				} else {
					// Stack is empty
					root = treeNode;
				}
				
			}
			
		}
		
	}
}

How To Display Generic Tree

Now, Let’s write the code to display our generic tree.

This is the code for the display function we are creating.

CODE :

public static void display(Node node){
		String str = node.data + " -> ";
		for(Node child : node.children){
			str += child.data + " , ";
		}
		System.out.println(str + " .");
		
		for(Node child : node.children){
			display(child);
		}
	}

This display function will display the output in this pattern.

OUTPUT :

10 -> 20 , 30 , 40 ,  .
20 -> 50 , 60 ,  .
50 ->  .
60 ->  .
30 -> 70 , 80 , 90 ,  .
70 ->  .
80 -> 110 , 120 ,  .
110 ->  .
120 ->  .
90 ->  .
40 -> 100 ,  .
100 ->  .

This is the full code for the generic tree which we have created :

CODE

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
	// Node representation
	private static class Node{
			int data;
			ArrayList<Node> children = new ArrayList<>();
		}
		
		// This is the display function for printing the generic tree
	public static void display(Node node){
		
		String str = node.data + " -> ";
		for(Node child : node.children){
			str += child.data + " , ";
		}
		System.out.println(str + " .");
		
		for(Node child : node.children){
			display(child);
		}
		
	}
		
	public static void main (String[] args) throws java.lang.Exception
	{
		int arr[] = {10,20,50,-1,60,-1,-1,30,70,-1,80,110,-1,120,-1,-1,90,-1,-1,40,100,-1,-1,-1};
		
		Node root = null;
		Stack<Node> stack = new Stack<>();
		
		for(int i=0 ; i<arr.length ; i++){
			
			if(arr[i] == -1){
				stack.pop();
			} else {
				
				Node treeNode = new Node();
				treeNode.data = arr[i];
				
				if( stack.size() > 0 ){
					Node top = stack.peek();
					top.children.add(treeNode);
					stack.push(treeNode);
				} else {
					root = treeNode;
					stack.add(root);
				}
			
			}
			
		}
		
		display(root);
		
	}
}

OUTPUT

10 -> 20 , 30 , 40 ,  .
20 -> 50 , 60 ,  .
50 ->  .
60 ->  .
30 -> 70 , 80 , 90 ,  .
70 ->  .
80 -> 110 , 120 ,  .
110 ->  .
120 ->  .
90 ->  .
40 -> 100 ,  .
100 ->  .

Broz Who Code

CodingBroz

Leave a Comment

Your email address will not be published. Required fields are marked *