Minimum Cost Binary Tree

#include <bits/stdc++.h>
using namespace std;


int setHeights(int i, vector<int> &heights, vector<int> &cost){
    int n = heights.size();
    if(i>=n){
        return 0;
    }

    int leftHeight = 0, rightHeight = 0;
    if(2*i+1<n){
        leftHeight = cost[2*i] + setHeights(2*i+1, heights, cost);
    }

    if(2*i+2<n){
        rightHeight = cost[2*i+1] + setHeights(2*i+2, heights, cost);
    }

    return heights[i] = max(leftHeight, rightHeight);
}

int getAns(int i, vector<int> &heights, vector<int> &cost){
    int n = heights.size();
    if(i>=n){
        return 0;
    }

    int leftAns = 0, rightAns=0;

    if(2*i+1<n){
        leftAns = heights[i] - heights[2*i+1] - cost[2*i] + getAns(2*i+1, heights, cost);
    }
    if(2*i+2<n){
        rightAns = heights[i] - heights[2*i+2] - cost[2*i+1] + getAns(2*i+2, heights, cost);
    }

    return leftAns + rightAns;
}

int main() {
    // your code goes here

    // Ques Input
    vector<int> cost = {3,1,2,1,5,4};
    int n = 7;


    // Soln begins
    vector<int> heights(n, 0);

    setHeights(0, heights, cost);

    int ans = getAns(0, heights, cost);

    cout<<ans<<endl;

    return 0;
}