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 keys stored in the left sub-tree, and smaller than all keys in right sub-tree.[1] (The leaves (final nodes) of the tree contain no key and have no structure to distinguish them from one another. Leaves are commonly represented by a special leaf or nil symbol, a NULL pointer, etc.)
Tag Archives: rank
Kth smallest/minimum element in a BST – Rank of a BST node
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 node in the call stack is the desired kth smallest node. This is O(n) time algorithm.
Permutation Rank
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 permutation.