Implementation of algorithms and data structures from various programming portals are given in respective directories:
- It is an information retrieval data structure.
- It is also called radix/prefix tree.
- It is used for efficient searching of keys in a container. If the keys are strings, the particular string can be searched in O(n), where n denotes the length of the string to be searched.
- Each node of the trie has multiple branches, a node where a word ends is marked with terminal = true.
Implementation : trie
- Number of possible binary search trees with n keys.
- Number of expressions containing n pairs of parantheses which are correctly matched. For n = 3, possible expressions are ((())), ()()(), (())(), ()(()), (()())
- Number of ways n + 1 factors can be completely paranthesized, for eg. N = 3 and 3 + 1 factors: (a, b, c, d), we have: (ab)(cd), a(b(cd)), ((ab)c)d, (a(bc))d, a((bc)d).
- Number of ways a convex polygon of n + 2 sides can split into triangles by connecting vertices.
- Number of different unlabelled binary trees can be there with n nodes.
- The number of paths with 2n steps on a rectangular grid from botton left, i.e., (n-1, 0) to top right (0, n-1) that do not cross above the main diagonal.
- Number of ways to form a "mountain range" with n upstrokes and n downstrokes.