“ As it is little bit tricky to understand binary search tree.. we will see one by one.. further moving. The insertion is little bit simple, since we need to just find the sub tree where the new number will fit in on a already existing BST”
Binary search tree matches the insertion philosophy of the heap. Heapify function for a max heap basically adds a data item and makes the heap to follow the max heap property by up bubbling. It always assumes the given heap is already a max heap.
The same assumption we make in a binary search tree as well. We assume the already given tree is a BST and traverse it to find the correct spot
Insertion is simple. Just insert the data at the right or left of a sub tree based on the parent node. Even if the parent has no child, the comparison is made to put the element at right spot. Unlike heap, where we compare left and root to insert the right node, here we can directly insert without much confusion.
Heap: both left and right much be less than the root node
BST: left < root < right
This is the important difference to be understood.
- I simply didn’t understand the need for prev. :) Dummies brain.. prev is important to track the previous node while you are iterating.
- If its a binary tree, we only think about left & right nodes. But in a BST, we have a parent node for easy traversal.
- The input array gets sorted automatically when inserted into BST