An O(N^2) Algorithm for Optimal BST

Problem: Given a set of ordered keys and their corresponding probabilities to be visited, construct an optimal BST tree with minimum search cost.

Solution: This is the classical optimal BST problem. The well-known solution has an O(N^3) complexity. However, Knuth found a better way that can achieve O(N^2). Basically, when we try to find the root of an optimal BST, previously we need to iterate from i to j. But there is an observation: root[i, j-1] <= root[i,j] <= root[i+1, j]. Given this inequality, we can reduce the range which we look for the root. This new range (root[i, j-1]], root[i+1, j]) is smaller than (i, j). The detail solution and proof can be found here.

Construct All Possible Binary Trees with N Nodes

Problem: Enumerate all possible binary trees with n nodes. For example, if n=1, there just one tree; if n=2, there are two trees:

         *             or            *
           \                          /
            *                      *

Solution: The key is to understand what can uniquely denote a tree (or serialize a tree). A good way to serialize a tree is to record the pre-order traversal of a binary tree plus the nil virtual leaf information. If we denote an actual node as "1", the nil virtual leaf as "0". The sequence "10100" will stand for the following tree:


                  *          
               /      \                    
             nil       *
                      /    \
                   nil    nil

The way to decide the nil leaf is to check the children of a node. If a node is a leaf in the tree, it will have two nil virtual leaves, since a leaf won't have any children.  Similarly, we can know the sequence "11000" will stand for the following tree:


                  *          
                 /  \                
               *    nil
              /  \
           nil  nil

Therefore,  our target is to enumerate all possible sequences. There are several constraints on the sequences:

• For a n node tree, the length of the sequence will be 2n+1 with n "1" and n+1 "0".
• For any position i in the sequence s and i != 2n,  the number of "1" should always be no smaller than the number of "0" in the sub-sequence s[0, i].

The related code is as follow:

// rebuild the tree from a sequence such as "11000"
TreeNode * rebuild_tree(int s[], int n)
{

    TreeNode *root = create_node();
    stack<TreeNode *> stk;
    stk.push(root);
    
    for(int i=1; i<s.size(); i++)
    {
       if(s[i])
       {
         
         TreeNode *node = create_node();
         if(s[i-1]) 
         {
           stk.top()->left = node;           
         }
         else
         {
           stk.top()->right = node;
           stk.pop();          
         }
         stk.push(node);
       }
       else 
       {
         if(!s[i-1]) stk.pop();
       }
    
    }
    
    return root;

}

//print all possible trees
void output_all_possible_trees(int *seq, int n, int num1, int num0)
{
     
     if((num1 + num0) == 2*n)
     {
        seq[2*n] = 0;
        TreeNode *root = rebuild_tree(seq, 2*n+1);
        print_tree(root);
        return;
     }
        
    if(num1 >= num0 && num1 < n)
    {
        seq[num1+num0] = 1;
        output_all_possible_trees(seq, n, num1+1, num0); 
    }       
    
    if(num0 < num1 && num1 <=n)
    {
        seq[num1+num0] = 0;
        output_all_possible_trees(seq, n, num1, num0+1);  
    
    }
   
}

Iterative Binary Tree Traversal with Constant Space Overhead

Problem: Given a binary tree, try to traverse the tree in an iterative way. The space overhead is expected to be constant.

Solution: With stack, we can iteratively traverse the tree. Here explain a way to traverse the tree without stack. The main idea is to use threaded tree. The key is to leverage the right child pointer of a node that is null. Then set this null-valued right child pointer to the in-order successor of the node. The detail of the algorithm is as follow:

• Inspect a node n, if the node doesn't have a left child, visit this node, then proceed to its right child.
• If the node n has left child, there are two situations. The first is that the predecessor of n has not been processed. Then we need to find a right_most node that will be the predecessor of n set right_most's right child to be n. If n's left child has a right child, right_most is left child's right-most child; if n's left child doesn't have a right child, right_most is left child itself. Then we proceed to  n's left child.
• The second situation is that the predecessor of n has been processed. We can tell this by keep following n's left child's right child pointer until a right child pointer points to n or the pointer is null. If the pointer points to n, it means the predecessor of n has been processed, then we visit n, proceed to its right child. We can do one extra thing here, before moving forward, we can set the right child of n's predecessor to be null, since previously we modified its value to thread the tree. By doing this, we can keep the tree unmodified after traversal.
• The algorithm stops when we find the current node is null

The code is below:

void Non_recursive_tree_traversal(TreeNode *root)
{
   if(!root) return;
   
   TreeNode *cur = root;
     
   while(cur)
   {
      // if no left child, visit itself      
      if(!cur->left)
      {
        visit(cur);
        cur = cur->right;        
      }
      // left child is there
      else 
      {
        TreeNode *pp = cur->left;
        
        while(pp->right)
        {
           if(pp->right == cur) break;      
           pp = pp->right;     
        }
        
        // if cur's predecessor has been visited 
        if(pp->right == cur)
        {
           visit(cur);
           // revert the right pointer to null
           pp->right = NULL;
           cur = cur->right;
        }        
        else if(!pp->right)
        {
           // if the right child pointer is null
           // set its value to thread the tree
           pp->right = cur;
           cur = cur->left; 
        }
 
      }     
   }
}

Get the Max and Min Simultaneously

Problem: Given an array of integers, try to get the max and min in this array with the least number of comparisons.

Solutions:  if we have a current_max and current_min, for each element except the first one, we need to compare it against current_max and current_min. Thus in total, we need 2n-2 comparisons (or 2n-3 if you do it slightly different). However, a better approach exists by inspecting the integers in pair. We first compare the two adjacent integers, and use the bigger one from the two to compare against current_max and use the smaller one from the two to compare against current_min. For example, if A[i] = 4, A[i+1] = 10 and current_max = 11 and current_min = 2,  we just need to compare A[i] against current_min and A[i] against current_max. Therefore, for every two integers, we need 3 comparisons, which leads to a total comparisons around 3n/2.

Something about Heapsort

Heapsort has two pleasant properties

1. an average and worst-case O(N*LogN) complexity
2. in place algorithm, no extra space is needed.

Heapsort has two steps:

1. first make a max heap (or min heap), this operation takes O(N)
2. pop the root of the heap, swap it with the last element in the heap (the last leaf), do heapify on the elements rangeing from 1 to N-1. Basically, we build a new max (min) heap on the elements rangeing from 1 to N-1
3. repeat the step 2

Strassen’s Method

Strassen’s method is a good  algorithm used in matrix multiplication. Naive approach usually takes O(N^3) to do matrix multiplication, while Strassen’s method costs O(N^2.8). Basically its recursion formula is like T(N) = 7*T(N/2) + N^2.

Get the Maximum Profit from Stock -- Maximum Subarray Problem

Problem: Given an array price[], price[i] denotes the stock price at day i. Assume the array has a length of N (from day 1 to day N), try to get the maximum profit by selecting optimal timing to bug and sell stocks. For example, if price[] = {5, 2, 4, 3, 1},  the maximum profit per share we can get is $2. What we need to do is buy at day 2 and sell at day 3.

Solution: Naive approach takes O(N^2) by checking any two days. An improved approach costs O(NlogN) by first finding a descending sequence from the beginning. However, optimal approach should only cost O(N). The key is to do some transformation on the original problem.  Let us still reuse the previous example, given price[] = {5, 2, 4, 3, 1}, we can get another array diff[] = {-3, 2, -1, -2} such that diff[i] = price[i] - price[i-1] .  Then other goal is just to find the maximum subarray in diff[].  As known, there is a O(N) solution for the  maximum subarray problem.

More: An alternative that may be conceptually even simpler exist. Just do a linear scan, we keep a current_min， then for every day, we calculate the gain as the difference between the price at that day and current_min，if the gain is more than the maximum gain that we are tracking, update the maximum.
This algorithm also takes O(N).