CareerCup

This is easy one, Same as height balance.

Rather than increment by 1, you have to increment by the node->data

Assum root of the tree is given, you can do recursive in-order call to right and left subtrees and get the sum.

sumTree(struct tree* node, int *sum) {
    if(node == NULL) {
        return;
    }
    /* Do in order traversal */
    sumTree(node->left, sum);
    *sum = *sum + node->data;
    sumTree(node->right, sum);
}

int main() {
    int rightSum = 0;
    int leftSum = 0;
    sumTree(root->left, &leftSum);

    sumTree(root->right, &rightSum);
    
     if(leftSum == rightSum) {
         printf("Tree  is balanced \n");
     }else {
         printf("Tree not balanced \n");
     }
}

I think the allBalancedNodes() can be achieved in O(n) with post Order traversal.

Have a variable called total in the node like below:

class Node
{
    int total;  // -- a variable indicating sum seen until now

   int key;
   int value;
  
   Node left;
   Node right;
   Node parent;
}

isBalanced() definition:

public boolean isBalanced()
	{
		return ( ( left == null && right == null ) || ( left != null && right != null && left.total == right.total ) );
	}

Post order traversal updating total on each node :

public void postOrderTraversal( Node node )
	{
		if ( node == null ) return;
		postOrderTraversal( node.left );
		postOrderTraversal( node.right );
		
		node.total = node.value;
		if ( node.left != null ) node.total += node.left.total;
		if ( node.right != null ) node.total += node.right.total;
		
		System.out.println( " Is balanced : " + node.isBalanced() );
	}

In the example above, shouldn't it be

[12].isBalanced() -> False.  [3, 5]

?

import java.util.List;
import java.util.Queue;
import java.util.ArrayList;
import java.util.LinkedList;

public class BalanceSumBinaryTree
{
	public static void main(String[] args)
	{
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.right = new TreeNode(1);

		root.right.left = new TreeNode(1);
		
		BalanceSumBinaryTree b = new BalanceSumBinaryTree();
		System.out.println(b.isBalance(root));
		System.out.println(b.allBalanceNodes(root));
	}

	public boolean isBalance(TreeNode root)
	{
		if(root==null)
			return true;

		int left = helper(root.left);
		int right = helper(root.right);

		return left==right;
	}

	private int helper(TreeNode root)
	{
		if(root==null)
			return 0;
		int left = helper(root.left);
		int right = helper(root.right);

		return left + root.val + right;
	}

	public List<TreeNode> allBalanceNodes(TreeNode root)
	{
		Queue<TreeNode> next = new LinkedList<>();
		Queue<TreeNode> curr;
		next.offer(root);
		
		List<TreeNode> res = new ArrayList<>();

		while(!next.isEmpty())
		{
			curr = next;
			next = new LinkedList<>();

			while(!curr.isEmpty())
			{
				TreeNode temp = curr.poll();
				if(isBalance(temp))
					res.add(temp);

				if(temp.left!=null)
					next.offer(temp.left);
				if(temp.right!=null)
					next.offer(temp.right);
			}
		}
		return res;
	}
}

class TreeNode
{
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int val)
	{
		this.val = val;
	}

	public String toString()
	{
		return this.val+" ";
	}
}