largest complete subtree in a binary tree

Question

I am defining a complete subtree as a tree with all levels full and the last level left justified i.e. all nodes are as far left as possible, and I want to find the largest subtree in a tree that is complete.

One method is to do the method outlined here for every node as root, which would take O(n^2) time.

Is there a better approach?

Answer 1

Since there isn't a C++ solution above, I have added my solution. Let me know if you feel there is anything incorrect or any improvements that can be made.

struct CompleteStatusWithHeight {
 bool isComplete;
 int height;
};

int FindLargestCompletetSubTreeSize(const unique_ptr<BinaryTreeNode<int>>& tree)
{
  return CheckComplete(tree).height;
}

CompleteStatusWithHeight CheckComplete(const unique_ptr<BinaryTreeNode<int>>& tree)
{
if (tree == nullptr) {
       return {true, -1};  // Base case.
}

auto left_result = CheckComplete(tree->left);
if (!left_result.isComplete) {
  return {false, 0};  // Left subtree is not balanced.
}
auto right_result = CheckComplete(tree->right);
if (!right_result.isComplete) {
  return {false, 0};  // Right subtree is not balanced.
}

bool is_balanced = abs(left_result.height - right_result.height) == 0;
bool is_left_aligned = (left_result.height - right_result.height) == 1;
bool is_leaf =  left_result.height  == -1 && right_result.height ==-1;
bool is_complete = is_balanced || is_left_aligned || is_leaf;

int height = max(left_result.height, right_result.height) + 1;
return {is_complete, height};
}