BST Introduction šŸŽÆ

beginner
15 min

BST Introduction šŸŽÆ

Welcome to the world of Data Structures and Algorithms! Today, let's dive into one of the most fundamental data structures ā€“ the Binary Search Tree (BST).

A Binary Search Tree (BST) is a type of tree data structure in computer science. It helps us efficiently store and retrieve data, especially large sets of data. Let's explore this fascinating structure together! šŸ’”

Table of Contents

  1. Why Binary Search Trees?
  2. Binary Tree vs Binary Search Tree
  3. BST Node and Properties
  4. Binary Search Tree Insertion
  5. Binary Search Tree Traversals
  6. Binary Search Tree Deletion
  7. Quiz

Why Binary Search Trees? šŸ“

Binary Search Trees (BSTs) are used to efficiently store and retrieve data, making them ideal for handling large data sets. BSTs provide O(log n) time complexity for searching, inserting, and deleting elements, which is much faster than arrays or linked lists when dealing with large data sets.

Binary Tree vs Binary Search Tree šŸ“

A Binary Tree is a tree data structure in which each node has at most two children ā€“ a left child and a right child. On the other hand, a Binary Search Tree (BST) is a specialized binary tree that maintains a specific property:

  • The key (or value) of the left child is always less than the parent node.
  • The key (or value) of the right child is always greater than the parent node.

BST Node and Properties šŸ“

A BST node consists of three parts:

  1. Data (or key): The value stored in the node.
  2. Left: A pointer to the left child node.
  3. Right: A pointer to the right child node.

A BST follows certain properties:

  1. The left subtree is less than the root node.
  2. The right subtree is greater than the root node.
  3. Both the left and right subtrees are also BSTs.

Binary Search Tree Insertion šŸ“

Inserting a new node into a BST involves finding the appropriate location for the new node based on its key value. The algorithm follows these steps:

  1. If the tree is empty, create a new node and make it the root node.
  2. Traverse the tree to find the appropriate location for the new node (left subtree for smaller values, right subtree for larger values).
  3. Insert the new node at the found location.

Here's an example:

python
class Node: def __init__(self, key): self.key = key self.left = None self.right = None def insert(root, key): if root is None: return Node(key) else: if root.key < key: root.right = insert(root.right, key) else: root.left = insert(root.left, key) return root

šŸ’” Pro Tip: This insertion algorithm ensures that the BST remains balanced and maintains the O(log n) time complexity for searching, inserting, and deleting elements.

Binary Search Tree Traversals šŸ“

There are three main traversal methods for BSTs: In-order, Pre-order, and Post-order. These methods allow us to visit all the nodes in the tree in a specific order, making it easy to perform operations like finding the minimum, maximum, and range values.

  1. In-order traversal: Left subtree, root node, right subtree. This order ensures that the nodes are visited in ascending order of their keys.
  2. Pre-order traversal: Root node, left subtree, right subtree. This order provides a depth-first search of the tree, visiting the root node first.
  3. Post-order traversal: Left subtree, right subtree, root node. This order provides a depth-first search of the tree, visiting the root node last.

Here's an example of in-order traversal using recursion:

python
def inorder(root): if root: inorder(root.left) print(root.key) inorder(root.right)

Binary Search Tree Deletion šŸ“

Deleting a node from a BST involves finding the node to be deleted and replacing it with an appropriate successor or predecessor. The algorithm follows these steps:

  1. Find the node to be deleted.
  2. If the node is a leaf node (no children), simply remove it.
  3. If the node has only one child, replace it with the child node.
  4. If the node has two children, find the minimum value in the right subtree (the successor) and replace it with the value of the node to be deleted.

Here's an example of deleting a node with the key 10:

python
def delete(root, key): if root is None: return root if key < root.key: root.left = delete(root.left, key) elif key > root.key: root.right = delete(root.right, key) else: if root.left is None: return root.right elif root.right is None: return root.left else: temp = find_min(root.right) root.key = temp.key root.right = delete(root.right, temp.key) return root

Quiz šŸ“

Quick Quiz
Question 1 of 1

What is the time complexity of searching, inserting, and deleting elements in a BST?

That's it for today! I hope you enjoyed learning about BSTs. In the next lesson, we'll dive deeper into BST operations and explore advanced concepts like balanced BSTs and AVL trees. Happy coding! šŸ’”