When autocomplete results are available use up and down arrows to review and enter to select. Touch device users, explore by touch or with swipe gestures.
Representing a Binary (Min) Heap in an array. Heaps are usually always populated in BFS order so the leaf nodes are always at the last or penultimate level (as shown in the figure).
Quick Sort works by partitioning the input around a randomly chosen element from the input, and recursively doing the same on the 2 partitions till we get sub-arrays of size '2', at which point, sorting them is as easy as swapping 2 elements that are relatively out of place (as per their expected sorted order).
Heaps are one of the more interesting and one of the relatively less emphasized data structures in undergraduate computer science. Using a min(or max)-heap, one can realize a sorting algorithm (heap-sort) that achieves the optimal sorting bound of O(n log n). In this visual, you can see how one can go about populating a min-heap (which we saw earlier). As you can see, each insertion costs O(log n) since you need to (in the worst case) move a newly inserted element up to the root of the...
Building a Cartesian Tree. A Cartesian Tree is a heap-like structure such that the root element of every sub-tree is not greater than any of the elements in the sub-tree below it. Like the heap, a Cartesian Tree is also a recursive structure. We show a linear time algorithm to build a cartesian tree from an input array. The difference between a cartesian tree and heap is that the former preserves the relative order of elements in the input array while the latter does not.
Binary search over a sorted array to find an element. We always check the center element of the remaining part of the array to discard either the right or the left half from further consideration. Runtime complexity: O(lg n).
Selection Sort: Always select the smallest remaining element in the input element and copy it to the end of the output array. In some sense, this is an inverse of Insertion Sort, where you insert the next element from the input array into it's correct sorted order in the output array.
The classical merge-sort algorithm works by successively merging contiguous arrays of size {1, 2, 4, 8, 16, 32, etc...} till the complete input has been merged. Merge Sort achieves the optimal running time of the sorting bound of O(n log n).
Blue arrows indicate edges, and red arrows indicate the order of traversal. The numbers indicate when the traversal happened. Given the definitions of each of the tree traversals, try to reason why in-order traversal doesn't exist for general (non-binary) trees.
General Technique: As soon as a node is visited, we check if both nodes in a query pair that involves the visited node have been visited. If so, we find the root node of the other node's subtree (not the most recently visited node in the pair) and set that as the LCA of the pair of nodes.
Blue arrows indicate edges, and red arrows indicate the order of traversal. The numbers indicate when the traversal happened. Binary Tree Traversal is a specialized form of General Tree traversal, where the notion of in-order tree traversal is well defined.
