[Verse 1]
Navigate the nodes with precision in mind
Left child smaller, right child you'll find
Greater values climbing up the tree
Ordered structure sets our data free
Root to leaf, the path reveals its face
Binary choices guide us to the place
Each comparison cuts the search in half
Logarithmic time, that's the math
[Chorus]
Left less, right more, that's the BST core
Insert, delete, search and explore
Balance the height, keep the tree tight
O log n operations burning bright
Left less, right more, never ignore
The fundamental law of the BST shore
[Verse 2]
Insertion starts from the root node base
Compare the value, choose the chase
Smaller goes left, larger goes right
Repeat until you find the site
Empty spot means place it there
New leaf node without a care
But watch the depth, it might grow tall
Unbalanced trees will make you crawl
[Chorus]
Left less, right more, that's the BST core
Insert, delete, search and explore
Balance the height, keep the tree tight
O log n operations burning bright
Left less, right more, never ignore
The fundamental law of the BST shore
[Verse 3]
Deletion brings three cases to the scene
Leaf node simple, just remove clean
One child present, lift it up high
Replace the parent, watch it fly
Two children tricky, here's the trick
Find successor, make the switch
Rightmost left or leftmost right
Maintains the order, keeps it tight
[Bridge]
In-order traversal reveals the sort
Left root right, the perfect report
Pre-order copies, post-order frees
Recursive patterns flow with ease
Self-balancing keeps the speed
AVL and Red-Black indeed
Rotations spinning left and right
Maintaining that logarithmic height
[Chorus]
Left less, right more, that's the BST core
Insert, delete, search and explore
Balance the height, keep the tree tight
O log n operations burning bright
Left less, right more, never ignore
The fundamental law of the BST shore
[Outro]
Binary search tree, elegant and clean
Most efficient structure ever seen
When balanced right, performance soars
Left less, right more, open those doors