Finding all the leafs in a binary tree and summing them to their fathers-CodePudding

I am really struggling with a problem: I have to find all the leaves in a binary tree and sum them to their father using recursion and only basic controls(no specialised functions).

I tried checking all the nodes' children to see if those were leaves and then add them to their fathers but it seems I can't get the recursion done correctly

t = { val: 1, sx: { val: 8, sx: { val: 7, sx: {}, dx: {} }, dx: { val: 

1, sx: {}, dx: {} } }, dx: { val: 3, sx: { val: 5, sx: {}, dx: {} }, dx: {} } };

function pota3(t) {
  if (t == null) { return }

  if (t.dx != null) {
    if (t.dx.sx == null && t.dx.dx == null) {
      t.val  = t.dx.val
        delete t.dx 
    }
  }
  if (t.sx != null) {
    if (t.sx.sx == null && t.sx.dx == null) {
      t.val  = t.sx.val
        delete t.sx 
    }
  }
  pota3(t.dx)
  pota3(t.sx)
}
pota3(t)

wanted result:

    t = {
  val: 1,
  sx: { val: 16,sx: {}, dx: {}},
  dx: { val: 8, sx: {}, dx:{} }
  }

CodePudding user response：

You could define some exit condition, like no node or no val property and assign val and all other subnodes.

const
    sum = node => {
        if (!node || !('val' in node)) return 0;
        return node.total = node.val   sum(node.sx)   sum(node.dx);
    },
    t = { val: 1, sx: { val: 8, sx: { val: 7, sx: {}, dx: {} }, dx: { val:  1, sx: {}, dx: {} } }, dx: { val: 3, sx: { val: 5, sx: {}, dx: {} }, dx: {} } };

console.log(t);
sum(t);
console.log(t);

.as-console-wrapper { max-height: 100% !important; top: 0; }

CodePudding user response：

const t = { val: 1, sx: { val: 8, sx: { val: 7, sx: {}, dx: {} }, dx: { val: 
1, sx: {}, dx: {} } }, dx: { val: 3, sx: { val: 5, sx: {}, dx: {} }, dx: {} } };

console.log(t);

const addLeafs = (point) => {
  if(point.sx.val !== undefined || point.dx.val !== undefined) {
    // not a leaf
    if(point.sx.val !== undefined) {
      // try to add first child value if it's not empty
      point.val  = addLeafs(point.sx);
    }
    if(point.dx.val !== undefined) {
      // try to add second child if it's not empty
      point.val  = addLeafs(point.dx);
    }
    // it's not a leaf, so parent should not increase value
    return 0;
  } else {
    // it's a leaf - add it's value to parent
    return point.val;
  }
}

addLeafs(t);
console.log(t);