Let’s Build a Binary Search Tree in Java!

I know you know that a BST (Binary Search Tree) uses dynamic memory, meaning it employs discontinuous memory allocation similar to a linked list, unlike an array which uses continuous memory allocation.

Before getting your hands dirty, I will shed some light on some rapid fire facts. 🔥🔥🔥
Fact 1: BSTs use dynamic memory allocation for their nodes. Each node in the tree is dynamically allocated in memory and contains data and pointers to its left and right child nodes (subtrees). This dynamic allocation allows the BST to grow and shrink as elements are inserted or removed.

Fact2: BST offer efficient search, insert, and delete operations when the tree is balanced. The time complexity for these operations in a balanced BST is O(log n), where “n” is the number of nodes in the tree.

Fact3: (Only for people who read yesterday’s blog about BST) 🤩
it’s essential to note that the efficiency of BST operations depends on the balance of the tree. In the worst-case scenario, when the tree is heavily unbalanced (resembling a linked list), the time complexity for these operations can degrade to O(n), where “n” is the number of nodes in the tree. This can happen, for example, if elements are inserted in a sorted order into the BST. Don’t worry we have techniques such as AVL trees and Red-Black trees to keep the tree balanced automatically. I will explore those techniques in the coming blogs.👍

NO MORE TALKING, lets dive into…