DSA Visualizations | Hello Interview

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 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.


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:


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:

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 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(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.

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.

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.

Next: Validate Binary Search Tree

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

Sort By

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Path Sum

Validate Binary Search Tree

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".

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

DESCRIPTION (credit Leetcode.com)

Example Input:

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

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?

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

Extra Step: Determining if a Node is "Good"

Here's what the helper function looks like:

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.


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

Summary

Global Variables

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 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

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.val
            result.append(root)
        
        left = dfs(root.left, max_)
        right = dfs(root.right, max_)           
        return result + left + right

    return len(dfs(root, -float('inf')))

Alternative Approach 2

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'), [])

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.

Next: Validate Binary Search Tree

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

Sort By

Loading comments...

BlogBehavioral Interview Examples Interviewing for Experienced SWEs All Blog Posts

Compare UsCompare to Interviewing.io

LinksFAQ Schedule Mock Interviews Pricing Become a Coach Our Coaches Learn System Design Learn DSA Guided Practice Hello Interview Premium

LegalTerms and Conditions Privacy Policy

Contactsupport@hellointerview.com7511 Greenwood Ave North
Unit #4238 Seattle, WA 98103