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);
}

Binary Tree - sum of two nodes (Google Interview Question)

Here is another Google Interview problem:

Given a BST and a value x. Find two nodes in the tree whose sum is equal x. Additional space: O(height of the tree). It is not allowed to modify the tree.

The solution uses two stacks and the size of the binary tree. The approach is recursive and is similar to the binary search algorithm in arrays. The two stacks contain candidate answer numbers and on each iteration based on a calculation we pop or add new number in a stack. The binary tree size is used in cases where no answer exists. In these cases the algorithm starts endless loop.

void algorithm(Stack stk1, Stack stk2,
   double x, int size) {
    if (size == 0){
        System.out.println("No answer is found!");
        return;
    }
    if (!stk1.isEmpty() && !stk2.isEmpty()) {
        if (stk1.peek().data + stk2.peek().data == x) {
            System.out.println("Nodes are:\n" + stk1.peek().data + "\n"
            + stk2.peek().data);
            return;
        }
        if (stk1.peek().data + stk2.peek().data > x) {
            if(stk2.size()==1){
                BinaryTree node = stk2.pop();
                stk2.add(node);
                addRightNodes(stk2, node.getLeft());
            } else {
                addLeftNodes(stk2, stk2.pop());
            }    
        } else if (stk1.peek().data + stk2.peek().data < x) {
            if(stk1.size()==1){
                BinaryTree node = stk1.pop();
                stk1.add(node);
                addLeftNodes(stk1, node.getRight());
            } else {
                addRightNodes(stk1, stk1.pop());
            }    
        }
    }
    algorithm(stk1, stk2, x, --size);
}

See also the "Sum of nodes at odd and even levels of Binary Tree" problem.

Sum of nodes at odd and even levels of Binary Tree

Given a Binary Tree, write a function which calculates the difference between the sum of node values at odd levels and sum of node values at even levels, i.e. function(BinaryTree) = (sum of values of nodes at odd height) - (sum of values of node at even height). Consider the root node is at height 1.

int calculateDifference(BinaryTree root) {
    if (root == null) {
        return 0;
    }
    int result = root.getData() - calculateDifference(root.getLeft())
              - calculateDifference(root.getRight());
    return result;
};

The solution is short and uses recursion. The idea is that you negate all levels under the current one (the level of the current node) and you do that on each step of the recursion.

sum[l1] - (sum[l2] - (sum[l3] - (sum[l4] - ... = sum[l1] - sum[l2] + sum[l3] - sum[l4]...

Deifference between sum of nodes on even height and sum of nodes on odd height

Are two Binary Trees mirror image of each other?

How can you check if two binary trees are mirror image of each other? It would mean that if you do an inorder traversal on the trees, the elements of the second tree will be visited in reversed order compared to the order of the elements visited in the first tree. Here is the Java code:

boolean areMirrorTrees(BinaryTree a, BinaryTree b) {
    if (a == null && b == null) {
        return true;
    }
    if (a == null || b == null) {
        return false;
    }
    return a.data == b.data && areMirrorTrees(a.left, b.right)
            && areMirrorTrees(a.right, b.left);
}

Inorder traversal of the first tree will be: 3, 4, 5, 6, 7, 8, 9, 10, 12, 13.
Inorder traversal of the second tree will be: 13, 12, 10, 9, 8, 7, 6, 5, 4, 3.

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);
        }
    }
}