Maximum sum of nodes in Binary tree with no directly connected nodes

Problem: Get the maximum sum given a binary tree where you can't use directly connected nodes.

Example:

Input: 
     4
    / \
   2   3
    \   \ 
     3   2

Output: 9 
Explanation: Maximum sum with no directly connected nodes = 4 + 3 + 2 = 9.

Approach: We can use Post order traversal. Basically here we traverse the binary tree and at each node we will calculate two sums; 1) Max sum using the node 2) Max sum without using the node so basically the method will return an array which will contain [max_sum_using_node, max_sum_without_using_node].

At every node we will recursively call this method to get the above mentioned sums for left node of current node and right node of current node. Now our result will be: 

• SumUsingTheCurrentNode = node.Value + leftSum[1] + rightSum[1]. Basically if you see our return value, you will see that leftSum[1] = max_sum_without_using_left_node and rightSum[1] is max_sum_without_using_right_node. We are choosing index 1 because we don't want to use immideate left and right nodes given we are using the current node.
• SumWithOutUsingTheCurrentNode = Max(leftSum[0], leftSum[1]) + Max(rightSum[0], rightSum[1]). Here as we are not using current node, there are no restrictions. We can go for the maximum value of leftSum and rightSum to maximize the result.
• [SumUsingTheCurrentNode, SumWithOutUsingTheCurrentNode] will be returned

Now once we get the above array for the root, we can just return the maximum of [max_sum_using_node, max_sum_without_using_node].

Implementation in C#:

         public int MaxSumWithNoConnectedNode()

        {

            if (this.Root == null)

            {

                return 0;

            }

            int[] maxSums = this.MaxSumWithNoConnectedNode(this.Root);

            return Math.Max(maxSums[0], maxSums[1]);

        }

        // Returns [max_sum_using_node, max_sum_without_using_node]

        private int[] MaxSumWithNoConnectedNode(BinaryTreeNode node)

        {

            if (node == null)

            {

                return new int[] { 0, 0 };

            }

            int[] leftMaxSums = this.MaxSumWithNoConnectedNode(node.LeftNode);

            int[] rightMaxSums = this.MaxSumWithNoConnectedNode(node.RightNode);

            

            // Can't include leftMaxSum[0] and rightMaxSum[0] as current node is used

            int useThisNodeSum = node.Value + leftMaxSums[1] + rightMaxSums[1]; 

            

            // No restrictions here as current node is not used, just take the maximum

            int dontUseThisNodeSum = Math.Max(leftMaxSums[0], leftMaxSums[1]) + Math.Max(rightMaxSums[0], rightMaxSums[1]);

            return new int[] { useThisNodeSum, dontUseThisNodeSum };

        }

Complexity: O(n)