Trees using Java

In this blog, we are going to see about Tree’s, Now why trees? Tree is also a dynamic structure that can be established primarily on Linked list

In linked list items are in order but in trees, the items are branched.

→Binary Tree

→Binary search tree

→AVL tree

→Red black tree

→N-ary tree

→General Tree

Now I’m going to cover all these topics, but will try to learn core concept and then you are ready to create other types!

Let’s see Binary Search Tree

Every node in a binary search tree comprises the following attributes.

1. key/data: The value stored in the node.
2. left: The pointer to the left child.
3. right: The pointer to the right child.
4. p: The pointer to the parent node.

So, the structure of class is to be like

class Node{

int date;

Node left,right;

}

Node parent/root;

Since, as you are familiar with double linked list, this is not a big deal.

Here is unique property of binary search tree

Let x be a node in a binary search tree.

• If y is a node in the left subtree of x, then y.key ≤ x.key

This is not complicated. Close your eye for a second and then think the concept.

We will see what’s binary search tree first

Binary search tree is tree having all greater values to right node in left node

Insertion operation →

We can solve this recursively

1.If root is null then insert data

2.else if value is greater than root data then root of right equal to insert of root of right and value

3.else if value is lesser than root data then root of left equal to insert of root of left and value

Now you may have got idea to do this without recursively

1. while root is not null loop
2. If value is greater than root data then root is equal to root of right
3. Else value less than root data then root is equal to root of left
4. end while loop
5. root.data = value

Both have same logic but some alteration needed.

Coming to traversal there are three ways to traverse a tree.

Each tree has unique approach to display elements. Don’t worry it’s magic time! Remember this formula and whenever you have to do traversal use this formula

→Inorder

→Preorder

→Postorder

Let’s see one by one,

Inorder Traversal :

“Left, Root, Right”

Let’s take example tree and try to decode the formula

I’m going consider myself as a machine and going to give you output

Output cycle = []

root = 15

root.left ? 24 : 15

root.left ? 35 : 24

Output cycle = [35]

root = 24

Output cycle = [35, 24]

root = 15

Output cycle = [35, 24, 15]

root.right ? 54 : 15

root.left ? 62 : 54

Output cycle = [35, 24, 15, 62]

root = 54

Output cycle = [35, 24, 15, 62, 54]

root.right ? 13 : 54

Output cycle = [35, 24, 15, 62, 54, 13]

So hope you have understood the concept

We are diving into code now, Inorder is name of function

1. If node is null then return ;
2. inorder of node of left
3. print node of data
4. inorder of node of right

Simple right?

So, You know the logic for inorder, so it’s easy to learn preorder and postorder

Formula for Preorder :

“Root, Left, Right”

So in code just the order has to be changed

1. If node is null then return ;
2. print node of data
3. inorder of node of left
4. inorder of node of right

Formula for Postorder :

“Left, Right, Root”

So in code just the order has to be changed

1. If node is null then return ;
2. Inorder of node of left
3. Inorder of node of right
4. print node of data

All the operations of binary search tree is completed,

Now it’s time to move to other tree types.