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

# Category: Tree

## Heap – Theory

Heap is the underlying implementation of Priority Queue. A heap is implemented using a binary tree. A heap can be visualized to have a tree structure logically but internally it's implemented an array. 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… Continue reading Heap – Theory

## 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… Continue reading BST – Set 1

## 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… Continue reading Binary Tree – Set 3

## Binary Tree – Set 2

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 inorder traversal and keep track of previously visited node. When a node is being visited, assign previously visited node as next. Time Complexity: O(n) 2. This is… Continue reading Binary Tree – Set 2

## 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… Continue reading Self Balancing Binary Tree

## 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… Continue reading Binary Tree – Set 1

## Priority Queue – Theory

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

## Heap

Min Heap Visualizer Max Heap Visualizer Heap Basics Question List Heap is an almost complete binary tree. Time complexity of building a heap = O(n) (and not O(n(logn))) - SO N – 1 internal nodes in a binary tree with N leaf (external) nodes GFG It would be O(n log n) if you built the heap by repeatedly… Continue reading Heap

## Trie – Prefix Tree

Trie Youtube Video and Java Code(add, search, delete) Gist(add, search, frequency). I'm making a search engine called MillionGazillion from Interview Cake. Algo: 1. We can store the data using a hash table mapping. This though takes a lot of space. To prevent that we use a Trie(though it has it's own memory issues but hey… Continue reading Trie – Prefix Tree