Binary Tree - height and size

What is height and what is size of Binary Tree?
The size of a tree is the size of the root. The size of a node is the number of descendants it has including itself. Therefore, the tree size is the number of all tree nodes.
The height (or depth) of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a depth of zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has depth and height −1.
In the picture below you see a binary tree with height 3 and size 9.

Binary Tree

Here are two functions calculating the size and the height of a binary tree. The first function is recursive and returns the height:

int heightOfBinaryTree(BinaryTree node) {
    if (node == null) {
        return -1;
    } else {
        return 1 + Math.max(heightOfBinaryTree(node.left),
                            heightOfBinaryTree(node.right));
    }
}

The size solution is recursive, too:

int binaryTreeSize(BinaryTree node) {
    if (node == null) {
        return 0;
    }
    return (binaryTreeSize(node.left) + binaryTreeSize(node.right) + 1);
}

Bracket combinations (Google Interview Question)

Write a function that prints all combinations of well-formed brackets. The input is a number which says how many pairs of brackets will the different outputs have. For Brackets(3) the output would be:
((()))  (()())  (())()  ()(())  ()()().

The solution below uses recursion. The logic here is very simple - every output is constructed starting with its first symbol. On each step a new symbol is added following these rules:

• rule 1: if the number of opened brackets is equal to the number of closing brackets, then the only next possible symbol to add is '('
• rule 2: if the number of opened brackets is more than the number of closing brackets, then there are two options - either we add ')' or '('
• rule 3: if the number of opened brackets is more than half the number of all brackets, then the construction went wrong and we break the whole case
• rule 4: if the number of opened brackets is less than the number of closing brackets, then the construction went wrong and we break the whole case
• rule 5: the last symbol of the output cannot be '('

private void Brackets(String output, int open, int close, int total) {
    if (output.length() == total * 2 && output.charAt(total * 2 - 1) != '(') {
        System.out.println(output);
    } else if (open > total || open < close) {
        return;
    } else {
        if ((open == close)) {
            Brackets(output + "(", open + 1, close, total);
        }
        if ((open > close)) {
            Brackets(output + "(", open + 1, close, total);
            Brackets(output + ")", open, close + 1, total);
        }
    }
}

public void Brackets(int total) {
    Brackets("", 0, 0, total);
}

This is an Interview Question for Software Engineers at Google. Here you can find more information.

Travel from string to string (Google Interview question)

Google Interview Question (http://www.careercup.com/question?id=14947965):

Given a source string and a destination string write a program to display sequence of strings to travel from source to destination. Rules for traversing:
1. You can only change one character at a time
2. Any resulting word has to be a valid word from dictionary
Example: Given source word CAT and destination word DOG , one of the valid sequence would be
CAT -> COT -> DOT -> DOG
Another valid sequence can be
CAT -> COT - > COG -> DOG
One character can change at one time and every resulting word has be a valid word from dictionary

The solution here includes not only functions but global variables as well.

public class SourceToDestinationString {
    // Container for the valid words
    HashSet dictionary = null;
    // Container for words already passed by a word sequence
    HashSet visited;

    public SourceToDestinationString() {
        super();
        visited = new HashSet();
        dictionary = new HashSet();
        initDictionary();
    }

    private void initDictionary() {
        // Add the wrods in the dictionary
    }

    // Returns all valid words suitable for the next step of the path
    private ArrayList generateWords(String source, int position) {
        if (position < 0 || position >= source.length())
            return null;
        ArrayList result = new ArrayList();
        for (char ch = 'A'; ch <= 'Z'; ch++) {
            StringBuffer tmpWord = new StringBuffer(source);
            tmpWord.setCharAt(position, ch);
            String word = tmpWord.toString();
            if (dictionary.contains(word)) {
                result.add(word);
            }
        }

        return result;
    }

    // The sequence of words is written in the stack 'path' 
    public void sourceToDestinationString(Stack path, String destination) {
        String source = path.peek();
        if (source.equals(destination)) {
            System.out.print("Solution is ");
            System.out.println(path);
            return;
        }

        visited.add(source);

        for (int i = 0; i < source.length(); i++) {
            ArrayList words = generateWords(source, i);
            for (String nextWord : words) {
                if (visited.contains(nextWord))
                    continue;
                path.push(nextWord);
                sourceToDestinationString(path, destination);
                path.pop();
            }
        }
  
        visited.remove(source);
    }
}

Fibonacci numbers - 4 solutions

Find the n-th Fibonacci number. The Fibonacci numbers are integers 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
Wikipedia says:

By definition, the first two numbers in the Fibonacci sequence are 0 and 1 (alternatively, 1 and 1), and each subsequent number is the sum of the previous two. 

For example the 7-th Fibonacci number in the sequence is 8. Here are a few solutions. The first one is a trivial one and follows the definition - i.e. it uses recursion.

long fibonacciRecursive(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

The second solution is iterative. A drawback here is that the size of the array which is used to store the Fibonacci numbers needs to be defined statically.

long fibonacciIterative(int n) {
    int size = 100;
    long[] fibonacciNumbers = new long[size + 1];
    fibonacciNumbers[0] = 0;
    fibonacciNumbers[1] = 1;
  
    for (int i = 2; i <= n; i++) {
        fibonacciNumbers[i] = fibonacciNumbers[i - 1]
                            + fibonacciNumbers[i - 2];
    }
    return fibonacciNumbers[n];
}

The third solution is again iterative. The difference here is that it uses an array with size 3. This is a very elegant and optimized solution.

long fibonacciIterativeLowMem(int n) {
    int[] fibonacciNumbers = new int[3];
    fibonacciNumbers[0] = 0;
    fibonacciNumbers[1] = 1;

    for (int i = 2; i <= n; i++) {
        fibonacciNumbers[i % 3] = fibonacciNumbers[(i - 1) % 3]
                                + fibonacciNumbers[(i - 2) % 3];
    }
    return fibonacciNumbers[n % 3];
}

Here is one more solution that uses an optimization called memoization. The idea here is that we avoid the calculation of the tasks we already had calculated.

long fibonacciMemoization(int n) {
    int size = 100;
    long[] fibonacciNumbers = new long[size+1];
    fibonacciNumbers[0] = 0;
    fibonacciNumbers[1] = 1;
    for (int i = 2; i < size; i++) {
        fibonacciNumbers[i] = -1;
    }
  
    if (fibonacciNumbers[n] != -1) {
        return fibonacciNumbers[n];
    } else {
        fibonacciNumbers[n] = fibonacciMemoization(n - 1)
                            + fibonacciMemoization(n - 2);
        return fibonacciNumbers[n];
    }
}

Reverse a LinkedList

Given a singly linked list. You have to revers it.

The first solution uses recursion.

Node reverseList(Node previous, Node current) {
    Node tmp;
    if (current.next == null) {
        current.next = previous;
        return current;
    }
    tmp = reverseList(current, current.next);
    current.next = previous;
    return tmp;
}

The second solution is non-recursive.

Node reverse(Node current) {
    Node tmp;
    Node previous = null;
    while (current != null) {
        tmp = current.next;
        current.next = previous;
        previous = current;
        current= tmp;
    }
    return previous;
}

How to find k-th element from the end of a linked list?

The solution below uses recursion to get the number of elements in the linked list and then prints only the value at the k-th node from end of the Linked List.

public static void kthElement(LinkedList list, int k) {
    ListIterator iterator = list.listIterator();
    handleNextElement(iterator, k);
}

private static int handleNextElement(ListIterator iterator, int k) {
    int elementValue = 0;
    if (!iterator.hasNext()) {
        return 0;
    }

    elementValue = iterator.next();
    int count = handleNextElement(iterator, k) + 1;

    if (count == k) {
        System.out.println(elementValue);
    }

    return count;
}

k-th node from end

Another solution is non-recursive where you run two runners/iterators in parallel with distance k between them.

Integer kthElement(LinkedList list, int k) {
    if (k < 1 || k > list.size()) {
        return null;
    }

    ListIterator iterator = list.listIterator();
    for (int i = 0; i < k; i++) {
        if (iterator.hasNext()) {
            iterator.next();
        } else {
            return null;
        }
    }

    ListIterator iterator2 = list.listIterator();
    while (iterator.hasNext()) {
        iterator.next();
        iterator2.next();
    }

    Integer result = iterator2.next();
    return result;
}

2 iterators with distance k between them

This solution takes O(n) time and O(1) space.

Array is transformed into Binary Tree

How will you place all elements of a given array into binary tree? The given array is unsorted.
Here is one recursive solution of the problem:

TreeNode toTree(ArrayList array){
    if (array == null || array.size() == 0) {
        return null;
    }
 
    TreeNode result = new TreeNode(array.get(0));
    for (int i = 1; i < array.size(); i++) {
        addTo(result, array.get(i));   
    }
  
    return result;  
}

void addTo(TreeNode node, int i) {
    if (i < node.d) {
        if (node.getLeft() == null) {
            node.setLeft(new TreeNode(i));
        } else {
            addTo(node.getLeft(), i);
        }
    } else {
        if (node.getRight() == null) {
            node.setRight(new TreeNode(i));
        } else {
            addTo(node.getRight(), i);
        }
    }
}