Balanced sums in binary tree

Question

I found an interesting algorithmic problem. We are given a binary tree which has value 0 in every vertex apart from leaves. In leaves we have two options:

1. value is unknown, but we know it is a natural number >=1

2. value is known and it is a natural number >=1

The problem is to decide if it is possible to set every unknown value in leaves such that every subtree of a given tree has the same sum of values in vertexes in its left and right subtree.

For example:

tree1:

      0
     / \
    0   ?
   / \
  0   5
 / \
?   ?

The answer is NO - taking into consideration that every question mark has to be a natural number, it is of course not possible

tree2:

        0
     /     \
    0      0
   / \    / \
  0   10 ?   ?
 / \
5   ?

The answer is YES - we set: 5, 10, 10 respectively in every question mark.

So far, I came up only with an obvious algorithm - we create system of linear equations and check if it has a solution in natural numbers. But I think it can be very slow for big trees and it should be a better way to solve it. Can anybody help? I would be very grateful.

Answer 1

I think a recursive solution works just fine. At every node get the weight of the left and right children. You have the following cases:

1. L and R are both known: The node is valid iff L == R
2. Neither L or R is known: This node is unknown and has multiplicity twice that of the largest multiplicity of L and R
3. Exactly one of L or R is unknown: This node is valid iff the weight of the known child is divisible by the multiplicty of the unknown child. It's weight is twice the weight of the known child.

The idea here is that you need to keep track of how many unknown children are below a certain node, since values can only be integers. Multiplicity always doubles because, at one node, even if its left child has 4 unknowns and its right has 1 unknown, then the 1 unknown will have to be a multiple of 4 and so the multiplicity of this node will need to be 8.

Note: I'm using the word multiplicity here and it isn't really quite right, but I couldn't think of a good word to use.

Here is code, in Go, that demonstrates this solution on your examples:

package main

import (
  "fmt"
)

// Assume that (Left == nil) == (Right == nil)
type Tree struct {
  Val         int
  Left, Right *Tree
}

func (t *Tree) GetWeight() (weight int, valid bool) {
  if t.Left == nil {
    return t.Val, true
  }
  l, lv := t.Left.GetWeight()
  r, rv := t.Right.GetWeight()
  if !lv || !rv {
    return 0, false
  }
  if l < 0 && r < 0 {
    if l < r {
      return 2 * l, true
    }
    return 2 * r, true
  }
  if l < 0 {
    return 2 * r, r%(-l) == 0
  }
  if r < 0 {
    return 2 * l, l%(-r) == 0
  }
  return r + l, r == l
}

func main() {
  t := Tree{0,
    &Tree{0,
      &Tree{0,
        &Tree{Val: 5},
        &Tree{Val: -1},
      },
      &Tree{Val: 10},
    },
    &Tree{0,
      &Tree{Val: -1},
      &Tree{Val: -1},
    },
  }
  w, v := t.GetWeight()
  fmt.Printf("%d, %t\n", w, v)
  t = Tree{0,
    &Tree{0,
      &Tree{0,
        &Tree{Val: -1},
        &Tree{Val: -1},
      },
      &Tree{Val: 5},
    },
    &Tree{Val: -1},
  }
  w, v = t.GetWeight()
  fmt.Printf("%d, %t\n", w, v)
}