title: Root to leaf path with maximum distinct nodes
body: <p>I was recently looking over the following problem <a href="https://www.geeksforgeeks.org/root-leaf-path-maximum-distinct-nodes/" rel="nofollow noreferrer">here</a>. Basically, you are given a binary tree and need to find the path with the highest number of distinct values. The link above encourages using a hash, but I am unsure how a hash would help in this case. In the article the following is stated:</p>
  
  <blockquote>
    <p>A simple solution is to explore all root to leaf paths. In every root
    to leaf path, count distinct nodes and finally return the maximum
    count.</p>
    
    <p>An efficient solution is to use hashing. We recursively traverse the
    tree and maintain count of distinct nodes on path from root to current
    node. We recur for left and right subtrees and finally return maximum
    of two values.</p>
  </blockquote>
  
  <p>I am not sure how a hash approach works better in this case (it's hard for me to see since I don't know c++). Can anyone help me translate the hashing approach to python? I have a setup a tree here:</p>
  
  <pre><code>class TreeNode(object):
      def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None
  
  
  root = TreeNode('A')
  
  second = TreeNode('Z')
  root.left = second
  
  third = TreeNode('D')
  second.left = third
  
  fourth = TreeNode('A')
  third.left = fourth
  
  tenth = TreeNode('A')
  third.right = tenth
  
  fifth = TreeNode('A')
  root.right = fifth
  
  sixth = TreeNode('U')
  fifth.left = sixth
  
  seventh = TreeNode('Z')
  fifth.right = seventh
  
  eighth = TreeNode('Y')
  seventh.right = eighth
  
  nineth = TreeNode('B')
  seventh.right = nineth
  </code></pre>
  
  <p>Which looks like </p>
  
  <pre><code>        A
         / \
        Z   A
       /   / \
      D   U   Z
     / \       \
    A   A       Y
  </code></pre>
  
  <p>Any help is appreciated. Thanks.</p>