Find the max path from root to leaf of a n-ary tree without including values of two adjacent nodes in the sum

Question

I recently got interviewed and was asked the following question.

Given an n-ary tree, find the maximum path from root to leaf such that maximum path does not contain values from any two adjacent nodes.

(Another edit: The nodes would only have positive values.)

(Edit from comments: An adjacent node means node that share a direct edge. Because its a tree, it means parent-child. So if I include parent, I can not include child and vice versa.)

For example:

        5
    /        \
  8          10
 /  \       /   \
1    3      7    9

In the above example, the maximum path without two adjacent would be 14 along the path 5->10->9. I include 5 and 9 in the final sum but not 10 because it would violate the no two adjacent nodes condition.

I suggested the following algorithm. While I was fairly sure about it, my interviewer did not seem confident about it. Hence, I wanted to double check if my algorithm was correct or not. It seemed to work on various test cases I could think of:

For each node X, let F(X) be the maximum sum from root to X without two adjacent values in the maximum sum.

The formula for calculating F(X) = Max(F(parent(X)), val(X) + F(grandParent(X)));

Solution would have been Solution = Max(F(Leaf Nodes))

This was roughly the code I came up with:

class Node
{
    int coins;
    List<Node> edges;

    public Node(int coins, List<Node> edges)
    {
      this.coins = coins;
      this.edges = edges;
    }
}

class Tree
{
  int maxPath = Integer.MIN_VALUE;

  private boolean isLeafNode(Node node)
  {
    int size = node.edges.size();
    for(int i = 0; i < size; i++)
    {
      if(node.edges.get(i) != null)
        return false;
    }
    return true;
  }

  // previous[0] = max value obtained from parent
// previous[1] = max value obtained from grandparent
  private void helper(Node node, int[] previous)
  {
    int max = Math.max(previous[0], max.val + previous[1]);
    //leaf node

    if(isLeafNode(node))
    {
      maxPath = Math.max(maxPath, max);
      return;
    }

    int[] temp= new int[2];
    temp[0] = max;
    temp[1] = prev[0];
    for(int i = 0; i < node.edges.size(); i++)
    {
      if(node.edges.get(i) != null)
      {
        helper(node.edges.get(i), temp);
      }
    }
  }


  public int findMax(Node node)
  {
    int[] prev = new int[2];
    prev[0] = 0;
    prev[1] = 0;
    if(node == null) return 0;
    helper(node, prev);
    return maxPath;
  }
}

Edit: Forgot to mention that my primary purpose in asking this question is to know if my algorithm was correct rather than ask for a new algorithm.

Edit: I have a reason to believe that my algorithm should also have worked.

I was scouring the internet for similar questions and came across this question: https://leetcode.com/problems/house-robber/?tab=Description

It is pretty similar to the problem above except that it is now an array instead of the tree.

The formal F(X) = Max(F(X-1), a[x] + F(X-2)) works in this case.

Here is my accepted code:

public class Solution {
    public int rob(int[] nums) {

        int[] dp = new int[nums.length];
        if(nums.length < 1) return 0;
        dp[0] = nums[0];
        if(nums.length < 2) return nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for(int i = 2; i < nums.length; i++)
        {
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
        }
        return dp[nums.length-1];

    }
}

Answer 1

The natural solution would be to compute for each node X two values: max path from X to leaf including X and max path from X to leaf, excluding X, let's call them MaxPath(X) and MaxExcluded(X).

For leaf L MaxPath(L) is Value(L) and MaxExcluded(L) is 0.

For internal node X:

MaxPath(X) = Value(X) + Max over child Y of: MaxExcluded(Y)
MaxExcluded(X) = Max over child Y of : Max(MaxExcluded(Y), MaxPath(Y))

The first line means that if you include X, you have to exclude its children. The second means that if you exclude X, you are free to either include or exclude its children.

It's a simple recursive function on nodes which can be computed going leaves-to-parents in O(size of the tree).

Edit: The recursive relation does also work top-down, and in this case you can indeed eliminate storing two values by the observation that MaxExcluded(Y) is actually MaxPath(Parent(Y)), which gives the solution given in the question.

Answer 2

Implementation of what @RafałDowgird explained.

/*                         5
 *              8                   10
 *          1       3         7           9
 *        4   5   6   11  13     14    3      4
 * 
 * 
 */




public class app1 {

public static void main(String[] args) {
    Node root = new Node(5);
    root.left = new Node(8);root.right = new Node(10);
    root.left.left = new Node(1);root.left.right = new Node(3);
    root.right.left = new Node(7);root.right.right = new Node(9);
    root.left.left.left = new Node(4);root.left.left.right = new Node(5);
    root.left.right.left = new Node(6);root.left.right.right = new Node(11);
    root.right.left.left = new Node(13);root.right.left.right = new Node(14);
    root.right.right.right = new Node(4);
    System.out.println(findMaxPath(root));

}

private static int findMaxPath(Node root) {


    if (root == null) return 0;

    int maxInclude = root.data +  findMaxPathExcluded(root);
    int maxExcludeLeft = Math.max(findMaxPath(root.left), findMaxPathExcluded(root.left));
    int maxExcludeRight = Math.max(findMaxPath(root.right), findMaxPathExcluded(root.right));
    return Math.max(maxInclude, Math.max(maxExcludeLeft, maxExcludeRight));
}

private static int findMaxPathExcluded(Node root) {

    if(root == null) return 0;
    int left1 = root.left!=null ? findMaxPath(root.left.left) : 0;
    int right1 = root.left!=null ? findMaxPath(root.left.right) : 0;
    int left2 = root.right!=null ? findMaxPath(root.right.left) : 0;
    int right2 = root.right!=null ? findMaxPath(root.right.right) : 0;

    return Math.max(left1, Math.max(right1, Math.max(left2, right2)));
 }

}
class Node{
  int data;
  Node left;
  Node right;
  Node(int data){
    this.data=data;
  }
}