## Thursday, 30 July 2015

### Trees In Data Structure

What is Tree:
A tree is a non linear data structure. A tree is a way of representing the hierarchical nature of a structure in graphical form.
A tree is a set of nodes that either:is empty or has a designated node, called the root, from
which hierarchically descend zero or more sub trees, which are also trees.

Terminology
• The Degree of a node is the number of sub trees of the nodes
• The Node with zero degree or has no children is called leaf or terminal node(E,H,C,I,K,G).
• A node that has subtrees is the parent of the roots of the subtrees
• The roots of these subtrees are the children of the node.
• Children of the same parent are siblings.
• The ancestors  of a node are all the nodes along the path from the root to the node.
• Root of tree is the node with no parents. There can be at most one root in a tree(node A in the above example)
• Children of same parent are called siblings(B,C, D are siblings).
• The height of a node is the length of the path from that node to deepest node. Height of a tree is the length of a path from root to deepest node in the tree.(Height of tree is 6 in the above example A to M)
• The depth of a node is the length of the path from root to that node.(depth of F is 3, A-D-F)

Binary Tree:

A tree is called binary tree if each node has zero child, one child or two children. Empty  tree is also a binary tree.
Example:

Binary Tree Traversal
1. DFS(Depth First Search): Depth-first traversal (Arkiletian traversal) is easily implemented via a stack
1. Pre-Order
2. Post Order
3. In Order
2. BFS (Breath First Search) is also known as level order in Tree. breadth-first traversal is easily implemented via a queue

Structure of Binary Tree:

public class BinaryTree {
private int data;
private BinaryTree left;
private BinaryTree right;

public BinaryTree() {
}
public BinaryTree(int data) {
this.data=data;
}
public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public BinaryTree getLeft() {
return left;
}
public void setLeft(BinaryTree left) {
this.left = left;
}
public BinaryDataTree getRight() {
return right;
}
public void setRight(BinaryTree right) {
this.right = right;
}

}

Operations on Binary Tree:
1. Inserting an element in to a tree.
2. Deleting an element from a tree.
3. Search for an element
4. Traversing a tree
Auxiliary Operations:
1. Finding size of a tree
2. Height of a tree
3. LCA
4. Sum of the tree
5. Mirror Image etc.

Note: Will explain different problem on tree in next couple of articles. Subscribe for it.