The idea here is to optimize the previous approach using dynamic programming. We are calling some functions again and again so we will call them once and store their values in a ‘DP’ array.

For example, when calculating RIDED and NOT_RIDED:

RIDED = ROOT.VAL + MAX_FUN(ROOT.LEFT, True) + maxFun(ROOT.RIGHT, True)

NOT_RIDED = MAX_FUN(ROOT.LEFT, False) + MAX_FUN(ROOT.RIGHT, False)

The MAX_FUN is called four times. Moreover, when we call MAX_FUN(ROOT.LEFT, True) and MAX_FUN(ROOT.LEFT, False), those two involve the same calculations internally, such as MAX_FUN(NODE.LEFT.LEFT, False).

We can also see this in the below recursive tree:

We see the repetitive calls are made from the recursive tree.

  Now we will store our MAX_FUN possible in a hashmap because MAX_FUN is called many times again and again to save time and redundant calculations we store the MAX_FUN in HASH_MAP

So we use a recursive function that returns the maximum fun value that can be achievable.

Algorithm: 

Map ‘RIDED_MAP’, ‘NOT_RIDED_MAP’.

Int maxFun(root, parentVisited)
{
If ‘parentVisited’ = true that means parent node is already visited

    If ridedMap[root] has already set before 
        then return ridedMap[root] 
   
   then we have only one choice
   
   ridedMap[root] := maxFun(root->left,false) + maxFun(root ->, false) 
   return ridedMap[root]
                         
If ‘parentVisited’ = false that means parent node is not rided 

    If notRidedMap[root] has already set before 
        then return notRidedMap[root] 
    
    Then we have two choice:
                 
    rided = root.data + maxFun(root.right, true) + maxFun(root.left, true)
                   
    notRided =  maxFun(root.right, false) + maxFun(root.left, false)
                    
    notRidedMap[root] := max(rided, notRided)
              
return max(rided, notRided)
}

The idea here is to use iterative DP but before using iterative DP we need to map or assign an index to each node so that we then able to make a DP array.

We use the most common mapping that is used in heaps and segment trees.

We create an array where nodes are arranged from the BFS suffix.

For example:

Given tree: [39, 84, 35, 5, -1, 95, 9,-1,-1,-1,-1,-1,-1]

Array-based index tree will be like this:

We can achieve this using BFS and storing the node value at a particular index in the array.

Now declare two arrays ‘DP_RIDED’ and ‘DP_NOT_RIDED’ where 

DP_RIDED[i] represents maximum fun we can achieve if we start riding from this node and ride this ride.

DP_NOT_RIDED[i] represents maximum fun we can achieve if we start riding from this node and do not ride this ride.

Base Case:

For all leave nodes 
  DP_RIDED[i] = NODE.VAL
  DP_NOT_RIDED[i] = 0

Transition states:

DP_RIDED[i]  = NODE.VAL + ∑ DP_NOT_RIDED[CHILD]

DP_NOT_RIDED[i] = ∑ max( DP_RIDED[CHILD], DP_NOT_RIDED[CHILD] )

Algorithm:

• Declare 3 arrays ‘TREE’, ‘DP_RIDED’, ‘DP_NOT_RIDED’.
• Transform the tree from node-base to array-based using simple BFS.
• Using the transition
  • DP_RIDED[i]  = TREE[i] + ∑ DP_NOT_RIDED[CHILD]
  • DP_NOT_RIDED[i] = ∑ max( DP_RIDED[CHILD], DP_NOT_RIDED[CHILD] )

Assign a value to the DP array

• return max(DP_RIDED[0], DP_NOT_RIDED[0])

Description of BFS function

The function will take 3 parameters.

Tree: array to store the tree in an array.

ROOT: binary tree node

CHILDREN_INDEX: a graph that contains an index of the children nodes according to the array-based tree.

int BFS(vector<int> &tree, binaryTreeNode<int> *root, map<int,vector<int>>childrenIndex){
Int index = -1;
queue q -> first element is binarytree node and second is parent index

while(!q.empty){

index++;
currentNode = q.first.
Parent = q.second

If currentNode is NULL 
    then we will skip this
else
    tree.add(currentNode.data)
    childrenIndex[parent].add(index) 
   
q.add({currentNode.left,index})
q.add({currentNode.right,index}) 
}
return index
}