Crack the Coding Interview

We know that a binary tree is a rooted tree in which each node has no more than two children. We can extend this definition to an n-ary tree. If a tree is rooted in which each node has no more than N children, it is called an n-ary tree. In other words, n-ary trees are tree data structures with up to n children nodes for each node.

Suffix trees are a compressed version of the trie that includes all of a string's suffixes. Suffix trees can be used to solve many string problems that occur in text-editing, free-text search, etc. The ability to search efficiently with mismatches might be considered their greatest strength.

AVL Trees named after its inventors Adelson-Velsky and Landis, is a unique variation of the Binary Search Tree, which is a self-balancing BST. The property of AVL Trees is that they automatically attain the tree's minimum possible height after executing any operation.

Dynamic Programming is a popular problem-solving approach in data structures and algorithms, where we solve problems by combining the solutions to subproblems like the divide-and-conquer method. But rather than computing the same sub-problem repeatedly, we solve the sub-problem once and store the calculated value in extra memory to avoid the recomputation.

Trie is a famous data structure used to store and process data, especially strings. It is a tree where each node represents a prefix or end of a word (the path traced from the root to that node). The word trie comes from retrieval as a trie can retrieve all the words with a given prefix.

There are two ways to solve and implement dynamic programming problems: 1) The top-down approach (Memoization) and 2) The bottom-up approach (Tabulation). Both approaches perform similarly in one way: They use extra memory to store the solution to sub-problems, avoid the recomputation and improve the performance by a huge margin. On another side, both of them are different in so many ways, and understanding this difference would help us to make critical decisions during problem-solving.