Definition of a Tree:

A tree is a set of one or more nodes T such that:

(i).There is a specially designated node called a root

(ii).The remaining nodes are partitioned into n disjointed

set of nodes T1, T2,…,Tn, each of which is a tree.

Degree of a Node of a Tree:

The degree of a node of a tree is the number of subtrees having this node as a root. In other words,the degree is the number of descendants of a node. If the degree is zero, it is called a terminal or leaf node of a tree.

Degree of a Tree:

The degree of a tree is defined as the maximum of degree of the nodes of the tree, that is, degree of tree = max(degree(node i) for I = 1 to n)

Level of a Node:

We define the level of the node by taking the level of the root node as 1, and incrementing it by 1 as we move from the root towards the subtrees.We then define the depth of the tree to be the maximum value of the level of the node of the tree.

Binary tree:

A tree T is finite set of nodes, such that

(i).T is empty(called Empty binary tree),

(ii).T contains specially designed node called the root

of T,and the remaining nodes of T form T1 and T2

which are called as left subtree and right subtree.

Binary Search Tree:

Def:

A Binary Tree is said to be Binary Search Tree, the values in the left subtree should be less than that of root element and the values in the right subtree should be greater than that of root element.

Tree Traversals:

Traversing is nothing but visiting all the nodes of a Tree exactly once.

In-order Traversal:

•visit left sub tree of the Root node using In-order traversal

•visit Root node

•visit right sub tree of the Root node using In-order traversal

Pre-order Traversal:

•visit Root node

•visit left sub tree of the Root node using Pre-order Traversal

•visit right sub tree of the Root node using Pre-order Traversal

Post-order Traversal:

•visit left sub tree of the Root node using Post-order Traversal

•visit right sub tree of the Root node using Post-order Traversal

•visit Root node