The Binary Search Tree (BST)

A Binary Search Tree is a fundamental data structure organized in a hierarchical tree format. It's a specific type of binary tree where each node has at most two children, referred to as the left child and the right child. The key property of a BST is that for any given node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater than the node's value. This ordering allows for efficient search, insertion, and deletion operations, with an average time complexity of O(log n).

Binary Search Tree Operations

Insertion

New nodes are always inserted as leaf nodes. The insertion process starts at the root and traverses the tree by comparing the new value with the value of the current node. If the new value is smaller, it proceeds to the left child, and if it's larger, it proceeds to the right child. This continues until an empty spot is found where the new node can be added, maintaining the BST property.

Deletion

Deleting a node from a BST is more complex as the tree's structure must be maintained. There are three cases:

• Node is a leaf: The node can be directly removed.
• Node has one child: The node is replaced by its single child.
• Node has two children: The node is replaced by its inorder successor which is the smallest node in its right subtree or its inorder predecessor the largest node in its left subtree. The successor is then deleted from its original position.

Traversal

Traversal is the process of visiting all nodes in the tree in a specific order. There are three primary depth-first traversal methods visualized in this project:

• In-order Traversal (Left, Root, Right): Visits the left subtree, then the root node, then the right subtree. A key feature of a BST is that an inorder traversal will visit the nodes in ascending sorted order.
• Preorder Traversal (Root, Left, Right): Visits the root node first, then the left subtree, then the right subtree. This is useful for creating a copy of the tree.
• Postorder Traversal (Left, Right, Root): Visits the left subtree, then the right subtree, and finally the root node. This is often used to delete all nodes in a tree.