Insert in BST (Binary Search Tree) 🎯

Welcome to our comprehensive guide on Insert in BST! In this lesson, we'll delve into the fascinating world of Data Structures and Algorithms, focusing on Binary Search Trees (BST). By the end of this tutorial, you'll be able to insert elements into a BST with confidence. 💡

Understanding Binary Search Tree (BST) 📝

Before we dive into inserting elements, let's quickly understand what a BST is. A BST is a type of binary tree data structure where each node has at most two children: a left child and a right child. The tree is ordered in such a way that the key value of each node is greater than or equal to its left subtree's keys and less than or equal to its right subtree's keys.

Inserting Elements into a BST 📝

Now, let's learn how to insert elements into a BST. We'll follow these simple steps:

Initialization: Create an empty BST (we'll represent a BST as a Javascript object).

javascript

let root = null;

Inserting a new element: To insert a new element, we'll perform a recursive search in the tree until we find the appropriate place to insert it. If the tree is empty, we set the new element as the root. If the new element's value is less than the current node's value, we move to the left subtree. Otherwise, we move to the right subtree.

javascript

function insert(node, data) {
  if (!node) { // if the node is null, we create a new node with the given data
    return { value: data };
  }

  if (data < node.value) {
    node.left = insert(node.left, data); // move to the left subtree
  } else {
    node.right = insert(node.right, data); // move to the right subtree
  }

  return node; // return the updated node
}

// To insert a new element, say 5, in an empty tree
root = insert(root, 5);

💡 Pro Tip: The time complexity of inserting a new element in a BST is O(log n), making it an efficient data structure for large datasets.

Practical Application 📝

Let's build a simple BST and insert some elements to better understand how it works.

javascript

// Inserting elements: 5, 3, 7, 2, 6, 8, 4, 10, 1
root = insert(root, 5);
root = insert(root, 3);
root = insert(root, 7);
root = insert(root, 2);
root = insert(root, 6);
root = insert(root, 8);
root = insert(root, 4);
root = insert(root, 10);
root = insert(root, 1);

Now, let's visualize the resulting BST for better understanding.

          5
       /     \
      3       7
     / \     / \
    2   6   8   10
   /     / \
  1    4   10

Quiz 📝

Let's test your understanding!

That's it for today! We've learned how to insert elements into a Binary Search Tree (BST). In our next lesson, we'll explore more BST operations like searching, deleting, and more! 🚀

Stay patient, keep practicing, and happy coding! 🎉