Binary Search Trees: Foundations
and Applications
Submitted to: Arvind Kumar Maurya
Submitted by: Vandini Gupta
Ashoka Institute of Technology and Management
by Vandini Gupta
Understanding Binary Search Trees (BST)
A Binary Search Tree (BST) is a hierarchical data structure that organizes data in a specific way, enabling efficient searching, insertion, and deletion operations. It
is a variant of a binary tree, adhering to strict rules that maintain its ordered nature. Each node in a BST holds a single value.
Left Subtree Rule Right Subtree Rule Unique Values
For any given node N, all values in its left For any given node N, all values in its right In a basic BST implementation, all nodes are
subtree must be strictly less than the value of subtree must be strictly greater than the value typically required to have distinct, unique
N. of N. values. This simplifies operations and ensures
predictable behavior.
Searching for Elements in a BST
Searching in a BST leverages its ordered structure to efficiently locate a specific item. The process involves comparing the target item with node values and
traversing either left or right until the item is found or a null child is encountered.
Algorithm Steps Search Example: Davis
1. Start from the root node of the tree. Search for "Davis" in a tree where "Harris" is the root.
2. Compare the ITEM to be searched with the value of the current node N. Compare "Davis" with "Harris" ³ "Davis" < "Harris", go left.
3. If ITEM is less than N, move to the left child. Current node is "Cohen". Compare "Davis" with "Cohen" ³ "Davis" >
4. If ITEM is greater than N, move to the right child. "Cohen", go right.
5. If ITEM is equal to N, the search is successful. Current node is "Green". Compare "Davis" with "Green" ³ "Davis" <
"Green", go left.
6. Repeat this process until the ITEM is found (success) or a NULL child is
reached (failure). Found "Davis" ' . Search successful.
Inserting New Nodes into a BST
Inserting a new node into a BST follows a similar logic to searching. The goal is to find the correct position where the new value can be added while maintaining
the BST properties. New nodes are always inserted as leaf nodes.
Identify Null Child
Locate Insertion Point
The search will eventually lead to a point where a NULL child is
Utilize the standard BST search procedure to traverse the tree. This helps encountered. This indicates the position where the new item should be
in finding the appropriate parent node for the new item. inserted.
Update Pointers
Insert Item
Ensure that all necessary pointers (from the parent node to the new child)
Insert the ITEM as either the left or right child of the last compared node, are correctly updated to reflect the new structure of the tree.
depending on its value relative to that node.
For example, to insert ITEM = 20: Compare with 38 (go left), then 14 (go right), then 23 (go left), then 18 (go right). Since 18 has no right child, 20 is inserted as the
right child of 18.
Deleting Nodes from a BST
Deleting a node from a BST is more complex than insertion or searching, as it involves handling three distinct cases to ensure the tree's structural integrity and
BST properties are maintained. The first step always involves finding the node to be deleted and its parent.
1 Case 1: Node has No Children 2 Case 2: Node has One Child 3 Case 3: Node has Two Children
(Leaf Node)
If the node has only one child, replace the This is the most complex case. Find the
If the node to be deleted is a leaf, simply set node with its sole child. The parent's inorder successor of the node to be deleted
the corresponding pointer from its parent pointer should then bypass the deleted (the smallest value in its right subtree).
to NULL, effectively removing it from the node and point directly to its grandchild. Replace the deleted node's value with the
tree. inorder successor's value, then delete the
inorder successor from its original position
(which will be a Case 1 or Case 2 deletion).
BST Modifications: Handling Duplicates and Violations
While basic BSTs typically enforce unique values, modifications can be made to accommodate duplicates. However, any modification must carefully consider its
impact on the BST properties, as a single improper replacement can invalidate the entire tree's structure.
BST with Duplicates Maintaining BST Property
One common modification allows for duplicate values. A widely accepted When replacing a node, especially during deletion, it's crucial that the
approach is to permit values equal to the parent node's value to be placed in replacement node does not violate the BST's fundamental rules.
the right subtree. This alternative definition maintains search efficiency.
Replacing 23 with 35 (where 35 is less than the root's value of 38): ' Still
Example: If a node has value N, and you insert another N, it would go into the a valid BST.
right subtree. Replacing 23 with 40 (where 40 is greater than the root's value of 38, but
it's in the left subtree): o Not a valid BST. This would violate the left
subtree property for the root.
Traversals in Binary Search Trees
Tree traversals are methods for visiting each node in a tree exactly once. For BSTs, specific traversal orders yield unique and useful outputs, especially the inorder
traversal which always produces sorted data.
Inorder Traversal (Left, Root, Right) Preorder Traversal (Root, Left, Right) Postorder Traversal (Left, Right, Root)
Visits the left subtree, then the current node, then Visits the current node first, then recursively Recursively traverses the left subtree, then the
the right subtree. This traversal method always traverses the left subtree, and finally the right right subtree, and finally visits the current node.
yields the elements of the BST in sorted subtree. This is useful for creating a copy of the This is often used for deleting nodes in a tree or
(ascending) order. tree or for prefix expressions. for postfix expressions.
Traversal Example: A Visual Walkthrough
Consider the following set of numbers inserted into a BST: 40, 25, 70, 22, 85, 60, 80, 90, 10, 30. Let's visualize the structure and the output of each traversal type.
40
/ \
25 70
/ \ \
22 30 85
/ / \
10 80 90
Preorder Traversal: 40, 25, 22, 10, 30, 70, 85, 80, 90 (Root, Left, Right)
Inorder Traversal: 10, 22, 25, 30, 40, 60, 70, 80, 85, 90 (Left, Root, Right - Sorted!)
Postorder Traversal: 10, 22, 30, 25, 60, 80, 90, 85, 70, 40 (Left, Right, Root)
