CODEWITHSUNDEEP
calgorithmdata-structuresbinary-tree
i.Beginner
i.Beginner

Reputation: 21

How to check whether a complete binary tree is value-balanced

How can I check whether a given complete binary tree represented by an array is a value balanced binary tree? By value-balanced I mean, if for each and every node, the sum of the integer values of nodes on the left-hand side is equal to the sum of values on the right-hand side. What is the C-like algorithm?
It's easy to find out the indices of the nodes having children. But I'm unable to develop the logic for computing the sum at each node recursively. The sum also needs to be computed in such a manner that the sum of all the nodes of the left subtree below a particular node will be equal to the right-handed counterpart of it and dig down below in a similar manner. How is it possible using an array?

Upvotes: 0

Views: 328

Answers (1)

amit
amit

Reputation: 178441

You can do a post order traversal of the tree, that sums each subtree, and when back to the root (of each subtree), evaluates if the two subtrees have the same weight.

C-like Pseudo code:

res = 1; //global variable, can also be used as sending pointer to res instead
int verifySums(Node* root) {
   if (root == null) return 0;
   int leftSum = verifySums(getLeft(root));
   int rightSum = verifySums(getRight(root));
   if (leftSum != rightSum) res = 0;
   return leftSum + rightSum + getValue(root);
}

Where

  • Node getLeft(Node*) is returning a pointer to a Node representing the left child of the argument
  • Node getRight(Node*) is returning a pointer to a Node representing the right child of the argument
  • int getValue(Node*) is returning the value of the given node

The idea is to do a post-order traversal that sums the value of all children to the left, get sum to the right and then:

  1. Verify correctness - if it's not, the answer of the entire tree is no, and set it in res.
  2. sum the two sums + current node, and return it back to parent.

Upvotes: 2

Related Questions