The Diameter of a Binary Tree

Problem: Given a binary tree, there is a path connecting any two nodes u,v in the tree. Among all the possible paths, the longest path is considered as the diameter of the binary tree. Find out this path.

Solution: We can use recursion to solve this problem. We need to be careful than this longest path can just reside in one of the sub-tree of the root. The code for this algorithm is as follow:

int height(TreeNode * root)
{
   if(!root) return 0;
   
   return 1+max(height(root->left), height(root->right));


int Diameter(TreeNode *root)
{
   if(!root) return 0;

   int h_left = height(root->left);
   int h_right = height(root->right);
   
   return max(1+h_left+h_right, max(Diameter(root->left), Diameter(root->right)));

}

Memorization might be used to avoid repeated calculation.

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; 
        }
 
      }     
   }
}

Serialize a Binary Tree

We know with pre-order and mid-order we can decide a binary tree. Besides, tree have array representation. However, to have better space efficiency, we can just store a binary tree according to its pre-order, but with null node also stored!

Find the Least Common Ancestor of Two Tree Nodes

Problem: Given two nodes in a tree, find the least common ancestor of them.

Solution: This is not a difficult problem. If there is parent pointer, things will be easier. However, simple solution still exist for tree nodes without parent pointer. See the code below:

node * common_ancestor(node *root, node *n1, node *n2)
{
   if(root==null || n1 == null || n2 == null)
     return null;

    if(n1 == root || n2 == root) return root;
   
   node * left = common_ancestor(root->left, n1, n2);
   node * right = common_ancestor(root->right, n1, n2);
   
   if(left && right) return root;
   
   return left ? left : right; 

}

More: if we need to do many common_ancestor() operations, there is a more efficient off-line algorithm called "Tarjan's off-line least common ancestors algorithm". It can get the least common ancestors for m pairs of nodes in just one tree traversal. The main idea is to leverage disjointed forest  with path compression and union by rank.

Segment Tree and Interval Tree

To build a Segment Tree, first sort all the end points of the segments, than adding -infinity and +infinity. For n segments, we then partition (-infinity, +infinity) into 2n+1 segments. These 2n+1 segments serve as elementary intervals. From them (considering them as leafs),  we can build a balanced binary tree. Then we add the n segments into the tree. Each node represents an interval. Non-leaf nodes represent the interval which is the union of their children. When adding a segment, we store the information of that segment in all nodes where the nodes' intervals are within the segment's interval. Besides, the nodes' parents' interval are not within the segment's interval.

• building cost is O(nlogn), space cost is O(nlogn), the cost to find all segments that contain a point (stabbing query) is O(k+logn)
• can also solve box overlap problem, Klee's measure problem.
• For multi-level segment tree, first build a base segment tree on one axis. Then build small segment tree on each node of the base tree, only for the segments stored on that node.
• For more details, please check http://www.cnblogs.com/TenosDoIt/p/3453089.html (in Chinese).

To build an Interval Tree, it is a little bit similar. First sort all the end points of the intervals and find the median points. Every node in the interval tree is associated with a point. And the node contains all the intervals that cover the point. The left child (sub-tree) of the node contains all the intervals whose upper bounds are smaller than the node's point. Similarly, we can define the right child.

• building cost is O(nlogn), space cost is O(n), the cost to find all intervals that overlap with an interval   (range query) is O(k+logn). 
• The result is a ternary tree with each node storing:
  • A center point
  • A pointer to another node containing all intervals completely to the left of the center point
  • A pointer to another node containing all intervals completely to the right of the center point
  • All intervals overlapping the center point sorted by their beginning point
  • All intervals overlapping the center point sorted by their ending point
• If we need to do a range query with interval tree, see we want to find the set of r that overlap with interval q. We first to sort all the start/end points of intervals, then find those have either start/end inside q. Second, we need select one point in q, do the query on the interval tree to find all the intervals that have the point. At the end, we need to merge results and do the dedup.

See Also: Klee's measure problem

Link all the nodes at the same level for a binary tree

Problem: Given a binary tree, assume you have one extra pointer (TreeNode *next), link all the nodes at the same level by using this next pointer. No other extra space is allowed (e.g., queue)


Solution:  if the tree is a full binary tree, where all non-leaf nodes have two children, the solution will be easier. You can find it at ihas1337code. If the tree is not necessarily a full binary tree, the solution is more difficult. But here we can still give an iterative solution. The key here is to leverage the established "next" pointer. When we are visiting the ith level (assume all the "next" pointers at ith level have been established), we construct the the "next" pointers at i+1th level. The details of the algorithm are as follow:

• if a node has both left child and right child, then left child's next should link to right child. This is the most straightforward case.
• if a node only have one child, to assign the child's next, we need to look at the node's siblings. basically, we need to find the first non-leaf sibling of the node, then find its left-most child as the target of the current node's child's next pointer. 
• We construct the next pointer level by level. When we are visiting the ith level (assume all the "next" pointers at ith level have been established), we construct the the "next" pointers at i+1th level. During this process, we also record the first non-leaf node at i+1th level. Since when we proceed to visit i+1th level, we need to start from that node. If such node can't be found, it means we finish linking the tree by level.

 The code is as follow (may not be the optimal):

typedef struct TreeNode{
        struct TreeNode *left;
        struct TreeNode *right;
        struct TreeNode *next;
        int value;     
}TreeNode;


bool isLeaf(TreeNode *root)
{
    return root->left==NULL && root->right==NULL;
}

TNode * leftmostChild(TreeNode *root)
{
  return root->left? root->left:root->right;
}


TreeNode * real_next_non_leaf(TreeNode *root)
{
    while(root->next && isLeaf(root->next)) root = root->next;
    
    return root->next;

}

void link_tree_level(TreeNode *root)
{
     if(!root || !isLeaf(root)) return;
     
     TreeNode *firstp = leftmostChild(root);
     
     while(true)
     {
         TreeNode *nnext;
         while(root)
         {
             if(root->left && !root->left->next) 
             {
               if(root->right)  
               {
                  root->left->next = root->right;
                  nnext = real_next_non_leaf(root);
                  root->right->next = nnext ? leftmostChild(nnext) : nnext;
                  root = nnext;              
               }
               else
               {
                  nnext = real_next_non_leaf(root);
                  root->left->next = nnext ? leftmostChild(nnext) : nnext;
                  root = nnext;
               }
             }
             else if(root->right)  
             {
                  nnext = real_next_non_leaf(root);
                  root->right->next = nnext ? leftmostChild(nnext) : nnext;
                  root = nnext;              
            }
         }
                
       
        while(firstp && isLeaf(firstp))
                    firstp = firstp->next;
       
        if(!firstp) break;
        root = firstp;
        firstp = leftmostChild(root);
       
     }
 
}