### Passing Values Down and Helper Functions

In the Return Values section, we covered how return values allow us to solve binary tree problems from the "bottom-up".

In some cases, questions require us to pass information "down" from parents to child nodes, which we do via the parameters of our recursive function. If we need more parameters than the original function signature allows, then we need to introduce a helper function to help us recurse.

Let's look at an example of a question that requires a helper function.

###### DESCRIPTION (credit Leetcode.com)

Given the root node of a binary tree, write a function to find the number of "good nodes" in the tree. A node X in the tree is considered "good" if in the path from the root to the node X, there are no nodes with a value greater than X's value.

**Example**
Input:

Output: 3. The good nodes are highlighted in green (4, 7, 9)

Node 4: The root node is a "good node" since there are no nodes with a value greater than 4 in the path from the root to the node. Node 2: The path from the root to the node is [4, 2], and 4 is greater than 2. Node 1: The path from the root to the node is [4, 2, 1], and both 4 and 2 are greater than 1. Node 3: The path from the root to the node is [4, 2, 3], and 4 is greater than 3.

Node 7: The path from the root to the node is [4, 7], and there are no nodes with a value greater than 7, so it is a "good node". Node 6: The path from the root to the node is [4, 7, 6], and 7 is greater than 6. Node 9: The path from the root to the node is [4, 7, 9], and there are no nodes with a value greater than 9, so it is a "good node".

**Define the Return Value**
If I'm at a node in the tree, what values do I need from my left and right children to calculate the number of good nodes in the subtree rooted at the current node?

I need to know the number of good nodes in my left subtree and the number of good nodes in my right subtree, which tells me that each recursive call should return the number of good nodes in the subtree rooted at the current node.

If I know those two values, then I can return the number of good nodes in my subtree by adding them together, and then adding 1 if the current node is a good node. We'll figure out how to tell if the current node is a good node next, but first let's figure out the base case.

**Base Case**
The number of good nodes in an empty tree is 0.

**Extra Step: Determining if a Node is "Good"**

In order to tell if a root node is "good", we need to know the maximum value of any node on the path starting from the original root of the tree to the current node. Since this is a value that must be passed down from parent nodes to children, we need to introduce a helper function that introduces an extra parameter max_, which represents the maximum value seen so far on the current path from the root.

To check if the current node is a good node, we compare the current node's value to max_. If the current node's value is greater than or equal to max_, then the current node is a good node, and we increment our count by 1.

Here's what the helper function looks like:

def dfs(root, max_):# base caseif root is None:return 0count = 0if root.val >= max_:# good node found, update count and max_count += 1max_ = root.val# recurse and pass down updated max_# to the left and right childrenleft = dfs(root.left, max_)right = dfs(root.right, max_)# return the number of good nodes in the# subtree rooted at the current nodereturn count + left + right

In our main function, we can make the initial call to our helper function with max_ set to -infinity to kick off the recursion.

The animation below visualizes each step of the solution. Pay attention to how the max value seen so far on the current path from the root is passed down from parent to child nodes via the parameter in the helper function.

def goodNodes(root):def dfs(root, max_):if root is None:return 0count = 0if root.val >= max_:count += 1max_ = root.valleft = dfs(root.left, max_)right = dfs(root.right, max_)return left + right + countreturn dfs(root, -float("inf"))

Questions involving **root-to-leaf** paths are common examples of where using helper functions are necessary, as we can use the helper function to introduce extra parameters that store the state of our current path.

#### Summary

Some questions require that nodes have values that are passed down to them via their parents. These values are passed via the parameters of the recursive function. If we need more values than the original function signature allows, then we need to introduce a helper function to help us recurse.

### Global Variables

In some cases, using a global variable that all recursive calls access can simplify the code. Recalling the Good Nodes question from the previous section, Let's say that instead of returning only returning the count of all good nodes, we want to return a list of all good nodes in the tree.

To do so, we can initialize a single list that all recursive calls have access to, and append the current node to that list if it's visible:

def goodNodes(root):nodes = []def dfs(root, max_):nonlocal nodesif root is None:returnif root.val >= max_:max_ = root.valnodes.append(root)dfs(root.left, max_)dfs(root.right, max_)dfs(root, -float('inf'))return nodes

Note that there are no return values in the recursive function. We use depth-first search to traverse each node in the tree, and at each node, we check if the node is visible. If it is, we append it to the global list of visible nodes.

##### Alternative Approach 1

Compare that approach to the following, where each recursive call returns a list of visible nodes in its subtree, and the parent node combines them to return the final list of visible nodes:

def goodNodes(root):def dfs(root, max_):if root is None:return []result = []if root.val >= max_:max_ = root.valresult.append(root)left = dfs(root.left, max_)right = dfs(root.right, max_)return result + left + rightreturn len(dfs(root, -float('inf')))

While this approach avoids a global variable, it has a one major drawback: it requires us to merge lists returned by each subtree at each node into a new list in every call, which adds both time and space complexity. In the worst case, when every node in the tree is visible, we end up copying up to N nodes at each of the N nodes in the tree, resulting in a time complexity of O(n2).

##### Alternative Approach 2

Another alternative approach is to pass a single list of visible nodes as an extra parameter to the recursive function and update it as we recurse. While this is more time and space efficient than merging lists, it is cumbersome and error-prone, as we need to both pass the list down to each recursive call, and correctly return it to the parent node.

def goodNodes(root):def dfs(root, max_, nodes):if root is None:return nodesif root.val >= max_:max_ = root.valnodes.append(root)left = dfs(root.left, max_, nodes)# need to pass the result from the# left to the right subtreeright = dfs(root.right, max_, left)return rightreturn dfs(root, -float('inf'), [])

For these reasons, global variables are preferred whenever we need to collect values in a list as we traverse the binary tree. Global variables are also useful when the return values of each recursive function differs from what the question is asking. We'll cover a few such examples in the practice problems.

### Analyzing Time and Space Complexity

If there a N nodes in a binary tree, then a depth-first search based solution will visit each node exactly once.

**Time Complexity**:
Find the work done per recursive call, and multiply it by N. All of the examples (aside from the merging lists example) perform a constant amount of work per recursive call, so the time complexity is O(N).

**Space Complexity**:
The memory that each recursive call occupies on the call stack is part of the space complexity of a problem. In depth-first search problems, a recursive call is made for each node in the tree, so the space complexity is at least O(N). This is in addition to the amout of space required for each recursive call itself, which differs from problem to problem.

Loading comments...