BST's In-order Traversal, No Recursion, No Stack

[Question]
Make BST in-order traversal without using recursive calls nor stack.

[Analysis]
Morris Traversal.

[Code]
/ *
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> v;
        if (root==NULL) return v;
     
        TreeNode* cur = root;
        TreeNode* pre = NULL;
        while (cur!=NULL) {
            if (!cur->left) {
                v.push_back(cur->val);
                cur = cur->right;
            }
            else {
                if (pre && pre->right==cur) {
                    pre->right = NULL;
                    v.push_back(cur->val);
                    cur = cur->right;
                } else {
                    pre = cur->left;
                    while (pre->right!=NULL && pre->right!=cur) {
                        pre = pre->right;
                    }
                    if (pre->right==NULL) {
                        pre->right = cur;
                        cur = cur->left;
                    }
                }
            }
        }
        return v;
     
    }
};

Find Ceiling of a Number in BST

[Question]
A binary search tree is given. Find the ceiling value present in the BST of 
a given key. eg-
                        8
               3              12
           2      6       10    15
                4
key - 13 => 15 
key - 4 =>6 
key - 8 =>10

[Analysis]
Using in-order traversal. The time complexity is O(lgN) on average, O(N) at the worst case.

[Code]

class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int v): val(v), left(NULL), right(NULL) {};
};

//
// return the pointer when a ceiling is found;
// otherwise, NULL;
//
TreeNode* find_ceiling(TreeNode* root, int target)
{
    if (root==NULL) return NULL;

    if (root->val == target) return root;

    if (root->val > target) {
        TreeNode* temp = find_ceiling( root->left, target );
        return (temp==NULL)? root: temp;
    }

    return find_ceiling( root->right, target );
}

Longest Consecutive Sequence

[Question]

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

[Analysis]
Each element is a consecutive sequence of length 1. Suppose element A, it can be represented as a sequence [A, A+1). If A+1 is in the array, the sequence that starts from A can be represented as [A, A+2). Repeat the finding process, using a hash table which maps A (the starting value) to the ending value (exclusive) of the sequence.

It is equivalent to use mapping between A and "length of consecutive sequence", as shown in 2nd solution code.

[Solution]
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        if (num.size()<2) return num.size();
     
        int max_len = 1;
        unordered_map<int,int> map;    
        for (auto a: num)
            map[a] = a+1;

        for(auto kv: map) {
            int a = kv.first;
            int next = map[a];
            while (map.find(next)!=map.end()) {
                map[a] = map[next];
                map.erase(next);
                next = map[a];
            }
            max_len = max(map[a]-a, max_len);
        }

        return max_len;
    }
};

//Solution 2nd
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        if (num.empty()) return 0;
        int max_len = 1;
   
        unordered_map<int,int> map;  
        for (auto& a: num) map[a] = 1;

        for(auto& kv: map) {
            int a = kv.first;
            int next=a+map[a];
            while (map.count(next)) {
                map[a] += map[next];
                map.erase(next);
                next=a+map[a];
            }
            max_len = max(max_len, map[a]);
        }

        return max_len;
    }
};

Power (X, N)

[Question]
    Calculate Power(X, N).

[Analysis]
   Power(X, N) = Power(X, N/2) * Power(X,N/2) if N is even;
   Power(X, N) = Power(X, N/2) * Power(X,N/2) * X if N is odd;
   There are corner cases, when N is negative or X is negative, to consider.

[Solution]
class Solution {
public:
    double power(double x, int n) {
        if (n==0) return 1;
        if (n==1) return x;    
        double tmp = power(x, n/2);
     
        if ( (n & 0x0001) ==0 )
              return (tmp * tmp);
       else
              return (tmp * tmp * x );      
    }
 
    double pow(double x, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function

        bool rev=false, neg=false;
        if (n<0) {
            n= -n;
            rev = true;
        }
     
        if (x<0 && n & 0x0001) {
            x = -x;
            neg = true;
        }
     
        double rslt = power(x, n);
        if (rev) rslt = 1/rslt;
        if (neg) rslt = -rslt;
        return rslt;

    }
};