# Find largest complete subtree in a binary tree
### Problem
For this problem, a subtree of a binary tree means any connected subgraph. A binary tree is complete if every internal node has two children, and every leaf has exactly the same depth. Describe and analyze a recursive algorithm to compute the largest complete subtree of a given binary tree. Your algorithm should return both the root and the depth of this subtree. See Figure . for an example


### Algorithm Description
This algorithm will recurse to the bottom of the tree, then at each node compare its left substree with its right subtree and determine which one is larger or if they can be merged together to make a larger one, returning the subtrees root and depth.

fun check(node, depth)
{
    if (node == nill)    return (nill, -1);
    
    (leftChild, leftDepth) = check(node.left);
    (rightChild, rightDepth = check(node.right);
    
    if (leftDepth == rightDepth) {
            return (node, leftDepth + 1); 
    }
    
    if (leftDepth >= rightDepth)    return (leftChild, leftDepth);
    else                            return (rightChild, rightDepth);
}

### Correctness proof
The algorithm will correctly return the root (node) of the tallest possible subtree in a given tree
#### Base Case
Empty tree/node -> returns (null,-1) which is right as there is no subtree
#### Case 1
Both children are complete subtrees and have the same depth: the current node becomes the root of a new subtree and depth = leftchilds depth + 1
#### Case 2
If the node's substrees are inbalanced then the biggest substree stays the same

There are no other cases. QED

### Time Complexity
Since each node would be visited once only the time complexity is O(n)