sol.cc

// Sol1.

int stringToLong(string str) {
        const char* p = str.c_str();
        
        // Skip space in the front.
        for(; *p == ' '; ++p);
        
        // Get the sign of the input.
        bool sign;
        if(*p == '+' || *p == '-') {
            sign = *p == '+' ? true : false;
            ++p;
        }
        long long ret = 0;
        while(*p >= '0' && *p <= '9') {
            ret = ret*10 + (*p - '0');
            // Check whether the output overflow.
            if(ret > numeric_limits<int>::max())
                return sign == true ? numeric_limits<int>::max() : numeric_limits<int>::min();
            ++p;
        }
        return sign == true ? (int)ret : (int)(-ret);
}

// Sol2.

struct TreeNode {
	TreeNode* left, *right, *middle;
	int val;

	TreeNode(int val) : val(val), left(NULL), right(NULL), middle(NULL) {}
};

class TrinaryTree {
public:
	TrinaryTree() : root(NULL) {}

	void add(int val) {
		if(!root)
			root = new TreeNode(val);
		else
			addHelper(val, root);
	}

	// Add a dummy head to avoid boundary case.
	bool remove(int val) {
		TreeNode dummy(INT_MAX);
		dummy.left = root;
		bool ret = remove(val, root, &dummy);
		if(ret) {
			root = dummy.left;
		}
		return ret;
	}

private:
	void addHelper(int val, TreeNode* node) {
		assert(node != NULL);
		if(val == node->val) {
			if(node->middle)
				addHelper(val, node->middle);
			else 
				node->middle = new TreeNode(val);
		} else if(val > node->val) {
			if(node->right)
				addHelper(val, node->right);
			else
				node->right = new TreeNode(val);
		} else {
			if(node->left)
				addHelper(val, node->left);
			else
				node->left = new TreeNode(val);
		}
	}

	// Remove node with value val. Return false if cannot find the node.
	bool remove(int val, TreeNode* node, TreeNode* par) {
		if(node->val > val) {
			if(node->left)
				return remove(val, node->left, node);
			else
				return false;
		} else if(node->val < val) {
			if(node->right)
				return remove(val, node->right, node);
			else
				return false;
		} else {
			if(node->middle) {
				TreeNode* curr = node->middle, *curr_parent = node;
				while(curr->middle) {
					curr_parent = curr;
					curr = curr->middle;			
				}
				delete curr_parent->middle;
				curr_parent->middle = NULL;
			} else if(!node->left && !node->right) { // Leaf node. Delete it and reset parent fields.
				if(par->left == node)
					par->left = NULL;
				if(par->right == node)
					par->right = NULL;
				delete node;
			}else if(node->left && node->right) { 
				// two branches. set its value to be its in-order successor's value.
				// Then call remove again to remove that duplicate node.
				TreeNode* curr = node->right;
				while(curr->left) {
					curr = curr->left;				
				}
				node->val = curr->val;
				node->middle = curr->middle;
				curr->middle = NULL;
				return remove(node->val, node->right, node);
				// Belowing node only has one branch. so just set parent field and delete node.
			} else if(par->left == node) {
				par->left = node->left ? node->left : node->right;
				delete node;
			} else if(par->right == node) {
				par->right = node->left ? node->left : node->right;
				delete node;
			}
				return true;
			}
	}
private:
	TreeNode* root;
};