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… Continue reading B – Tree – Theory
Binary Heap is the underlying implementation of Priority Queue. A heap can be visualized to have a tree structure logically. This tree satisfies the two heap properties - value property and the shape property. Although the heap is a tree, because of the heap property it's easy to implement it as an array. Binary Heap is… Continue reading Heap – Theory
BST Visualizer BST Complexity 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. Conversely if we have n nodes in a complete(almost) BT then height of the tree will be floor(log(n)), (base 2) this… Continue reading BST – Set 1
BT Set – 2, BT Set – 1, Question Set (101- ..) Binary Tree Visualizer ** Remove nodes on root to leaf paths of length < K. GFG Algo: We do a postorder traversal and in each iteration we also path the length till node. When we reach a leaf node, we check if the length till… Continue reading Binary Tree – Set 3
1, 4-6, 8, 10, *11, 14, 15, 18, 21, 22, **23, 24, 29, 34, 35, 36, BT Set - 1, BT Set - 3 , Question Set(41-101) Binary Tree Visualizer *** Populate Inorder Successor for all nodes GFG Code Algo: 1. Traverse the given tree in reverse in-order traversal(this is visiting the right most node -> root… Continue reading Binary Tree – Set 2
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… Continue reading Self Balancing Binary Tree
InterviewBit 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… Continue reading Binary Tree – Set 1
Java Docs In computer science, a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their… Continue reading Priority Queue – Theory
1,2,3,5,7,12,14, 19/20, 21, 22, **23, **25 Heap is the underlying implementation of Priority Queue. We use Priority Queue classes to implement min and max heaps in Java. SO 1 Index array for heap - Parent = i/2 Child = 2*i , 2*i + 1 Last Non-Leaf Node = floor(n/2) Leaf Node Starts from = floor(n/2… Continue reading Heap Problem Set
1 (Basic), 2 (autocomplete), 9, 11, 12 Trie Youtube Video and Java Code(add, search, delete) Gist(add, search, frequency). ***** Implement a phone directory using Trie / Autocomplete Algo: Save all the words in Trie. Now while searching we check for the first entered character in the prefix. If found, then we start suggesting all the words… Continue reading Trie – Prefix Tree
