Medium Level Tree Problems

1.  Up side down a tree

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

Given a binary tree {1,2,3,4,5},

    1
   / \
  2   3
 / \
4   5

return the root of the binary tree [4,5,2,#,#,3,1].

   4
  / \
 5   2
    / \
   3   1  

The problem is not really hard, but it is confusing enough.
This can be achieved by recursion.  Note:
1)For the left , let it be new root;
2) for the right, let it be the new left.
3) Do not forget to reset root and right's children to NULL. Otherwise, it is infinity loop.


TreeNode* upDown(TreeNode*root){    
    if (!root) return nullptr;
    if (!root->left) return root;

    assert(root->left);
    TreeNode* l= root->left;
    TreeNode* r= root->right;
    TreeNode* newH= upDown(root->left);
    l->right= root;
    l->left= upDown(r);
    root->left=0;
    root->right=0;
    if (r) { r->left=0; r->right=0;}
    return newH;
}

2.Convert Sorted Array to Binary Search Tree   and vise

The problem can be easy if one knows to use the middle element as root. Assign left part to left children and right part to right children.  Then recursion is very easy.

If the initial thought is going to place tree node in order of the array, you will have a painful day.

    TreeNode* sortedArrayToBST(vector<int>& nums, int l, int r){
        if (l>r) return nullptr;
        if (l<=r){
            TreeNode* root= new TreeNode(0);
            int m=(l+r)/2;
            if (l==r) {
                root->val= nums[l];
                return root;
            }
            if (m==l){//two elements
                root->val= nums[l];
                TreeNode* right= new TreeNode(nums[r]);
                root->right=right;
                return root;
            }
            //more than 3 elements
            root->val= nums[m];
            root->left= sortedArrayToBST(nums, l, m-1);
            root->right= sortedArrayToBST(nums, m+1,r);
        }
    } 

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.empty()) return nullptr;
        return sortedArrayToBST(nums, 0,nums.size()-1);
    }

To convert BST to Array is straight forward an In Order traversal.

3. Find the Kth Smallest nodes in BST

Solution: Think: the 1st smallest is at the left bottom most; 2nd is first parent, 3rd is the sibling of the first.  So it is actually In order traversal.  During traversal, counting down K. When K becomes 0, you get the kth.

void countSmall(TreeNode* root, int& k, int& target){

        if (!root) return;

        countSmall(root->left, k, target);

        if (--k==0){target=root->val; return ;}

        countSmall(root->right,k, target);

    }

    int kthSmallest(TreeNode* root, int k) {

        int target;

        countSmall(root, k, target);

        return target;

    }

4. Maximum path sum in Binary Tree

Given a binary tree, find the maximum path sum.  For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.

Solution: 
1) The first main problem is to divide the problem to Local and Global:
     The path sum uses the local root has ability to grow, so it is global. We have to propagate it not matter how big it is right now. (variable ext in the code)
      The local branch 's current maximum is decided and will not change any more. It will be checked right now to get the combination biggest using both local root, left and right. (variable local in the code)

2) One point needs to be careful. 
    local is obtained by  the biggest among local_left, local_right, ext.  Do not try to connect local_left or _right to root because you never know  how faraway they are.  Since ext is for sure to use root, we compare with ext to determine new local.

    void maxPathSum(TreeNode* root, int& local, int&ext) {

        int localL, localR, extL, extR;
        //leaf
        if (!root->left &&!root->right){
            local= root->val;
            ext= root->val;
            return;
        }
        //both children
        if (root->left &&root->right){
            maxPathSum(root->right,localR, extR);
            maxPathSum(root->left, localL, extL);
            int cross= max(extL+extR+root->val, root->val);
            ext= max(max(extL,extR)+root->val, root->val);
            local= max(cross, max(localL, localR));
            local= max(local, ext);
            return;
        }
        //only left
        if (root->left){
            maxPathSum(root->left, localL, extL);
            ext=max(extL+root->val, root->val); 
            local=max(ext, localL); 
            return;
        }
        //only right
        if (root->right){
            maxPathSum(root->right, localR, extR);
            ext=max(extR+root->val, root->val); 
            local=max(ext, localR); 
            return;
        }        
    }    

    int maxPathSum(TreeNode* root) {
        if (!root) return -INT_MIN;
        int local, ext;
        maxPathSum(root, local, ext);
        return max(local, ext);
    }

I shortened the code by processing the nullptr root. 

The problem is there is no good indicator  for integer value. I used INT_MIN. It has integer overflow problem. So I have to cast to double to make sure when INT_MIN come into calculation. But the code is shorter.

    void maxPathSum(TreeNode* root, int& local, int&ext) {
        if (!root) {local= INT_MIN;  ext=INT_MIN; return; }
        int localL, localR, extL, extR;
        maxPathSum(root->right,localR, extR);
        maxPathSum(root->left, localL, extL);
        int cross= max(double(extL)+extR+root->val, double(root->val));
        ext= max(max(double(extL),double(extR))+root->val, double(root->val));
        local= max(double(cross), max(double(localL), double(localR)));
        local= max(local, ext);
        return;
    }
    
    int maxPathSum(TreeNode* root) {
        int local, ext;
        maxPathSum(root, local, ext);
        return max(local, ext);
    }