Java Code that finds Least Common Ancestor in a binary tree

This problem is broken down into 3 pieces.

1. Find the paths to the target nodes.
2. Push them in a stack.
3. Reverse the stacks to find the element just before a mismatch.

Crux is this:

========================================================================

public static Node leastCommonAncestor(Node root, Node one, Node two)

{

if( one == null ) return two;

if( two == null ) return one;

Stack s1 = new Stack();

Stack s2 = new Stack();

s1.push(root);

s2.push(root);

boolean oneFound = findPath(root, one, s1);

boolean twoFound = findPath(root, two, s2);

if( ! oneFound || ! twoFound ) return null;

Stack rev1 = reverseStack(s1);

Stack rev2 = reverseStack(s2);

Node first = (Node) rev1.pop();

Node second = (Node) rev2.pop();

Node lca = first;

while( first.value == second.value )

{

lca = first;

if( ! rev1.empty() ) 

{

first = (Node) rev1.pop();

}

if( ! rev2.empty() )

{

second = (Node) rev2.pop();

}

}

return lca;

}

========================================================================

Code that reverses the stack should be easy. But findPath is the one needs attention.

========================================================================

public static boolean findPath(Node current, Node destNode, Stack s)

{

if( current == null ) return false;

if( current.value == destNode.value )

{

return true;

}

if( current.left != null )

{

s.push(current.left);

boolean found = findPath(current.left, destNode, s);

if(  found ) return true;

else s.pop();

}

if( current.right != null )

{

s.push(current.right);

boolean found = findPath(current.right, destNode, s);

if(  found ) return true;

else s.pop();

}

return false;

}

========================================================================

Test execute it here.

Java Code that converts String to Integer. Standard atoi function.

As a first thing, we need to sanitise the string.

1. It could be null.
2. It could have leading and trailing spaces.
3. It could have an additional +/- symbols.
4. It could have invalid characters, spaces and what not. 

As a next thing, for all we know the string could contain values more than Integer.MAX_VALUE. So, we don't accept strings of length more than that. 

Now, we simply pluck out each character, get it's integer value and add the corresponding exponent's according to the digit's position. We need to take caution when trying to add each characters because the string could still have a value more than Integer.MAX_VALUE. 

If we add the new value like this

    convertedInt + newValueToAdd > Integer.MAX_VALUE

it might overflow. 

So we do the opposite.
  convertedInt <= Integer.MAX_VALUE - newValueToAdd

Here is the implementation.
========================================================================

public static void main (String[] args) throws java.lang.Exception
{
String a = "2147483647";
System.out.println("Integer : " + atoi(a));
}

public static int atoi(String a) throws Exception
{
String sane = checkSanity(a);
if( sane == null )
{
throw new Exception("Not compatible");
}

if( sane.length() > 10 )
{
throw new Exception("Overflow");
}

if( sane.length() <= 0 )
{
throw new Exception("Underflow");
}

int convertedInt = 0;
int exponent = 0;
for( int i = sane.length() - 1; i >= 0 ; i-- )
{
int newDigit = Character.getNumericValue( sane.charAt(i) );

int newValueToAdd = (int) ( Math.pow(10, exponent) * newDigit );

if( convertedInt <= Integer.MAX_VALUE - newValueToAdd )
{
convertedInt += newValueToAdd;
}
else
{
throw new Exception("Overflow");
}

exponent++;
}

return convertedInt;
}

public static String checkSanity(String a)
{
// could be null
if( a == null )
{
return null;
}

// Trim leading and trailing spaces.
String b = a.trim();

// Should it have + or - symbol, consider.
String c;
if( b.charAt(0) == '+' || b.charAt(0) == '-' )
{
c = b.substring(1);
}
else
{
c = b.substring(0);
}

// could have special characters and non numbers.
for( int i = 0; i < c.length(); i++ )
{
if( ! Character.isDigit(c.charAt(i)) )
{
return null;
}
}

return c;
}
}

========================================================================

Test execute it here.

Java code that adds '1' to linked list of digits by reversing the list.

The idea is to reverse the list first. Keep adding the carry from the start to the end and perhaps, create a carry node at the end and then reverse back to normal order.

========================================================================

class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// create LL
                 ..
                 ..          
                 ..
                 ..
Node reversedHead = reverseLL(head);
incrementLL(reversedHead);
Node normal = reverseLL(reversedHead);
}

public static void incrementLL(Node head)
{
Node current = head;
Node previous = current;
int carry = 1;

while( current != null && carry > 0 )
{
int temp = current.value;

temp += carry;
carry = temp / 10;
temp %= 10;

current.value = temp;
previous = current;
current = current.next;
}

if( carry > 0 )
{
Node last = createNewNode(carry);
previous.next = last;
}

}

public static Node reverseLL(Node head)
{
Node current = head;
Node previous = null;

while( current != null )
{
Node temp = current.next;

current.next = previous;
previous = current;
current = temp;
}

return previous;
}

}
========================================================================

Test Execute it here.