# Binary Tree and Tree Traversals using Java

The root node of a tree is the node with no parents. There is at most one root node in a rooted tree.A leaf node has no children.
The depth of a node n is the length of the path from the root to the node. The set of all nodes at a given depth is sometimes called a level of the tree. The root node is at depth zero.
The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a height of zero.
Siblings are nodes that share the same parent node.
A node p is an ancestor of a node q if it exists on the path from q to the root. The node q is then termed a descendant of p.
The size of a node is the number of descendants it has including itself.
In-degree of a node is the number of edges arriving at that node.
Out-degree of a node is the number of edges leaving that node.
The root is the only node in the tree with In-degree = 0.

TreeNode Class

```
public class TreeNode{

TreeNode leftNode;
TreeNode rightNode;
int data;

public TreeNode(int value){
data = value;
leftNode = rightNode = null;
}

public void insert(int value){
if (value < data){
if (leftNode == null)
leftNode = new TreeNode(value);
else
leftNode.insert(value);
}
else if (value > data){
if (rightNode == null)
rightNode = new TreeNode(value);
else
rightNode.insert(value);
}
}

}
```

Preorder Traversal

```  preorder(node)
if node = null then return
print node.value
preorder(node.left)
preorder(node.right)
```

Postorder Traversal

```  postorder(node)
if node = null then return
postorder(node.left)
postorder(node.right)
print node.value
```

Inorder Traversal

```  inorder(node)
if node = null then return
inorder(node.left)
print node.value
inorder(node.right)
```

Queue based Level order Traversal

```levelorder(root)
q = empty queue
q.enqueue(root)
while not q.empty do
node := q.dequeue()
visit(node)
if node.left ≠ null
q.enqueue(node.left)
if node.right ≠ null
q.enqueue(node.right)
```

Tree Class

```
public class Tree {

private TreeNode root;

Queue queue = new Queue();

public Tree(){
root = null;
}

public void insertNode(int value){

if ( root == null)
root = new TreeNode(value);
else
root.insert(value);
}

public void preorderTraversal(){
preorder(root);
}

public void inorderTraversal(){
inorder(root);
}

public void postorderTraversal(){
postorder(root);
}

public void levelorderTraversal(){
levelorder(root);
}

public void levelorder(TreeNode node){
if (node == null)
return;

if (node == root)
queue.offer(node);

if (node.leftNode != null)
queue.offer(node.leftNode);
if (node.rightNode != null)
queue.offer(node.rightNode);

System.out.printf("%d ", queue.poll().data);

levelorder(queue.peek());
}

public void preorder(TreeNode node){

if (node == null)
return;

System.out.printf("%d ", node.data);
preorder(node.leftNode);
preorder(node.rightNode);

}

public void postorder(TreeNode node){

if (node == null)
return;

postorder(node.leftNode);
postorder(node.rightNode);
System.out.printf("%d ", node.data);
}

public void inorder(TreeNode node){

if (node == null)
return;

inorder(node.leftNode);
System.out.printf("%d ", node.data);
inorder(node.rightNode);
}

}

```

TreeTest Class

```import java.util.Random;

public class TreeTest {

public static void main(String[] args){
Tree tree = new Tree();
int value;
Random random = new Random();

System.out.println("Inserting values");
for (int i=1; i<=10;i++){
value=random.nextInt(100);
System.out.printf("%d ", value);
tree.insertNode(value);
}
System.out.println();
System.out.println("Preorder");
tree.preorderTraversal();
System.out.println();
System.out.println("Postorder");
tree.postorderTraversal();
System.out.println();
System.out.println("Inorder");
tree.inorderTraversal();
System.out.println();
System.out.println("Levelorder");
tree.levelorderTraversal();
}
}

```

Of course, you need the Queue DS for level order traversal.

```
import java.util.ArrayList;
import java.util.List;

public class Queue {

private List qlist;

public Queue(){
qlist = new ArrayList();
}

public void offer(TreeNode o){
if (qlist.isEmpty())
else
}

public TreeNode poll(){
if (qlist.isEmpty())
return null;
else
return qlist.remove(0);
}

public TreeNode peek(){
if (qlist.isEmpty())
return null;
else
return qlist.get(0);
}
}

```

And finally the output

```Inserting values
87 77 81 89 4 26 23 27 57 1
Preorder
87 77 4 1 26 23 27 57 81 89
Postorder
1 23 57 27 26 4 81 77 89 87
Inorder
1 4 23 26 27 57 77 81 87 89
Levelorder
87 77 89 4 81 1 26 23 27 57
```