CareerCup

There must be something wrong with the way the problem is stated or this is a trick problem. We are asked to find the largest subtree, a tree can be thought of is a subtree of itself. Hence if there are two duplicate subtrees of the input tree the function will return the tree itself otherwise it should return null.

If there are at least two leaf nodes that are identical we can be assured that there is at least two duplicate sub trees made out of just those two leaf nodes.

Hence the problem is reduced to finding two identical leaf nodes in the tree

import java.util.*;
static class Node
{
public int val;
public Node left,right;
}
public static boolean findDuplicateNodes(HashSet<Integer> vals,Node n)
{
	if(n==null)
		return false;
	if(vals.contains(n.val))
	{
		return true;
	}
	vals.add(n.val);
	if(findDuplicateNodes(vals,n.left))
		return true;
	if(findDuplicateNodes(vals,n.right))
		return true;
	return false;
}

Could you clarify please?
We need to find a vertex with both left and right subtrees being identical such that subtree size is maximum?
Or we need to to find the largest subtree that repeats two/three times?

Node resultNode;
  private void postOrder(Node root, StringBuffer result)
  {
      if(root!=null)
          {
          StringBuffer leftBuf = new StringBuffer();
          StringBuffer rightBuf = new StringBuffer();
          
          postOrder(root.left,leftBuf);
          postOrder(root.right,rightBuf);
          
          if(leftBuf.equals(rightBuf))
              {
              // we got it, continue to see if there is bigger result. it will be overwritten by higher level node. 
              resultNode = root;
          }
          result.append(leftBuf);
          result.append(rightBuf);
          
          result.append(root.val);
      }

}

Node resultNode;
  private void postOrder(Node root, StringBuffer result)
  {
      if(root!=null)
          {
          StringBuffer leftBuf = new StringBuffer();
          StringBuffer rightBuf = new StringBuffer();
          
          postOrder(root.left,leftBuf);
          postOrder(root.right,rightBuf);
          
          if(leftBuf.equals(rightBuf))
              {
              // we got it, continue to see if there is bigger result. it will be overwritten by higher level node. 
              resultNode = root;
          }
          result.append(leftBuf);
          result.append(rightBuf);
          
          result.append(root.val);
      }

}

In-Order traversal, compare subtree from left and right, when Max subtree size found return max. Repeat for each subtree and compare with global max found.

public static void main(String[] args) {
		
		/*
		 *      4
		 *     / \
		 *    2   2
		 *   / \  /\
		 *   1 3 1  3
		 */

		Node n2a = new Node(1, null, null);
		Node n2b = new Node(3, null, null);
		Node n2c = new Node(1, null, null);
		Node n2d = new Node(3, null, null);
		
		Node n1a = new Node(2, n2a, n2b);
		Node n1b = new Node(2, n2c, n2d);
		
		Node n0 = new Node(4, n1a, n1b);
		
		System.out.println(maxDuplicateSubtree(n0, new StringBuilder(), 0));		
                // output - 3
	}  

	public static int maxDuplicateSubtree(Node root, StringBuilder path, int maxSubtree) {
		if (root == null) {
			return 0;
		}
		StringBuilder leftPath = new StringBuilder();
        StringBuilder rightPath = new StringBuilder();
        int max = 0;
		int maxLeft = maxDuplicateSubtree(root.left, leftPath, maxSubtree);

		path.append(leftPath).append(root.v);
		
		int maxRight = maxDuplicateSubtree(root.right, rightPath, maxSubtree);
		max = Math.max(maxLeft, maxRight);
		
		path.append(rightPath);

		if (leftPath.toString().equals(rightPath.toString())) {
			max = Math.max(leftPath.length(), max);
		}		
		maxSubtree = Math.max(max, maxSubtree);
		
		return maxSubtree;
}

Humm something like this came to mind first. This is pretty bad since its n^2, I also figured a linear time solution based on hashing but it might be a pain if we wanted to avoid hash collisions.

struct node {
	node * left;
	node * right;
	node() {
		left = nullptr;
		right = nullptr;
	}
};

string getDesc(node * n, map<string, int> & m, map<node*, int> & cnts, node ** best) {
	string ans;
	if (n->left != nullptr) {
		ans += "L" + getDesc(n->left);
	}
	if (n->right != nullptr) {
		ans += "R" + getDesc(n->right);
	}
	int cnt = 0;
	for (auto c : ans) {
		if (c == 'R' || c == 'L') {
			cnt++;
		}
	}
	cnts[n] = cnt;
	m[ans]++;
	if (best == nullptr || (cnts[*best] < cnt && m[ans] >= 2)) {
		*best = n;
	}
	ans += "B";
	return ans;
}

node * best;
best = nullptr;
map<string, int> m;
map<node*, int> cnts;

getDesc(root, m, cnts, &best);

Note: not an answer, I'm asking again for clarification, but couldn't comment for some reason :(
So basically a smarter version of the following brute-force pseudocode is required?

def size(node): return 0 if node is None else 1 + size(node.left) + size(node.right)
def compare(a, b): return a is None and b is None or a is not None and b is not None and  compare(a.left, b.left) and compare(a.right, b.right)
def find_max(node):
    if node is None or compare(node.left, node.right):
        return size(node), node
    return max(find_max(node.left), find_max(node.right))

I think this can be solved by representing the 2 trees as an array and solving the problem of the longest common subsequence.

1. Find the size of leftTree
2. Find the size of rightTree

if leftTree is < (half the size of right Tree)
then answer is in rightTree - return results from right tree
else
answer is in leftTree + node + rightTree

Same condition applies for rightTree < (half the nodes of leftTree)

It should be O(nlogn) solution if I calculate correctly.
isEqual method runs in O(n) because O(n) = 2O(n/2) + c
getMaxStubTree runs in O(nlogn) because O(n) = 2O(n/2) + O(n)

public class Solution {

    public static void main(String [] args) {

        Node node6 = new Node(6);
        Node node5 = new Node(5);
        Node node7 = new Node(7);
        Node node4a = new Node(4);
        Node node4b = new Node(4);
        Node node3a = new Node(3);
        Node node3b = new Node(3);
        Node node3c = new Node(3);
        Node node3d = new Node(3);
        Node node1a = new Node(1);
        Node node2a = new Node(2);
        Node node1b = new Node(1);
        Node node2b = new Node(2);

        node6.left = node5;
        node6.right = node7;
        node5.left = node4a;
        node5.right = node4b;
        node4a.left = node3a;
        node4a.right = node3b;
        node4b.left = node3c;
        node4b.right = node3d;
        node3a.left = node1a;
        node3a.right = node2a;
        node3b.left = node1b;
        node3b.right = node2b;

        System.out.println(isEqual(node3a, node3b));

        System.out.println(isEqual(node3c, node3d));

        System.out.println(isEqual(node5, node7));

        getMaxSubtree(node6).ifPresent(System.out::println);
    }

    public static Optional<Result> getMaxSubtree(Node node) {

        if (node == null) {
            return Optional.empty();
        }

        int isEqual = isEqual(node.left, node.right);

        if (isEqual >= 0) {
            return Optional.of(new Result(node, isEqual+1));
        }

        Optional<Result> leftOptional = getMaxSubtree(node.left);
        Optional<Result> rightOptional = getMaxSubtree(node.right);

        if (leftOptional.isPresent() && rightOptional.isPresent()) {
            return leftOptional.get().height > rightOptional.get().height ?
                    leftOptional : rightOptional;
        } else if (leftOptional.isPresent() && !rightOptional.isPresent()) {
            return leftOptional;
        } else if (!leftOptional.isPresent() && rightOptional.isPresent()) {
            return rightOptional;
        } else {
            return Optional.empty();
        }
    }

    /**
     * if node1 == node2 return the height of the tree
     * @param node1
     * @param node2
     * @return
     */
    public static int isEqual(Node node1, Node node2) {
        if (node1 == null && node2 == null) {
            return 0;
        }

        if (node1 == null && node2 != null) {
            return -1;
        }

        if (node2 == null && node1 != null) {
            return -1;
        }

        if (node1.value != node2.value) {
            return -1;
        }

        int left = isEqual(node1.left, node2.left);
        int right = isEqual(node1.right, node2.right);

        if (left >= 0 && right >= 0) {
            return Integer.max(left, right) + 1;
        } else {
            return -1;
        }
    }
}

class Result {
    Node node;
    int height;

    public Result(Node node, int height) {
        this.node = node;
        this.height = height;
    }

    @Override
    public String toString() {
        return "Result{" +
                "node=" + node.value +
                ", height=" + height +
                '}';
    }
}

class Node {

    final int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }
}

Make a merkle tree out of it and do a BFS from the root of it looking for a node that has equal hashes for both of its children.

Took a stab: "Calculate the hash of each node's subtree. Store it in a hash table, key is <hash code of entire subtree> and value is List<<node, size of subtree that's has this node as the root>>.
In second phase, find from the hashtable, the node with the largest size subtree and where number of elements in the list > 2"

public class Node
    {
        public Node(int value)
        {
            this.Value = value;
        }

        public Node(int value, int left, int right)
        {
            this.Value = value;
            this.Left = new Node(left);
            this.Right = new Node(right);
        }

        public Node(int value, Node left, Node right)
        {
            this.Value = value;
            this.Left = left;
            this.Right = right;
        }

        public int Value { get; set; }
        public Node Left { get; set; }
        public Node Right { get; set; }

        public override string ToString()
        {
            return string.Format("Value: [{0}] \n, Left: [{1}], Right: [{2}]", this.Value, this.Left, this.Right);
        }

        public static Node FindLargestSubTreeWithDuplicate(Node node)
        {
            if (null == node)
            {
                return null;
            }

            IDictionary<int, IList<NodeWithSize>> hash = new Dictionary<int, IList<NodeWithSize>>();
            int nodeCount = 0;
            PopulateHash(hash, node, out nodeCount);
            return FindLargestDuplicate(hash);
        }

        private static Node FindLargestDuplicate(IDictionary<int, IList<NodeWithSize>> hash)
        {
            int maxSubTreeSize = 0;
            Node result = null;
            foreach (IList<NodeWithSize> matchingSubTrees in hash.Values)
            {
                if (matchingSubTrees == null || matchingSubTrees.Count <= 1)
                {
                    continue;
                }

                // find the one with max height
                foreach (NodeWithSize node in matchingSubTrees)
                {
                    if (node.CountSubtree > maxSubTreeSize)
                    {
                        maxSubTreeSize = node.CountSubtree;
                        result = node.Node;
                    }
                }
            }

            return result;
        }

        private static int PopulateHash(IDictionary<int, IList<NodeWithSize>> hash, Node node, out int nodeCount)
        {
            if (null == node)
            {
                nodeCount = 0;
                return 0;
            }

            int leftCount;
            int rightCount;
            int hashValue = PopulateHash(hash, node.Left, out leftCount) + node.Value.GetHashCode() + PopulateHash(hash, node.Right, out rightCount);
            nodeCount = leftCount + 1 + rightCount;
            NodeWithSize nodeWithSize = new NodeWithSize { Node = node, CountSubtree = nodeCount };
            if (hash.ContainsKey(hashValue))
            {
                hash[hashValue].Add(nodeWithSize);
            }
            else
            {
                hash.Add(hashValue, new List<NodeWithSize>() { nodeWithSize });
            }

            return hashValue;
        }

        private class NodeWithSize
        {
            public Node Node { get; set; }
            public int CountSubtree { get; set; }

            public override string ToString()
            {
                return string.Format(
                    "Size = {3} && Value: [{0}] \n, Left: [{1}], Right: [{2}]", this.Node.Value, this.Node.Left, this.Node.Right, this.CountSubtree);
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Node treeWithDupes = Program.BuildTreeWithDuplicateSubTree();
            Node largestDupe = Node.FindLargestSubTreeWithDuplicate(treeWithDupes);
            Console.WriteLine(largestDupe.ToString());
	}
}