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.