siehpe's blog

Help Needed In An Interview Question (Trees)
By siehpe, history, 8 years ago, In English

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

  • Vote: I like it
  • +17
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

      Suppose that for each vertex V you calculate Size[V] — amount of vertices in his subtree (including V) and MaxDepth[V] the deepest vertex in his subtree (depth relative to V, so children of V have depth 1).

      Then V's subtree is complete if and only if:

      Size[V] = 2MaxDepth[V] + 1 - 1

      Check for all subtrees and get the largest one. Everything can easily be done with one DFS traversal in O(N).

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Yeah, that's what I meant. Only clarifying MaxDepth[v] would be the depth of the deepest vertex in the subtree of v. You said it, but writting in another way: first vertex would have depth 0.

        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 4   Vote: I like it +4 Vote: I do not like it

          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 vertex V. Now we want to compute the following boolean values:

          Full[V] = true if the subtree of V is a full binary tree.

          Complete[V] = true if the subtree of V is 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 vertex V with left child V1 and right child V2.

          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 not complete.

          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 in Complete[V] whether the subtree of some vertex V is 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            if (maxdepth[v1] == maxdepth[v2])
    complete[v] = complete[v1] && complete[v2];
else if (maxdepth[v1] + 1 == maxdepth[v2])
    complete[v] = complete[v1] && full[v2];
else if (maxdepth[v1] == maxdepth[v2] + 1)
    complete[v] = full[v1] && complete[v2];
else
    complete[v] = 0;

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it +10 Vote: I do not like it

              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

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

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

                → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
»
8 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply