The largest full subtree in a binary tree

Question

I define a complete subtree as a tree with all levels filled, and the last level is left justified, i.e. all nodes are deleted as far as possible, and I want to find the largest subtree in the completed tree.

One way is to make the method here for each node as root, which will take O (n ^ 2) time.

Is there a better approach?

Answer 1

Since in C ++ there is no solution above, I added my solution. Let me know if you feel that there is something wrong 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};
}

Answer 2

Python. , . : [, , ]

• x = node
• y =

• z: 0 - , 1 - node , 2 -

  def largest_complete_tree(root):
  
      result = traverse_complete(root)
      print('largest complete subtree: {}'.format(result[0]))
  
  def traverse_complete(root):
      if root:
          left = traverse_complete(root.left)
          right = traverse_complete(root.right)
          max_complete = max(left[0], right[0])
          max_height = max(left[1], right[1])
          left_child_only = 1 if (left[2] == 1 and right[0] == 0) or (left[0] == 1 and right[0] == 0) else 0
  
          # 5 conditions need to pass before left and right can be joined by this node
          # to create a complete subtree.
          if left[0] < right[0]:
              return [max_complete, 0, 2]
          if left[2] == 2 or right[2] == 2:
              return [max_complete, 0, 2]
          if abs(left[1]-right[1]) > 1:
              return [max_complete, 0, 2]
          if (left[2] == 1 and right[2] == 1) or (left[2] == 0 and right[2] == 1):
              return [max_complete, 0, 2]
          if left[0] == right[0] and left[0] != 2**left[0] - 1:
              return [max_complete, 0, 2]
          return [left[0] + right[0] + 1, max_height + 1, left_child_only]
      else:
          return [0,0,0]
  

Answer 3

node, , node . node , node . node (r, w). w <= 2^r.

node , node (r, w) = (1, 1).

node (r1, w1) (r2, w2), :

• r1 > r2, node (r2 + 1, 2^r2 + w2)
• r1 == r2 w1 == 2^r1, node (r1 + 1, w1 + w2)
• r1 == r2 w1 < 2^r1, node (r1 + 1, w1) :

         root     
         ....
    /  \     /   \
   l    l    r    r
  /\   /    /\    /
  l l  l    r r  r

          m     
         ....
    /  \     /   \
   m    m    m    m
  /\   /    /\    /
  m m  m    r r  r

4. r1 < r2 w1 == 2^r1, node (r1 + 1, 2 * w1) :

         root     
         ....
    /  \      /   \
   l    l     r    r
  /\   / \    /\    /\
  l l  l  l   r r  r  r
             /
            r

          m     
         ....
    /  \      /   \
   m    m     m    m
  /\   / \    /\    /\
 m  m  m  m   m m  m  m
             /
            r

5. r1 < r2 w1 < 2^r1, node (r1 + 1, w1)

:

         root     
         ....
    /  \      /   \
   l    l     r    r
  /\   /      /\    /\
  l l  l      r r  r  r
             /
            r

          m     
         ....
    /  \      /   \
   m    m     m    m
  /\   /     /\    /\
 m  m  m     r r  r  r
            /
            r

(r, w) node . O(n). node r , node max w, node .

Answer 4

, Elements of Programming Interviews. .

.

. max , - ( , java ). , . , , (-1, false). T ' , . T- max, .

, .

• : root == null root -
• .

• / - leftInfo rightInfo.

• , , . , , max . , . , , . , (, NewSize). , max, .

. O (n) O (h), h - . ( , O (n)).

 public class Solution {

    public static void main(String[] args){
        TreeNode[] trees = new TreeNode[10];
        for(int i = 0; i < 10; i++){
            trees[i].val = i;
        }
    }

    public int largestCompleteTree(TreeNode root){
        int[] max = new int[1];
        helper(root, max);
        return max[0];
    }

    private Info helper(TreeNode root, int[] max){
        //Base case:
        if(root == null){
            return new Info(0, true);
        }

        if(root.left == null && root.right == null){
            max[0] = Math.max(max[0], 1);
            return new Info(1, true);
        }

        //Recursion
        Info leftInfo = helper(root.left, max);
        Info rightInfo = helper(root.right, max);  

        //Process based on left subtree and right subtree.
        //Neither is complete.
        if(!leftInfo.isComplete && !rightInfo.isComplete){
            //Do not need to update the max value.
            return new Info(-1, false);
        }
        //One of the subtree is complete, the current tree is not complete
        else if(!leftInfo.isComplete || !rightInfo.isComplete){
            if(leftInfo.isComplete){
                max[0] = Math.max(max[0], leftInfo.size);
                return new Info(-1, false);//the value has been recorded
            }else{
                max[0] = Math.max(max[0], rightInfo.size);
                return new Info(-1, false);
            }
        }
        //Both subtrees are complete,           
        else{
            int size = 0;
            if(((rightInfo.size & (rightInfo.size + 1)) == 0 &&
                leftInfo.size >= rightInfo.size &&
                leftInfo.size <= rightInfo.size*2 + 1)||
                ((leftInfo.size & (leftInfo.size + 1)) == 0 &&
                        rightInfo.size >= (leftInfo.size - 1)/2 &&
                        rightInfo.size <= leftInfo.size))
                {
                    size = leftInfo.size + rightInfo.size + 1;
                    max[0] = Math.max(max[0], size);
                    return new Info(size, true);
                }
             else{ //find the subtree with the greater size
                size = leftInfo.size > rightInfo.size ? leftInfo.size : rightInfo.size;
                max[0] = Math.max(max[0], size);
                return new Info(0, false);
            } 
        }   
    }
    class Info {
        boolean isComplete;
        int size;

        public Info(int size, boolean isComplete){
            this.isComplete = isComplete;
            this.size = size;
        }
    }
}

Answer 5

"Elements of Programming Interviews", , , , , , :

private struct str
        {
            public bool isComplete;
            public int height, size;
            public str(bool isComplete, int height, int size)
            {
                this.isComplete = isComplete;
                this.height = height;
                this.size = size;
            }
        }

        public int SizeOfLargestComplete()
        {
            return SizeOfLargestComplete(root).size;
        }

        private str SizeOfLargestComplete(Node n)
        {
            if (n == null)
                return new str(true, -1, 0);
            str l = SizeOfLargestComplete(n.left);
            str r = SizeOfLargestComplete(n.right);

            if (!l.isComplete || !r.isComplete)
                return new str(false, 0, Math.Max(l.size, r.size));

            int numberOfLeftTreeLeafes;
            if (l.height == -1)
                numberOfLeftTreeLeafes = 0;
            else
                numberOfLeftTreeLeafes = l.size - ((1 << l.height) - 1);

            bool leftTreeIsPerfect = (1 << (l.height + 1)) - 1 - l.size == 0;

            //if left subtree is perfect, right subtree can have leaves on last level
            if (leftTreeIsPerfect)
                if (l.size - r.size >= 0 && l.size - r.size <= numberOfLeftTreeLeafes)
                    return new str(true, l.height + 1, l.size + r.size + 1);
                else
                    return new str(false, 0, Math.Max(l.size, r.size));
            //if left subtree is not perfect, right subtree can't have leaves on last level
            //so size of right subtree must be the same as left without leaves
            else
                if (r.size == l.size - numberOfLeftTreeLeafes)
                return new str(true, l.height + 1, l.size + r.size + 1);
            else
                return new str(false, 0, Math.Max(l.size, r.size));

        }

Answer 6

, (, , EPI). , , , .

/**
 * Returns the largest complete subtree of a binary tree given by the input node
 *
 * @param root the root of the tree
 */
public int getLargestCompleteSubtree(INode<TKeyType, TValueType> root) {
    max = 0;
    calculateLargestCompleteSubtree(root);

    return max;
}

/**
 * Returns the largest complete subtree of a binary tree given by the input node
 *
 * @param root the root of the tree
 */
public TreeInfo<TKeyType, TValueType> calculateLargestCompleteSubtree(INode<TKeyType, TValueType> root) {
    int size = 0;

    // a complete subtree must have the following attributes
    // 1. All leaves must be within 1 of each other.
    // 2. All leaves must be as far left as possible, i.e, L(child).count() > R(child).count()
    // 3. A complete subtree may have only one node (L child) or two nodes (L, R).

    if (root == null)
    {
        return new TreeInfo<>(true, 0);
    }
    else if (!root.hasLeftChild() && !root.hasRightChild())
    {
        return new TreeInfo<>(true, 1);
    }

    // have children
    TreeInfo<TKeyType, TValueType> leftInfo = calculateLargestCompleteSubtree(root.getLeft());
    TreeInfo<TKeyType, TValueType> rightInfo = calculateLargestCompleteSubtree(root.getRight());

    // case 1: not a complete tree.
    if (!leftInfo.isComplete || !rightInfo.isComplete)
    {
        // Only one subtree is complete. Set it as the max and return false.
        if(leftInfo.isComplete) {
            max = Math.max(max, leftInfo.size);
        }
        else if(rightInfo.isComplete)
        {
            max = Math.max(max, rightInfo.size);
        }

        return new TreeInfo<>(false, -1);
    }

    // case 2: both subtrees complete
    int delta = Math.abs(leftInfo.size - rightInfo.size);
    if (delta <= 1)
    {
        // both are complete but R could be 1 greater...use L tree.
        size = leftInfo.size + 1;
        max = Math.max(max, size);
        return new TreeInfo<>(true, size);
    }
    else
    {
        // limit to size of R + 1 if L - R > 1, otherwise L
        if(leftInfo.size > rightInfo.size)
        {
            max = Math.max(max, leftInfo.size);
            size = rightInfo.size + 1;
        }
        else
        {
            max = Math.max(max, rightInfo.size);
            size = leftInfo.size;
        }

        return new TreeInfo<>(true, size + 1);
    }
}

Answer 7

Python. , .

# return (is_complete, max_height_so_far, is_perfect)
def is_complete_tree(node):
    # null
    if not node:
        return (True, -1, True)

    left_subtree = is_complete_tree(node.left_child)
    right_subtree = is_complete_tree(node.right_child)

    # if any of subtrees isn't complete, current tree is not complete
    if not left_subtree[0] or not right_subtree[0]:
        return (False, max(left_subtree[1], right_subtree[1]), False)

    # if both subtrees are complete, there are 2 cases in order for current tree to be complete
    # case 1: subtrees with same height
    # left subtree must be perfect
    if left_subtree[1] == right_subtree[1] and left_subtree[2]:
        return (True, left_subtree[1] + 1, right_subtree[2])

    # case 2: left subtree taller by 1
    # right subtree must be perfect
    if left_subtree[1] == right_subtree[1] + 1 and right_subtree[2]:
        return (True, left_subtree[1] + 1, False)

    # otherwise not complete
    return (False, max(left_subtree[1], right_subtree[1]), False)

Answer 8

: , , .

With the current number of nodes and height, you can calculate the root number of nodes and height through information related to its direct children, taking into account the relationship between child heights and if they are perfect subtrees or not.

The solution is O (n) time complexity and O (h) spatial complexity (the stack of function calls corresponds to the root through a unique path to the current node).

Here is the Python code for this solution, and you can find the full point with examples here :

from collections import namedtuple


class BTN():
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

# number of nodes for a perfect tree of the given height
def max_nodes_per_height(height: int) -> int:
    return 2**(height + 1) - 1


def height_largest_complete_subtree(root: BTN) -> int:
    CompleteInformation = namedtuple('CompleteInformation', ['height', 'num_nodes', 'max_height'])

    def height_largest_complete_subtree_aux(root: BTN) -> CompleteInformation:
        if (root is None):
            return CompleteInformation(-1, 0, 0)

        left_complete_info = height_largest_complete_subtree_aux(root.left)
        right_complete_info = height_largest_complete_subtree_aux(root.right)

        left_height = left_complete_info.height
        right_height = right_complete_info.height

        if (left_height == right_height):
            if (left_complete_info.num_nodes == max_nodes_per_height(left_height)):
                new_height = left_height + 1
                new_num_nodes = left_complete_info.num_nodes + right_complete_info.num_nodes + 1
                return CompleteInformation(new_height,
                                           new_num_nodes,
                                           max(new_height, max(left_complete_info.max_height, right_complete_info.max_height))
                                          )
            else:
                new_height = left_height
                new_num_nodes = max_nodes_per_height(left_height)
                return CompleteInformation(new_height,
                                           new_num_nodes,
                                           max(new_height, max(left_complete_info.max_height, right_complete_info.max_height))
                                          )
        elif (left_height > right_height):
            if (max_nodes_per_height(right_height) == right_complete_info.num_nodes):
                new_height = right_height + 2
                new_num_nodes = min(left_complete_info.num_nodes, max_nodes_per_height(right_height + 1)) + right_complete_info.num_nodes + 1
                return CompleteInformation(new_height,
                               new_num_nodes,
                               max(new_height, max(left_complete_info.max_height, right_complete_info.max_height))
                              )
            else:
                new_height = right_height + 1
                new_num_nodes = max_nodes_per_height(right_height) + right_complete_info.num_nodes + 1
                return CompleteInformation(new_height,
                               new_num_nodes,
                               max(new_height, max(left_complete_info.max_height, right_complete_info.max_height))
                              )

        elif (left_height < right_height):
            if (left_complete_info.num_nodes == max_nodes_per_height(left_height)):
                new_height = left_height + 1
                new_num_nodes = left_complete_info.num_nodes + max_nodes_per_height(left_height) + 1
                return CompleteInformation(new_height,
                           new_num_nodes,
                           max(new_height, max(left_complete_info.max_height, right_complete_info.max_height))
                          )
            else:
                new_height = left_height
                new_num_nodes = (max_nodes_per_height(left_height - 1) * 2) + 1
                return CompleteInformation(new_height,
                           new_num_nodes,
                           max(new_height, max(left_complete_info.max_height, right_complete_info.max_height))
                          )

    return height_largest_complete_subtree_aux(root).max_height