StringtoLong, Implement Trinary Tree

StringtoLong

Converts input String to Long

Solution

• input validation
• Over/Underflow
• positive/negative

long stringToLong(String s)
	{
		// Use Regex to filter out illegal inputs
		if(!s.matches("-?\\d+")){ 
			throw new NumberFormatException("input String " + s + " is illegal number format");
		}
		// Convert a string to a long 
		long result = 0;
		boolean IsNegative = s.charAt(0)== '-';
		int start=IsNegative ? 1:0;
		for(int i=start;i<s.length();i++){
			/* Deal with overflow and underflow */
			
			if(((!IsNegative) && result > (Long.MAX_VALUE)/10 )|| ((!IsNegative) && result == (Long.MAX_VALUE)/10 && (s.charAt(i) - 48)>7)){
				
				throw new NumberFormatException("input String " + s + " out of bound (overflow)");
			}
			else if((IsNegative && (-1 * result) < (Long.MIN_VALUE)/10 ) || (IsNegative &&  (-1 * result) == (Long.MIN_VALUE)/10 ) && (s.charAt(i) - 48)>8 ){
				
				throw new NumberFormatException("input String " + s + " out of bound (underflow)");
			}
			else{
				result=result * 10 + (s.charAt(i) - 48);
			}
		}
		return IsNegative ? -result : result;
	}

Implement Trinary Tree

Insersion and Deletion

Solution

• Define Node class
• Recursivly add/delete node

public class TrinaryNode{
	int val;
	TrinaryNode left;
	TrinaryNode right;
	TrinaryNode middle;
	TrinaryNode(int x){
		this.val = x;
	}

}
////////////
TrinaryNode root;
	TrinaryTree(){
		root = null;
	}
	TrinaryTree(int x){
		root = new TrinaryNode(x);
	}

	//Insertion
	TrinaryNode insert(TrinaryNode root, int x){

		TrinaryNode tmp = new TrinaryNode(x);
		//Insert root if root is not set
		if(root==null){
			root = tmp;
			return root;
		}
		//Find target position in left subtree if x is smaller than current node
		if(root.val > x){
			if(root.left==null){
				root.left = tmp;
			}
			else{
				insert(root.left, x);
			}
		}
		//Find target position in right subtree if x is larger than current node
		if(root.val < x){
			if(root.right==null){
				root.right = tmp;
			}
			else{
				insert(root.right, x);
			}
		}
		//Find target position in middle subtree if x is equal to current node
		if(root.val == x){
			if(root.middle==null){
				root.middle = tmp;
			}
			else{
				insert(root.middle, x);
			}
		}
		return root;
	}

	//Deletion
	TrinaryNode delete(TrinaryNode root, int x){
		//Target node is in left subtree
		if(root.val > x){
			root.left = delete(root.left, x);
		}
		//Target node is in right subtree
		else if(root.val < x){
			root.right = delete(root.right, x);
		}
		//Target node equals current node
		else if(root.middle != null){
			//Delete middle node that is equal to current node
			root.middle = delete(root.middle ,x);
		}
		//Replace current node with its successor in right subtree
		else if(root.right !=null){ 
			root.val = Sucessor(root.right).val;
			delete(root, Sucessor(root.right).val);
		}
		//Transplant left subtree directly
		else {
			root = root.left;
		}
		return root;
	}

	//Function to find successor in right subtree
	TrinaryNode Sucessor(TrinaryNode root){
		TrinaryNode tmp = root;
		while(tmp.left!=null){
			tmp=tmp.left;
		} 
		return tmp;
	}

	//Function to in-order traverse the tree for testing purpose
	void test_print(TrinaryNode root){
		if (root!=null){
			System.out.println("Node Value: " + root.val);
		}
		else return;
		test_print(root.left);
		test_print(root.middle);
		test_print(root.right);
	}