**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**

- DFS(Depth First Search): Depth-first traversal (Arkiletian traversal) is easily implemented via a stack
- Pre-Order
- Post Order
- In Order
- 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;

}

}

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:**

- Inserting an element in to a tree.
- Deleting an element from a tree.
- Search for an element
- Traversing a tree

**Auxiliary Operations:**

- Finding size of a tree
- Height of a tree
- LCA
- Sum of the tree
- Mirror Image etc.

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

## No comments:

## Post a Comment