Home Summing binary tree producing unexpected results
Reply: 1

Summing binary tree producing unexpected results

Flyrom
1#
Flyrom Published in 2018-01-13 03:20:54Z

Trying to sum all nodes in a BST of Integers

The method is passed 0, but when it transitions from the left sub tree to right sub tree, the sum seems to decrease. Any help would be appreciated

The method is passed the root and a counter initialized to 0

public static int sumTree(TreeNode root,int sum) {
if (root != null) {
  System.out.println("current value: " + root.getValue());
  sum += (Integer) root.getValue();
  System.out.println(sum);
  sumTree(root.getLeft(),sum);
  sumTree(root.getRight(),sum);
}

return sum;
}
John Kugelman
2#
John Kugelman Reply to 2018-01-13 03:27:43Z
sumTree(root.getLeft(),sum);
sumTree(root.getRight(),sum);

Just looking at these calls in isolation, they don't do anything. Their return values are being lost, and modifications to the recursive copies of sum don't affect the caller's sum; they're different variables.

public static int sumTree(TreeNode root) {
    if (root == null) {
        return 0;
    }

    System.out.println("current value: " + root.getValue());
    int sum = (Integer) root.getValue();
    System.out.println(sum);
    sum += sumTree(root.getLeft());
    sum += sumTree(root.getRight());

    return sum;
}

The fix is to add the return values of the two recursive calls to sum. There's no need to have sum as a parameter: the sum of a sub-tree is independent of the rest of the tree above it.

You need to login account before you can post.

About| Privacy statement| Terms of Service| Advertising| Contact us| Help| Sitemap|
Processed in 0.336323 second(s) , Gzip On .

© 2016 Powered by mzan.com design MATCHINFO