6.3 Tree height, level and depth

Understanding the concepts of height, level, and depth in a tree is essential for analyzing its structure and performance characteristics. Below is a detailed explanation of each term:

1. Tree Height

• Definition: The height of a tree is the length of the longest path from the root node to a leaf node. It is measured by the number of edges on the longest downward path from the root to a leaf.
• Calculation:
  • If a tree has no nodes (an empty tree), its height is typically defined as -1.
  • If the tree has only one node (the root), its height is 0.
  • For any other node, the height is calculated as: $$\text{Height}=1+\max (\text{Height of left subtree},\text{Height of right subtree})$$
• Example:
  • For the following tree:
     A
    / \
    B C
    / \
    D E
  • The height of this tree is 2, as the longest path from the root (A) to a leaf (D or E) contains 2 edges.

2. Level

• Definition: The level of a node is defined as the number of edges in the path from the root node to that particular node. The root node is at level 0, its children are at level 1, and so on.
• Calculation:
  • The level of a node can be determined based on its depth.
  • The level can be calculated as: $$\text{Level}=\text{Depth of the node}$$
• Example:
  • In the previous tree:
     A (Level 0)
    / \
    B C (Level 1)
    / \
    D E (Level 2)
  • Here, the node A is at level 0, nodes B and C are at level 1, and nodes D and E are at level 2.

3. Depth

• Definition: The depth of a node is the number of edges from the root node to that node. It measures how far down the tree the node is located.
• Calculation:
  • The depth of a node can be calculated by counting the number of edges from the root to that node. Alternatively, it can also be defined in terms of levels: $$\text{Depth}=\text{Level of the node}$$
• Example:
  • Using the same tree:
     A
    / \
    B C
    / \
    D E
  • The depth of:
    • Node A is 0 (0 edges from root).
    • Nodes B and C are 1 (1 edge from root).
    • Nodes D and E are 2 (2 edges from root).

6.4 Binary Search Tree

A Binary Search Tree (BST) is a specialized type of binary tree that maintains a sorted order of its elements. It allows for efficient searching, insertion, and deletion operations, making it a widely used data structure in computer science.

Properties of Binary Search Tree

1. Node Structure:
   • Each node contains a key (value), a left child, and a right child.
2. Ordering Property:
   • For any given node:
     • All values in the left subtree are less than the node’s value.
     • All values in the right subtree are greater than the node’s value.
3. No Duplicate Nodes:
   • A standard BST does not allow duplicate values. Each value must be unique.

Operations on Binary Search Tree

1. Insertion:
   • To insert a new value into the BST:
     • Start at the root and compare the value to be inserted with the current node’s value.
     • If the new value is less than the current node’s value, move to the left child; if it’s greater, move to the right child.
     • Repeat this process until a null position is found, then insert the new node.

   C Code for Insertion:

   struct Node {
   int data;
   struct Node* left;
   struct Node* right;
   };

   struct Node* insert(struct Node* root, int data) {
   if (root == NULL) {
   struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
   newNode->data = data;
   newNode->left = NULL;
   newNode->right = NULL;
   return newNode;
   }
   if (data < root->data) {
   root->left = insert(root->left, data);
   } else {
   root->right = insert(root->right, data);
   }
   return root;
   }

2. Searching:
   • To search for a value in the BST:
     • Start at the root and compare the target value with the current node’s value.
     • If the target value matches, return the node.
     • If it’s less, move to the left child; if greater, move to the right child.
     • Repeat this until the value is found or a null position is reached.

   C Code for Searching:

   struct Node* search(struct Node* root, int key) {
   if (root == NULL || root->data == key) {
   return root;
   }
   if (key < root->data) {
   return search(root->left, key);
   }
   return search(root->right, key);
   }
3. Deletion:
   • To delete a node from the BST, there are three main cases:
     • Node with no children: Simply remove the node.
     • Node with one child: Remove the node and link its parent to its child.
     • Node with two children: Find the inorder successor (smallest in the right subtree) or inorder predecessor (largest in the left subtree), replace the node’s value with that of the successor/predecessor, and delete the successor/predecessor.

   C Code for Deletion:

   struct Node* minValueNode(struct Node* node) {
   struct Node* current = node;
   while (current && current->left != NULL) {
   current = current->left;
   }
   return current;
   }

   struct Node* deleteNode(struct Node* root, int key) {
   if (root == NULL) return root;

   if (key < root->data) {
   root->left = deleteNode(root->left, key);
   } else if (key > root->data) {
   root->right = deleteNode(root->right, key);
   } else {
   // Node with one child or no child
   if (root->left == NULL) {
   struct Node* temp = root->right;
   free(root);
   return temp;
   } else if (root->right == NULL) {
   struct Node* temp = root->left;
   free(root);
   return temp;
   }

   // Node with two children: Get the inorder successor
   struct Node* temp = minValueNode(root->right);
   root->data = temp->data; // Copy the inorder successor’s content to this node
   root->right = deleteNode(root->right, temp->data); // Delete the inorder successor
   }
   return root;
   }

4. Traversal:
   • Common traversal methods include:
     • Inorder Traversal: Visits nodes in sorted order (Left, Root, Right).
     • Preorder Traversal: Useful for creating a copy of the tree (Root, Left, Right).
     • Postorder Traversal: Useful for deleting a tree (Left, Right, Root).

   C Code for Inorder Traversal:

   void inorderTraversal(struct Node* root) {
   if (root != NULL) {
   inorderTraversal(root->left);
   printf(“%d “, root->data);
   inorderTraversal(root->right);
   }
   }

Advantages of Binary Search Tree

• Efficiency: Operations like search, insert, and delete can be performed in O(log n) time on average if the tree is balanced.
• Sorted Data: Inorder traversal of a BST yields sorted data.

Disadvantages of Binary Search Tree

• Unbalanced Trees: In the worst case (e.g., inserting sorted data), the tree can become unbalanced, leading to O(n) time complexity for operations.
• Complexity of Balancing: Maintaining balance (e.g., using AVL trees or Red-Black trees) adds complexity to implementation.

6.5 Insertion, Deletion, Traversals (pre-order, post-order and in-order ), Search in BST

In this section, we will discuss the key operations of a Binary Search Tree (BST), including insertion, deletion, traversals (pre-order, post-order, and in-order), and search. Each operation is explained with accompanying C code examples.

1. Insertion in BST

Insertion in a BST involves placing a new node in the correct position according to the BST properties.

C Code for Insertion:

2. Deletion in BST

Deletion from a BST can be handled in three cases:

• Node with no children (leaf node)
• Node with one child
• Node with two children

C Code for Deletion:

3. Traversals in BST

Traversing a BST can be done in different orders: Pre-order, In-order, and Post-order.

• In-order Traversal: Left, Root, Right (produces sorted order).
• Pre-order Traversal: Root, Left, Right.
• Post-order Traversal: Left, Right, Root.

C Code for Traversals:

// In-order Traversal
void inorderTraversal(struct Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf(“%d “, root->data);
inorderTraversal(root->right);
}
}

// Pre-order Traversal
void preorderTraversal(struct Node* root) {
if (root != NULL) {
printf(“%d “, root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}

// Post-order Traversal
void postorderTraversal(struct Node* root) {
if (root != NULL) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf(“%d “, root->data);
}
}

4. Search in BST

Searching for a value in a BST involves comparing the target value to the current node’s value and recursively traversing left or right based on the comparison.

C Code for Search:

Example Usage

Here’s how to use the above functions in a complete program: