A non-linear data structure.

The tree may be defined as a finite collection of special data items called the** nodes.**

The nodes of the tree are arranged in the hierarchy structure to represent the **parent-child relationship.**

The first node is linked to some other nodes of the tree which in turn are linked to some other nodes.

All the nodes of the tree are called internal nodes except **the root and the leaf nodes.**

The leaf nodes are sometimes called as** external nodes.**

A binary tree with n nodes can have maximum** n-1 nodes.**

Node with zero descendants is called **leaf nodes.**

The tree is a finite set of data elements called nodes such that there is a special node called node of the tree; and remaining nodes are partitioned into a number of mutually exclusive subsets, which are themselves trees.

The edge that connects the nodes are called branches, and the number of branches connected to a particular node is called the degree of that node.

**Root** − Node at the top of the tree is called root.**Parent **− Any node except the root node has one edge upward to a node called a parent. **Child **− Node below a given node connected by its edge downward is called its child node.**Sibling** – Child of the same node are called siblings **Leaf** − Node which does not have any descendant or the node with zero degrees is called a leaf node. **Subtree** − Sub tree represents descendants of a node.

• **Levels** − The level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2 and so on.

• **Keys** − Key represents the value of a node based on which a search operation is to be carried out for a node.**Depth of the tree:** The length of the longest path from the root to any terminal node is called the

**depth of the tree.**

The root is always assigned

**level zero.**

The level of the node is called

**the depth of the node.**

The largest level of the tree is called

**the depth of the tree.**

The minimum depth of the tree is

**(log**where n is the number of the node.

_{2}n+1)**Binary Tree**

Each node can have either 0, 1, 2 children.

Therefore a binary tree is a tree that is either empty or each node can have a maximum of two children.

The node on the left of any node is called its

**left child**and the node on the right of any node is called the

**right child**.

A **binary tree** can be defined as a finite collection of nodes where each node is divided into three parts containing **left child address, information, **and** right child address.**

Classification of Binary Tree

If all the terminal nodes of a tree are at level d, where d is the depth of the tree then such a tree is called a strictly binary tree.

The maximum possible node at any level is 2^{n}, where n is the level number.

**Almost Complete Binary Tree**

If all the terminal nodes of a tree are at a level d or d-1, where d is the depth of the tree, then such trees are called **almost complete binary trees**.**Linked Representation of tree** **using array**

A tree is a collection of data that can be easily implemented using array.

The data items of the tree are maintained in the form of nodes divided into three parts.

Therefore, the tree may be maintained or represented by three parallel arrays of the same size.

Tree[0] contains the root of the tree

The left of the Tree[0] contains 1 which means the left subtree is at Tree[1], and the right field of the Tree[0] contains 2 which means the right subtree is at Tree[2].

Other nodes are represented in a similar manner.

The tree using array may be implemented in C by using an array of structures.

In C

struct node

{

int Left;

int Right;

int Info;

}; struct node Tree[12]

Therefore, Tree is a collection of 12 nodes each containing integer type of info and integer type of left and right fields because array index is also an integer and we use the array index as a pointer to a node

Tree[n] represents the node of the tree pointed by the index value n. For example, Tree[6] is the node of the tree pointed by index value 6., that is,**| 4 | C |8 |**

Tree[n].info–> represents the info part of the node of the tree pointed by an index value.

List[6].info=C

Tree[n].left –> represents the info part of the node of the tree pointed by an index value n.

List[6].left =4

represents the address of the left subtree of the node pointed by index 6.

Tree[n].right –> represents the right field of the node of the tree pointed by an index value n.

List[6].right=8.

Represents the address of the right subtree of the node pointed by index 6.**Sequential Representation of Binary Tree**

Instead of using three parallel arrays, the complete or almost complete binary tree can be represented using a single array.

In this method, the number is assigned to each node in a sequence from leftmost nodes to rightmost nodes, and with the condition that the root is always assigned to 1.

The left child of any node says k is placed at [2*k] and the right child is placed at [2*k+1].

The size of the array depends on the depth of the tree and it is given by

The father of any node k can be determined by k/2.

** Linked List Representation Using Pointer(Dynamic Representation**)

The dynamic representation does not have any size limitation and uses space proportional to the actual number of elements of the tree.

In C:

struct node

{ node *left;

node* right;

int info;

} struct node * root;**Traversal of Binary Tree**

Process in which each node is visited exactly once.

There are possibly 3! factorial ways i.e. 6 ways to Traverse a tree

But only **3 **are important to us.

Namely,**In-order Traversal**

Visit the left subtree in the in-order (L).

Visit the node (N).

Visit the right subtree in the in-order(R).

**Pre-order Traversa**l

Visit the node (N).

Visit the left subtree in the in-order (L).

Visit the right subtree in the in-order(R).

**Post-order Traversal**

Visit the left subtree in the in-order (L).

Visit the right subtree in the in-order(R).

Visit the node (N).

## Leave a Reply