Tree |

## Tree Terminology

Lets see some tree terminologies:-**Root:** The top node in a tree.**Child:** A node directly connected to another node when moving away from the Root.**Parent:** The converse notion of a child.**Siblings:** A group of nodes with the same parent.**Descendant:** A node reachable by repeated proceeding from parent to child.**Ancestor:** A node reachable by repeated proceeding from child to parent.**Leaf:** A node with no children.**Internal node:** A node with at least one child.**Degree:** The number of sub trees of a node.**Edge:** The connection between one node and another.**Path:** A sequence of nodes and edges connecting a node with a descendant.**Level:** The level of a node is defined by 1 + (the number of connections between the node and the root).**Height of node:** The height of a node is the number of edges on the longest path between that node and a leaf.**Height of tree:** The height of a tree is the height of its root node.**Depth:** The depth of a node is the number of edges from the tree’s root node to the node.**Forest:** A forest is a set of n ≥ 0 disjoint trees.

## Tree Node

Tree Node has a data part and references to its left and right child nodes.

`struct node {`

int data;

struct node *leftChild;

struct node *rightChild;

};

## Tree Traversals

- In-order Traversal
- Pre-order Traversal
- Post-order Traversal

### In-Order Traversal

**visit the left sub-tree, then the root and later the right sub-tree.**If a binary tree is traversed in-order, the output will produce sorted key values in an ascending order.

**4**->

**2**->

**5**->

**1**->

**3**

`Algorithm Inorder(tree)`

1. Recursively traverse the left subtree, i.e., call Inorder(left-subtree)

2. Visit the root

3. Recursively traverse the right subtree, i.e., call Inorder(right-subtree)

### Pre-Order Traversal

**first visit the root node, then the left sub tree and finally the right sub-tree.**

**1**->

**2**->

**4**->

**5**->

**3**

`Algorithm Preorder(tree)`

1. Visit the root.

2. Recursively traverse the left subtree, i.e., call Preorder(left-subtree)

3. Recursively traverse the right subtree, i.e., call Preorder(right-subtree)

### Post-Order Traversal

**first visit the left sub tree, then the right sub-tree and finally the root node.**

**4**->

**5**->

**2**->

**3**->

**1**

`Algorithm Postorder(tree)`

1. Recursively traverse the left subtree, i.e., call Postorder(left-subtree)

2. Recursively traverse the right subtree, i.e., call Postorder(right-subtree)

3. Visit the root

## Binary Search Tree(BST)

## Operations on a Binary Search Tree

**1. Search**

**2. Insertion**

**3. Deletion**

**Search Operation**

**Algorithm**

`node* search(int data){`

struct node *current = root;

printf("Visiting elements: ");

while(current->data != data){

if(current != NULL) {

printf("%d ",current->data);

//go to left tree

if(current->data > data){

current = current->leftChild;

}//else go to right tree

else {

current = current->rightChild;

}

//not found

if(current == NULL){

return NULL;

}

}

}

return current;

}

### Insert Operation

**Algorithm**

`Node * Insert(Node * root, int data)`

{

if(root == nullptr)

{

Node * NN = new Node();

root = NN;

root->data = data;

root->left = root ->right = NULL;

}

else

{

if(data < root->data)

{

root->left = Insert(root->left, data);

}

else

{

root->right = Insert(root->right, data);

}

}

return root;

}

### Deletion Operation in BST

**Case 1: Deleting a Leaf node (A node with no children)**

`Step 1: Find the node to be deleted using search operation`

Step 2: Delete the node using free function (If it is a leaf) and terminate the function.

**Case 2: Deleting a node with one child**

`Step 1: Find the node to be deleted using search operation`

Step 2: If it has only one child, then create a link between its parent and child nodes.

Step 3: Delete the node using free function and terminate the function.

**Case 3: Deleting a node with two children**

`Step 1: Find the node to be deleted using search operation`

Step 2: If it has two children, then find the largest node in its left subtree (OR) the smallest node in its right subtree.

Step 3: Swap both deleting node and node which found in above step.

Step 4: Then, check whether deleting node came to case 1 or case 2 else goto steps 2

Step 5: If it comes to case 1, then delete using case 1 logic.

Step 6: If it comes to case 2, then delete using case 2 logic.

Step 7: Repeat the same process until node is deleted from the tree.