Limited Time Offer:Up to 0% off Hello Interview Premium

⌘K

Tutor

Depth-First Search

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 (inspired by 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	Path	Is Good Node?	Explanation
4	[4]	Yes	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.
2	[4, 2]	No	4 is greater than 2.
1	[4, 2, 1]	No	Both 4 and 2 are greater than 1.
3	[4, 2, 3]	No	4 is greater than 3.
7	[4, 7]	Yes	There are no nodes with a value greater than 7, so it is a "good node".
6	[4, 7, 6]	No	7 is greater than 6.
9	[4, 7, 9]	Yes	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.

Two subtleties are worth calling out here, since they trip people up. Whether a node is good depends on the running max along the path, not on whether its parent is good.

Picture a path like 3 → 1 → 3. The middle 1 isn't good (the root 3 is larger), but max_ never drops, so it's still 3 by the time we reach the leaf. That leaf 3 is good: nothing on the path from the root is larger than it. A node can be good even when the node right above it isn't. And because the check is "greater than or equal to", a node that ties the running max counts as good too.

Here's what the helper function looks like:

Solution

def dfs(root, max_):
    # base case
    if root is None:
        return 0
    count = 0
    if root.val >= max_:
        # good node found, update count and max_
        count += 1
        max_ = root.val
    # recurse and pass down updated max_
    # to the left and right children
    left = dfs(root.left, max_)
    right = dfs(root.right, max_)           
    # return the number of good nodes in the
    # subtree rooted at the current node
    return 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.

Visualization


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

visible nodes in binary tree

0 / 37

In this implementation, notice that the helper function dfs is defined within the body of the main goodNodes function. While not strictly necessary, we recommend this approach as it allows for a cleaner way to use global variables, which we cover below.

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:

Solution


def goodNodes(root):
    nodes = []
    def dfs(root, max_):
        nonlocal nodes
        if root is None:
            return
        
        if root.val >= max_:
            max_ = root.val
            nodes.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.

Since the "global variable" nodes is declared within the body of the main goodNodes function, it's not truly global - only the recursive dfs function has access to it. This is preferred, as it protects the variable from being accidentally modified by code outside of the goodNodes function.

Although something like that most likely won't happen in the context of an interview, it's a good bit of knowledge that you can mention during your interview to demonstrate your understanding of scope.

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:

Solution

def goodNodes(root):
    def dfs(root, max_):
        if root is None:
            return []
        
        result = []
        if root.val >= max_:
            max_ = root.val
            result.append(root)
        
        left = dfs(root.left, max_)
        right = dfs(root.right, max_)           
        return result + left + right
    return 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(n²).

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.

Solution

def goodNodes(root):
    def dfs(root, max_, nodes):
        if root is None:
            return nodes
        
        if root.val >= max_:
            max_ = root.val
            nodes.append(root)
        
        left = dfs(root.left, max_, nodes)
        # need to pass the result from the
        # left to the right subtree
        right = dfs(root.right, max_, left)
        return right
    return 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.

Test Your Knowledge

Complexity Analysis

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

Time Complexity Analysis:

Find the work done per recursive call, and multiply it by N
All examples (aside from the merging lists example) perform constant work per recursive call
Therefore, the time complexity is typically O(N)

Space Complexity Analysis:

The memory that each recursive call occupies on the call stack contributes to space complexity
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), plus any additional space required by each recursive call

Mark as read

Next: Validate Binary Search Tree

Your account is free and you can post anonymously if you choose.

Unlock Premium Coding Content

Interactive algorithm visualizations

Guided Practice

Recent interview questions

Learn More

Reading Progress

On This Page

Global Variables

Depth-First Search

Passing Values Down and Helper Functions

DESCRIPTION (inspired by Leetcode.com)

Summary

Global Variables

Alternative Approach 1

Alternative Approach 2

Test Your Knowledge

Complexity Analysis

Comments

Questions

Learn

Links

Legal

Contact