B – Tree

B-Tree is a self-balancing search tree. In most of the other self-balancing search trees (like AVL and Red Black Trees), it is assumed that everything is in main memory. To understand use of B-Trees, we must think of huge amount of data that cannot fit in main memory. When the number of keys is high, the data is…

Heap – Theory

For a binary heap we have O(log(n)) for insert, O(log(n)) for delete min and heap construction can be done in O(n). SO Searching in a heap -  You need to search through every element in the heap in order to determine if an element is inside. One optimization is possible, though (we assume a max…

BST – Set 1

BST Visualizer In a complete(almost)  binary tree number of nodes (n) and height of tree (h) have a relationship like => n = 2^(h+1) -1,   this is the all the nodes of the tree. If we have n nodes in a complete(almost) BT then height of the tree will be floor(log(n)), (base 2) this is…

Binary Tree – Set 3

BT Set – 2, BT Set – 1, Question Set (101- ..) Binary Tree Visualizer Remove nodes on root to leaf paths of length < K. GFG Algo: The idea here is to use post order traversal of the tree. Before removing a node we need to check that all the children of that node in the shorter…

Binary Tree – Set 2

BT Set - 1, BT Set - 3 , Question Set(41-101) Binary Tree Visualizer *** Populate Inorder Successor for all nodes Code This is also referred to as Threaded Binary Tree. GFG Algo: 1. We need to do a reverse inorder traverse. 2. The same can be easily implemented using queue.We first do an inorder…

Self Balancing Binary Tree

AVL Tree Implementation. Code. GFG - Insert, Delete  Youtube Time Complexity: The rotation operations (left and right rotate) take constant time as only few pointers are being changed there. Updating the height and getting the balance factor also take constant time. So the time complexity of AVL insert remains same as BST insert which is O(h) where…

Binary Tree – Set 1

BT Set - 2, BT Set - 3 , Question Set (1- 40) Binary Tree Visualizer *** Binary Tree Traversal. Depth First Traversals:  Code  GFG Time Complexity: O(n) where n is number of nodes in the binary tree Inorder: Left, Root, Right -  [Pending] Morris Traversal for Inorder ( No stack, No Recursion) (Code, GFG) -  Iterative using…

Trie – Prefix Tree

Youtube Video and Java Code(add, search, delete) Gist(add, search, frequency). I'm making a search engine called MillionGazillion from Interview Cake.  First we can use a hash table. This though takes a lot of space.  To prevent that we use a Trie(though it has it's own memory issues but hey it's better here). One way would be…