Lecture 297:- Inserting in a Binary Search Tree

Inserting a new node in a Binary Search Tree (BST) is a fundamental operation that maintains the ordering property of the tree. The new node is inserted in a way that it adheres to the BST property, i.e., all nodes in the left subtree have keys less than the current node's key, and all nodes in the right subtree have keys greater than the current node's key.

To insert a new node in a BST, we follow these steps:

1. If the tree is empty (root is null), create a new node and set it as the root.
2. Start at the root and traverse the tree to find the appropriate position to insert the new node.
3. If the value of the new node is less than the current node's value, move to the left subtree.
4. If the value of the new node is greater than the current node's value, move to the right subtree.
5. Repeat steps 3 and 4 until we find an empty position where the new node can be inserted.

Here's the C++ implementation of inserting a new node in a BST:

cppCopy code

#include <iostream> using namespace std; struct TreeNode {    int val;    TreeNode* left;    TreeNode* right;    TreeNode(int data) : val(data), left(nullptr), right(nullptr) {} }; // Function to insert a new node in a BST TreeNode* insertBST(TreeNode* root, int val) {    if (root == nullptr)        return new TreeNode(val);    if (val < root->val)        root->left = insertBST(root->left, val);    else if (val > root->val)        root->right = insertBST(root->right, val);    return root; } void inOrderTraversal(TreeNode* root) {    if (root == nullptr)        return;    inOrderTraversal(root->left);    cout << root->val << " ";    inOrderTraversal(root->right); } int main() {    // Create an empty binary search tree    TreeNode* root = nullptr;    // Insert nodes into the binary search tree    root = insertBST(root, 5);    root = insertBST(root, 3);    root = insertBST(root, 8);    root = insertBST(root, 2);    root = insertBST(root, 4);    root = insertBST(root, 7);    root = insertBST(root, 9);    // Perform an in-order traversal to see the sorted BST    cout << "In-order Traversal of BST: ";    inOrderTraversal(root);    cout << endl;    // Remember to free the allocated memory after use to avoid memory leaks.    delete root->left->left;    delete root->left->right;    delete root->left;    delete root->right->left;    delete root->right->right;    delete root->right;    delete root;    return 0; }

Output:

cssCopy code

In-order Traversal of BST: 2 3 4 5 7 8 9

In this example, we insert nodes with values 5, 3, 8, 2, 4, 7, and 9 into the BST and perform an in-order traversal to verify that the tree maintains its ordering property.