2
votes

Suppose that you are given an arbitrary binary tree. We'll call the tree balanced if the following is true for all nodes:

  1. That node is a leaf, or
  2. The height of the left subtree and the height of the right subtree differ by at most ±1 and the left and right subtrees are themselves balanced.

Is there an efficient algorithm for determining the minimum number of nodes that need to be added to the tree in order to make it balanced? For simplicity, we'll assume that nodes can only be inserted as leaf nodes (like the way that a node is inserted into a binary search tree that does no rebalancing).

3
why would you need to add nodes. wouldn't you just rebalance it without adding new ones?nathan hayfield
@nathanhayfield- If I was trying to build a balanced binary search tree, then yes, it would be best to try to rebalance the tree. This is more of a hypothetical question.templatetypedef
Calculate the height at every node, done?Alex DiCarlo
@AlexDiCarlo- If there is a height difference of +6 at a node, can you use that to immediately infer how many nodes must be added to the smaller tree to get the balance factor to correct to +1?templatetypedef
@nathanhayfield What is zero? We're talking about re-balancing by inserting new nodes, not re-balancing by moving nodes around.Alex DiCarlo

3 Answers

2
votes

The following tree fits into your definition, although it doesn't seem very balanced to me:

Depth 5 "balanced" tree

EDIT This answer is wrong, but it has enough interesting stuff in it that I don't feel like deleting it yet. The algorithm produces a balanced tree, but not a minimal one. The number of nodes it adds is:

where n ranges over all nodes in the tree, lower(n) is the depth of the child of n with the lower depth and upper(n) is the depth of the child of n with the higher depth. Using the fact that the sum of the first k fibonacci numbers is fib(k+2)-1, we can replace the inner sum with fib(upper(n)) - fib(lower(n) + 2).

The formula is (more or less) derived from the following algorithm to add nodes to the tree, making it balanced (in python, only showing the relevant algorithms):

def balance(tree, label):
  if tree is None:
    return (None, 0)
  left, left_height = balance(tree.left_child, label)
  right, right_height = balance(tree.right_child, label)
  while left_height < right_height - 1:
    left = Node(label(), left, balanced_tree(left_height - 1, label))
    left_height += 1
  while right_height < left_height - 1:
    right = Node(label(), right, balanced_tree(right_height - 1, label))
    right_height += 1
  return (Node(tree.label, left, right), max(left_height, right_height) + 1)

def balanced_tree(depth, label):
  if depth <= 0:
    return None
  else:
    return Node(label(),
                balanced_tree(depth - 1, label),
                balanced_tree(depth - 2, label))

As requested: report the count instead of creating the tree:

def balance(tree):
  if tree is None:
    return (0, 0)
  left, left_height = balance(tree.left_child)
  right, right_height = balance(tree.right_child)
  while left_height < right_height - 1:
    left += balanced_tree(left_height - 1) + 1
    left_height += 1
  while right_height < left_height - 1:
    right += balanced_tree(right_height - 1) + 1
    right_height += 1
  return (left + right, max(left_height, right_height) + 1)

def balanced_tree(depth):
  if depth <= 0:
    return 0
  else:
    return (1 + balanced_tree(depth - 1)
              + balanced_tree(depth - 2))

Edit: Actually, I think that other than computing the size of a minimum balanced tree of depth n more efficiently (i.e. memoizing it, or used the closed form: it's just fibonacci(n+1)-1), that's probably as efficient as you can get, since you have to examine every node in the tree in order to test the balance condition, and that algorithm looks at every node precisely once.

1
votes

Will this work?

Go recursively from the top. If the node A is imbalanced, add a node B on the short side and and enough left nodes to node B until node A is balanced.

(Of course, count the nodes added.)

1
votes

First let's find the height of left child and right child of each node.

Now consider the root of the tree it's height is

1+max(height(root.left) , height(root.right)).

let's assume left has height of n-1 then right should have minimum height of n-2. Let's define another relation here req[node] -> the minimum required height of each node to make the tree balanced.

if you observe for a node to be at height h one of it's children should be at least at n-1 and to make it balanced the other children should be at at least n-2.

start from root with req[root] = height of root

The pseudo code is :

    def chk_nodes(root, req):

      if(root == NULL):
        return minNodes(req)

      if(left[root] > right[root]):
       return chk_nodes(root.left  , req-1) + chk_nodes(root.right , req-2)

      else return chk_nodes(root.left , req-2) + chk_nodes(root.right , req-1)

Now what is minNodes(int req)?

It's a function which return 'minimum no of nodes required to create a balanced binary tree of height h'. the function is quite intuitive and self-explanatory.

      def minNodes(int req) :
          if req < 0 : return 0
          return 1 + minNodes(req-1) + minNodes(req-2)

In minNodes function , a lookup table can be used to make it O(1) lookup time and O(N) for construction.

when the chk_nodes function runs recursively , at leaf-nodes we will be left with left-node , req . if that req > 0 then there should be a new sub-tree (balanced) with height req. Hence minNodes( req ) are required at this particular leaf-node.

With only 2 traversals and O(N) time, O(N) space the problem is solved.