# Trees

**TREE**

Tree is defined as T (V,E) where V = set of vertices and E = set of edges.In a tree there is exactly one edge between a pair of vertices and there are no cycles and self loops.

The degree of a node in the tree is defined as the maximum number of children that node can hold.A tree can never be empty, but binary tree may be empty.

Internal node ( I ): A node having minimum of 1 child is know as internal node.

Leaf node ( L ): A node having no children.

External node ( E ): The replacement of null leaves are external nodes.

**Properties:-**

(i) For 'n' nodes there are (n-1) edges.

(ii) Let,

n

_{0}= number of nodes with degree 0.
n

_{2}= number of nodes with degree 2.
n

_{0}= n_{2 }+ 1
(iii) ( In heap array ) If child is at location i (index starts from 0 ) then parent is at location [ (i-1)/2].

If parent is at location i ( index starts at 0 ) then left child is at location 2i + 1 and Right child is at location 2i + 2.

(iv) (In heap array) If parent is at location i (indexing at 1 ) then Left child is at location 2i and Right child is at location 2i + 1.

If child is at location i (indexing at 1 ) then parent is at location [i/2].

(v) In a linked representation of binary tree,if there are 'n' nodes then number of NULL links = n + 1.

**Complete Binary**Tree is a tree in which nodes are inserted/filled from left to right. All the leaves may not be at the same level.

**Full Binary Tree**is a tree in which every node has exactly 2 children and all the leaves are at the same level.

All full binary trees are complete binary trees but vice versa is not true.

**Strict Binary Tree**is a tree in which each node has exactly 0 or 2 children.

A complete n-any tree is one in which every node has '0' or 'n' sons. If 'x' is the number of internal nodes of a complete n-any tree, the number of leaves in it is: x(n-1) + 1.

Let T(n) be the number of different binary search trees on n-distinct element , then

T(n) = ∑ T(k-1) T(n-k+1).

In binary tree, Rank (or) Index of any node.

**Rank(i) = (Number of nodes in left subtree of i) + 1**

In a m-ary tree (degree = m), if ni is number of nodes of degree 'i'.

( i = 0,1,.....,m) then n0 (leaf nodes) = 1 + ⅀ (i - 1)ni.

Maximum size of array to store a binary tree with 'n' nodes = 2

^{n}- 1.
Minimum size of array to store a binary tree with 'n' = 2

^{[log(n-1)]}- 1.
Maximum height possible for a binary tree with 'n' nodes = n.

Minimum height possible for a binary tree with 'n' nodes = Log

_{2 }n.
Maximum number of nodes in a binary tree of height 'h' = 2

^{h+1}– 1.
Total number of binary trees possible with n nodes =

^{2n}C_{n}/ (n+1)
For non-empty binary tree , if n is number of nodes and e is the number of edge , then n = e + 1.

**Binary Tree Traversals**

Traversing a tree means a visiting each node in a specified order.

Traversal Techniques

1. Preorder ( Root , Left, Right).

2.Inorder (Left, Root,Right)

3.Postorder(Left,Right,Root)

## No comments