The question :- Find the size of the largest complete subtree in a binary tree.

A complete binary tree is a tree with all levels filled except the last which is left filled.

I tried a postorder type approach but there were just too many cases to handle. I could not find the answer on google so I decided to ask it here

Я понять не могу ты про binary tree или че? Как tree может быть complete я понять не могу

Yes its a binary tree, I edited the post

Create 2 arrays,A(an integer array of size 64) and B(a boolean array which indicates if the nodes in the ith level are left indented).. Now for each level starting from 1,count the no of nodes in that level which are left indented,if this turns out to be a power of 2,store log2(no of left indented nodes found at this level),else store -2,along with this feel the array B(just check if 1st node of this level is there or not). Answer will be the longest increasing contiguous subarray in A with (difference between consecutive terms as 1) + 1(if B[i + 1] is set)..

I dont understand. Why is the answer the longest increasing contiguous subarray? Also what is the point of storing -2?

Auto comment: topic has been updated by siehpe (previous revision, new revision, compare).Well, you know how many nodes should be in a tree with k levels, right? Just compute how many levels are in each subtree and check if it matches with their size.

EDIT: according to what op said below, this would be an approach to verify if the subtree is a perfect binary tree, not a complete one.

Well if the root is considered level 0, then the number of nodes at level k can be between 2^k and 2^(k + 1) — 1 inclusive. However this does not necessarily mean that the subtree is complete because it may not be LEFT filled.

I'm not sure I understand you. I believe what gabrielsimoes proposed is perfectly correct.

Suppose that for each vertex

Vyou calculateSize[V] — amount of vertices in his subtree (includingV) andMaxDepth[V] the deepest vertex in his subtree (depth relative toV, so children ofVhave depth 1).Then

V's subtree is complete if and only if:Size[V] = 2^{MaxDepth[V] + 1}- 1Check for all subtrees and get the largest one. Everything can easily be done with one DFS traversal in

O(N).Yeah, that's what I meant. Only clarifying

MaxDepth[v] would be thedepthof the deepest vertex in the subtree ofv. You said it, but writting in another way: first vertex would have depth 0.I think you guys are talking about Perfect binary tree in which all nodes at each level are fully filled. However the question is for a complete binary tree where the last level may not be fully filled but it should be left filled

Ah, yes, you are correct. You should specify as not everyone is familiar with the notation (difference between full and complete binary tree, which I just googled). Sorry.

From what I understand a complete binary tree is one that may have only some prefix of the last layer filled (though all other layers must be full). A full binary tree is one that has all layers completely filled. Note that all full binary trees are also complete binary trees but not vice versa.

Here is another approach then:

Let's again compute the maximal depth in the subtree of each vertex and denote it again as

MaxDepth[V] for some vertexV. Now we want to compute the following boolean values:Full[V] =trueif the subtree ofVis a full binary tree.Complete[V] =trueif the subtree ofVis a complete binary tree.Now we can recursively compute these values. Obviously for leaves we have both of them being

true. Now suppose we have some vertexVwith left childV1 and right childV2.To find whether the subtree is full is quite easy:

Full[V] =Full[V1]&&Full[V2]&&MaxDepth[V1]==MaxDepth[V2]If the subtree turns out to be full we can just mark it as complete too. Otherwise, to find whether it is complete we have some cases:

1) if

MaxDepth[V1] =MaxDepth[V2] then the subtree of V is complete only if V1 is full and V2 is complete and hence:Complete[V] =Full[V1]&&Complete[V2]2) if

MaxDepth[V1] =MaxDepth[V2] + 1 then the subtree of V is complete only if V1 is complete and V2 is full, hence:Complete[V] =Complete[V1]&&Full[V2]3) in any other case the subtree of V is

notcomplete.And just to cover all corner cases — if we're working with a vertex that has only one child, then consider the other non-existing child to have maximum depth of -1 and to be both full and complete.

This is all linear with one DFS traversal and should work fine in

O(N). After the execution you'll have inComplete[V] whether the subtree of some vertexVis a complete binary tree. From then on it's easy to find stuff such as the largest one.I haven't tested it so if something's wrong feel free to correct me.

Maybe I misunderstood your approach, but shouldn't the cases be:

However, I'm still cofused with the conventions, lol. I think a full binary tree is the one in which all nodes which aren't leaves have two children. If I'm correct, what you called "full" would be "perfect".

Ah, it might be good for learners to state this approach is kind of a DP one.

Not exactly. If v1 is the left child and (maxdepth[v1] + 1 == maxdepth[v2]) then in no case can the tree be complete because the depth of the right side is more than the left. If v1 is the right child then (maxdepth[v1] == maxdepth[v2] + 1) is invalid for the same reason. Basically you have to delete one of those conditions depending on which child is the left and which one is the right

Ah, yes. I was confused again with complete binary trees.

Thank you ! Now the solution seems complete ;)

I think it can be done a bit easier — just recursively compute number of maximum "present" vertex and minimum "nonpresent". These numbers differ by one if and only if the subtree is complete.

I don't understand why people keep on downvoting questions in codeforces blog. It is all about learning through discussions. If the question is from an ongoing contest, it is perfectly fine but otherwise we all should try to help the concerned person