Find the rank of a number in the lexicographic order of its permutations For example: 312 has rank 5 in the sorted permutation list {123, 132, 213, 231, 312, 321}. A brute force method would be to generate all the permutation and sort them. This will be in exponential order as to generate all the […]
Tag Archives: rank
Given a binary search tree. Find the kth smallest element in the BST. A quick solution would be to perform a modified inorder traversal with an extra parameter k. Each time inorder traversal is popping a node out of recursion/call stack (i.e. unwinding a recursion)then we keep decreasing the k. When k=0 then the current […]
From wiki, A binary search tree is a rooted binary tree, whose internal nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right. The tree additionally satisfies the binary search tree property, which states that the key in each node must be greater than all […]