Prep Flashcards
In-order traversal
Left -> Root -> Righ
Pre-order traversal
Root -> Left -> Righ
Post-order traversal
Left -> Right -> Root
Tree
A tree is a widely used abstract data type that represents a hierarchical structure with a set of connected nodes. Each node in the tree can be connected to many children, but must be connected to exactly one parent, except for the root node, which has no parent.
Complete binary tree
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.
Balanced binary tree
A binary tree structure in which the left and right subtrees of every node differ in height by no more than 1.
Graph
A graph is a structure containing a set of objects (nodes or vertices) where there can be edges between these nodes/vertices. Edges can be directed or undirected and can optionally have values (a weighted graph). Trees are undirected graphs in which any two vertices are connected by exactly one edge and there can be no cycles in the graph.
Depth-first search
Depth-first search is a graph traversal algorithm which explores as far as possible along each branch before backtracking. A stack is usually used to keep track of the nodes that are on the current search path. This can be done either by an implicit recursion stack, or an actual stack data structure.
Breadth-first search
Breadth-first search is a graph traversal algorithm which starts at a node and explores all nodes at the present depth, before moving on to the nodes at the next depth level. A queue is usually used to keep track of the nodes that were encountered but not yet explored.
A similar template for doing breadth-first searches on the matrix goes like this. It is important to use double-ended queues and not arrays/Python lists as enqueuing for double-ended queues is O(1) but it’s O(n) for arrays.
Heap
A heap is a specialized tree-based data structure which is a complete tree that satisfies the heap property.
Max heap - In a max heap the value of a node must be greatest among the node values in its entire subtree. The same property must be recursively true for all nodes in the tree.
Min heap - In a min heap the value of a node must be smallest among the node values in its entire subtree. The same property must be recursively true for all nodes in the tree.
Hash table
A hash table (commonly referred to as hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function on an element to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored.
Separate chaining
A linked list is used for each value, so that it stores all the collided items.
Open addressing
All entry records are stored in the bucket array itself. When a new entry has to be inserted, the buckets are examined, starting with the hashed-to slot and proceeding in some probe sequence, until an unoccupied slot is found.
Linked list
Like arrays, a linked list is used to represent sequential data. It is a linear collection of data elements whose order is not given by their physical placement in memory, as opposed to arrays, where data is stored in sequential blocks of memory. Instead, each element contains an address of the next element. It is a data structure consisting of a collection of nodes which together represent a sequence.
Doubly linked list
A linked list where each node has two pointers, next which points to the next node and prev which points to the previous node. The prev pointer of the first node and the next pointer of the last node point to null.
