## Trees

As you already know, Arrays, Linked Lists, Stacks and Queues are linear data structures. But, trees are hierarchical data structures. There are different types of trees. We will now discuss a binary tree.

#### Important terms in a tree:

• Nodes: Tree represents nodes connected by edges
• Root: The topmost node is called root of the tree
• Children: The elements directly under an element are its children
• Parent: The element directly above something is called its parent
• Path: The sequence of nodes along the edges of a tree
• Leaf: The node which doesn’t have any child
• Levels: It represents the generation of a node. If the root node is at level 0, then its next child node is at level , its grandchild is at level 2, and so on.
• Subtree: It represents the descendants of a node

## Importance of Trees

• Trees provide insertion and deletion of elements which are quicker than Arrays and slower than Unordered Linked Lists
• In trees, nodes are linked using pointers. So, trees do not have an upper limit on number on nodes
• Trees provide searching of elements which is quicker than Linked List and slower than arrays
• Trees can be used to store information that forms a hierarchy. For example, the file system on a computer

A tree whose elements have at most 2 children is called a binary tree. We name those children as left and right child.

• The maximum number of nodes at level ‘L’ of a binary tree is 2L-1
For root, `L = 1`, number of nodes = 21-1 = 1
Assume that maximum number of nodes on level l is 2l-1
Since in Binary tree every node has at most 2 children, next level would have twice nodes, i.e. `2 * 2L-1`.
• The maximum number of nodes in a binary tree of height ‘h’ is `2h-1`.
• In Binary tree where every node has 0 or 2 children, number of leaf nodes is always one more than nodes with two children

## Types of Binary Tree:

• Full Binary Tree: A Binary Tree is full if every node has 0 or 2 children. You can even say, a Binary Tree is full if all nodes except leaves have two children.
In a Full Binary Tree, number of leaf nodes is number of internal nodes + 1
``L= n+1``

Where L = Number of leaf nodes, n = Number of internal nodes

• Complete Binary Tree: A Complete Binary Tree is a Binary Tree if all levels are completely filled except the last level. The last level has all keys as left as possible.
• Perfect Binary Tree: A Perfect Binary Tree is a Binary Tree in which all internal nodes have two children and all leaves are at the same level.
A Perfect Binary Tree of height h has 2h-1 node
• Balanced Binary Tree: A Balanced Binary Tree is a Binary Tree whose height is O(Logn) where n is the number of nodes.

Now, let us take a simple example to calculate the height of a tree. First of all, we have to implement a tree data structure as follows:

``````
public class BinaryTree {
TreeNode root;
public static class TreeNode {
TreeNode left;
TreeNode right;
Object data;
TreeNode(Object data) {
this.data = data;
left = right = null;
}
}
}
``````

Now, we have to find the height using the following code:

``````
public class HeightOfTree {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
/**
* Binary Tree in our example, height = 2
* 		1		(Root)
* 	  2	  3		(Level 1)
*  4    	 5		(Level 2)
*/
binaryTree.root = new TreeNode(1);
binaryTree.root.left = new TreeNode(2);
binaryTree.root.right = new TreeNode(3);
binaryTree.root.left.left = new TreeNode(4);
binaryTree.root.right.left = new TreeNode(5);
int heightOfTree = height(binaryTree.root);
System.out.printf("Height of tree is %d", heightOfTree);
}
public static int height(TreeNode root) {
if (root == null)
return -1;
int leftHeight = height(root.left);
int rightHeight = height(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
}
``````

Output:

``````
Height of tree is 2
``````

## Binary Search Tree:

A Binary Search Tree, is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains nodes with lesser keys than the node’s key
• The right subtree of a node contains nodes with greater keys than the node’s key
• The left and right subtree also needs to be a Binary Search Tree

Binary Search Tree has the ability to reduce the time complexity of fundamental operators like add, remove, and search. All these operations can be performed in O(log(n)) time.

Binary Search Tree has the unique property , where for each node, the data in the left child is less than or equal to the data in the node and the data in the right child is greater than or equal to the data in the node. This is the improvement in speed.

Example: Let us implement BST node first

``````
public class BstNode {
private BstNode left;
private BstNode right;
private Integer data;
public BstNode(Integer data) {
this.data = data;
}
public BstNode getLeft() {
return left;
}
public void setLeft(BstNode left) {
this.left = left;
}
public BstNode getRight() {
return right;
}
public void setRight(BstNode right) {
this.right = right;
}
public Integer getData() {
return data;
}
}
``````

Now let us implement Binary Search Tree:

``````
public class BinarySearchTreeImpl {

private BstNode root;

public boolean isEmpty() {

return (this.root == null);
}

public void insert(Integer data) {

System.out.print("[input: "+data+"]");
if(root == null) {
this.root = new BstNode(data);
System.out.println(" -> inserted: "+data);
return;
}

insertNode(this.root, data);
System.out.print(" -> inserted: "+data);
System.out.println();
}

private BstNode insertNode(BstNode root, Integer data) {

BstNode tmpNode = null;
System.out.print(" ->"+root.getData());
if(root.getData() >= data) {
System.out.print(" [L]");
if(root.getLeft() == null) {
root.setLeft(new BstNode(data));
return root.getLeft();
} else {
tmpNode = root.getLeft();
}
} else {
System.out.print(" [R]");
if(root.getRight() == null) {
root.setRight(new BstNode(data));
return root.getRight();
} else {
tmpNode = root.getRight();
}
}
return insertNode(tmpNode, data);
}
public static void main(String a[]) {
BinarySearchTreeImpl bst = new BinarySearchTreeImpl();
bst.insert(10);
bst.insert(20);
bst.insert(21);
bst.insert(8);
bst.insert(6);
bst.insert(16);
bst.insert(23);
}
}

``````

Output:

``````
[input: 10] -> inserted: 10
[input: 20] ->10 [R] -> inserted: 20
[input: 21] ->10 [R] ->20 [R] -> inserted: 21
[input: 8] ->10 [L] -> inserted: 8
[input: 6] ->10 [L] ->8 [L] -> inserted: 6
[input: 16] ->10 [R] ->20 [L] -> inserted: 16
[input: 23] ->10 [R] ->20 [R] ->21 [R] -> inserted: 23
``````

## AVL Tree:

AVL Tree is a self-balancing Binary Search Tree. In a binary search tree, the search time is identical to a linked list, i.e, log n.

The AVL tree balances itself by making rotations when the tree becomes unbalanced, O(logn) search time is guaranteed. So, the AVL tree is very consistent in terms of performance. Sorts can be implemented with the AVL trees. Despite having O(nlogn) time complexity, other sorting algorithms like quick or merge sort generally outperform.

#### Insertion:-

Insertion in AVL tree is performed in the same way as it is performed in a Binary Search Tree. But, it may lead to violation in the AVL tree property and therefore the tree may need balancing. The tree can be balanced by applying rotations.

#### Deletion:-

Deletion in AVL tree is also performed in the same way as it is performed in a Binary Search Tree. Deletion may also hamper the balance of the tree, so, various types of rotations are used to rebalance the trees.

## B Tree:-

B Tree is a specialized m-way tree that can be widely used for disk access. A B-Tree of order m can have at most m-1 keys and m children.

One of the main reason of using B tree is its capability to store large number of keys in a single node and large key values by keeping the height of the tree relatively small.

B tree of order m contains all the properties of an M way tree. In addition, it contains the following properties

• Every node in a B-Tree contains at most m children
• Every node in a B-Tree except the root node and the leaf node contain at least m/2 children
• The root nodes must have at least 2 nodes
• All leaf nodes must be at the same level

It is not necessary that, all the nodes contain the same number of children but, each node must have m/2 number of nodes.

B-Tree is used to index the data. It provides fast access to the actual data stored on the disks.

To search an un-indexed and unsorted database containing n key values, it needs O(n) running time in worst case. But, if we use B-Tree to index this data base, it will take O(logn) time to search in worst case.