treediff.java

At DoorDash, menus are updated daily even hourly to keep them up-to-date. Each menu can be regarded as a tree. When the merchant sends us the latest menu, can we calculate
how many nodes have changed/added/deleted?

Assume each Node structure is as below:

class Node {
        String key;
        int value;
        List children;
}

Assume there are no duplicate nodes with the same key.

Output: Return the number of changed nodes in the tree.

Existing tree
               a(1)
            /      
         b(2)      c(3)
        /     \         
      d(4)    e(5)      f(6)

New tree
            a(1)
               
               c(3)
                  
                   f(66)

a(1) a is the key, 1 is the value
For example, there are a total of 4 changed nodes. Node b, Node d, Node e are automatically set to inactive. The value of Node f changed as well.

Existing tree
            a(1)
          /      
        b(2‍‍‌‌‌‍‍‌‌‍‍‍‌‍‍‌‌‍)      c(3)
      /       \      
  d(4)      e(5)      g(7)

New tree
                a(1)
            /         
         b(2)         h(8)
      /    |   \           
e(5)   d(4)   f(6)       g(7)

There are a total of 5 changed nodes. Node f is a newly-added node. c(3) and old g(7) are deactivated and h(8) and g(7) are newly added nodes

followup print out the changes

Comments: 4
BestMost VotesNewest to OldestOldest to Newest
Login to Comment
hologic's avatar
hologic

39
April 14, 2022 8:21 AM

Read More
Old tree: 
                   a(1)
                  /      \
               b(2‍‍‌‌‌‍‍‌‌‍‍‍‌‍‍‌‌‍)       c(3)
              /     \        \
          d(4)      e(5)     f(6)

New tree:
                   a(1)
                  /      \
               b(2‍‍‌‌‌‍‍‌‌‍‍‍‌‍‍‌‌‍)      c(2)
                        /     \
                       g(5)    f(66)
                              /     \
                             k(2)   l(7)

Output:
Value changed for node: C
Extra nodes in the new tree: G
Value changed for node: F
Extra nodes in the new tree: K
Extra nodes in the new tree: L
Missing nodes from old tree: D
Missing nodes from old tree: E


import java.util.*;
public class UpdateNaryTree {
    HashMap<String, Node> map;
    StringBuilder updates;
    public String changedNodes(Node root1, Node root2)
    {
        map = new HashMap<>();
        updates = new StringBuilder();
        dfsToStoreFirstTreeInMap(root1);
        compareTrees(root2);
        if(map.size()>0)
        {
            //missing nodes in new tree
            for(String key : map.keySet())
            {
                updates.append("\n");
                updates.append("Missing nodes from old tree: ");
                updates.append(key);
            }
        }
        return updates.toString();
    }

    private void dfsToStoreFirstTreeInMap(Node root)
    {
        map.put(root.key, root);
        if(root.children == null)
        {
            return; 
        }
        for(Node child : root.children)
        {
            dfsToStoreFirstTreeInMap(child);
        }
    }

    private void compareTrees(Node root)
    {
        if(map.containsKey(root.key))
        {
            Node original = map.get(root.key);
            //check if the value is same to the original node
            if(original.val != root.val)
            {
                updates.append("\n");
                updates.append("Value changed for node: ");
                updates.append(root.key);
            }
            map.remove(root.key);
        }
        else //extra nodes in new tree
        {
            updates.append("\n");
            updates.append("Extra nodes in the new tree: ");
            recursivelyAddAllChildrenToUpdates(root);
            return;
        }
        if(root.children == null)
        {
            return; 
        }
        for(Node child : root.children)
        {
            compareTrees(child);
        }
    }

    private void recursivelyAddAllChildrenToUpdates(Node root)
    {
        updates.append(root.key);
        if(root.children == null)
        {
            return; 
        }
        for(Node child : root.children)
        {
            recursivelyAddAllChildrenToUpdates(child);
        }
    }
}