Sum two binary trees and return the result of the sum in a third one

user_13831347 0
Viewed 252

so i have to create a code that can sum two different binary trees and return the result of it in a third binary tree. It has to work using recursivity. Here's the code that i currently have. It kinda works but it does not working recursively.

   public BTree btNodeSum(BTree b, BTree b2) throws TreeException {
        if (isEmpty()) {
            throw new TreeException("Binary Tree is empty");
        }
        BTree tree = new BTree();
        tree.root = btNodeSum(b.root, b2.root);
        return tree;
    }
    
   private BTreeNode btNodeSum(BTreeNode b, BTreeNode b2) throws TreeException{
       BTreeNode n = new BTreeNode(0);
       if(b == null)
           return b2;
       if(b2 == null)
           return b;
       if(b.left != null && b2.left != null){
           b = btNodeSum(b.left, null);
           b2 = btNodeSum(null, b2.left);
           n.data = (int) btNodeSum(b, null).data  + (int) btNodeSum(null, b2).data;
       }
       else if(b.right != null && b2.right != null){
           b = btNodeSum(b.right, null);
           b2 = btNodeSum(null, b2.right);
           n.data =  (int) btNodeSum(b, null).data  + (int) btNodeSum(null, b2).data;
       }
       
       b = btNodeSum(b.left, null);
       b2 = btNodeSum(null, b2.left);
       b = btNodeSum(b.right, null);
       b2 = btNodeSum(null, b2.right);
       
       return n;
   }

The two trees that i am trying to sum have these values:

Click to look at the trees

And the output that a im getting is this one: sum of tree 1 and tree 2: PreOrder Tour: 8(null, 0),

I would appreciate all the help!!

tree recursion java
1 Answers

A simple Recursive function for sum of two binary trees:

/**
 * Definition for a binary tree node.
 * public class BTreeNode {
 *     int val;
 *     BTreeNode left;
 *     BTreeNode right;
 *     BTreeNode() {}
 *     BTreeNode(int val) { this.val = val; }
 *     BTreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public BTreeNode btSum(BTreeNode t1, BTreeNode t2) {
        if(t1==null){
            return t2;
        }
        if(t2==null){
            return t1;
        }
        BTreeNode t3 = new BTreeNode();
        t3.val = t1.val + t2.val;
        t3.left = btSum(t1.left, t2.left);
        t3.right = btSum(t1.right, t2.right);
        return t3;
    }
}
user_90423180
Related