title: Recurrence relation and time complexity of finding next larger in Generic tree
body: <p><strong>Question:</strong> Given a generic tree and an integer n. Find and return the node with next larger element in the tree i.e. find a node with value just greater than n.</p>
  <p>Although i was able to solve it is O(n) by removing the later for loop and doing comparisons while calling recursion. I am bit curious about time complexity of following version of code.</p>
  <p>I came up with recurrence relation as T(n) = T(n-1) + (n-1) = O(n^2). Where T(n-1) is for time taken by children and + (n-1) for finding the next larger (second for loop). Have i done it right? or am i missing something?</p>
  <pre><code>def nextLargestHelper(root, n):
  &quot;&quot;&quot;
  root =&gt; reference to root node
  n =&gt; integer
  Returns node and value of node which is just larger not first larger than n.
  &quot;&quot;&quot;
  # Special case
  if root is None:
      return None, None
  # list to store all values &gt; n
  largers = list()
  # Induction step
  if root.data &gt; n:
      largers.append([root, root.data])
  # Induction step and Base case; if no children do not call recursion
  for child in root.children:
      # Induction hypothesis; my function returns me node and value just larger than 'n'
      node, value = nextLargestHelper(child, n)
      # If larger found in subtree
      if node:
          largers.append([node, value])
  # Initialize node to none, and value as +infinity
  node = None
  value = sys.maxsize
  # travers through all larger values and return the smallest value greater than n
  for item in largers: # structure if item is [Node, value]
      # this is why value is initialized to +infinity; so as it is true for first time
      if item[1] &lt; value:
          node = item[0]
          value = item[1]
  return node, value
  </code></pre>