Embark on a journey through the fascinating world of trees and graphs in this enlightening post. Discover three essential algorithms that will empower you to traverse, analyze, and manipulate tree and graph structures effectively. Strengthen your knowledge of data structure and algorithms with this invaluable resource.

This post focuses on graph and tree data structures and demonstrates various operations that can be performed on them using Python. Graphs and trees are essential for modeling and solving a wide range of real-world problems. This notebook covers the basics of graphs and trees, including their representation, traversal, and common algorithms associated with them. You can run this post in Google Colab using this link:

Graph: A graph is a collection of vertices (nodes) and edges connecting the vertices. Graphs can be directed or undirected, weighted or unweighted, and can have cycles. In graphs, there is no hierarchy, and nodes can have multiple edges connecting them to other nodes.

Tree: A tree is a data structure in computer science consisting of nodes connected by edges. It is a type of graph but with the restriction that it has a hierarchical structure, meaning that there is a root node with child nodes, each of which may have their own child nodes, and so on. The edges represent the parent-child relationships between the nodes.

Graph vs. Tree: The main difference between a tree and a graph is that a tree has a hierarchical structure with a root node and child nodes, while a graph can have any arrangement of nodes and edges. A search tree is a specific type of tree data structure used for searching and traversing elements, while a graph can be used for many different purposes.

Search Tree: A search tree is a specific type of tree data structure used for searching and traversing elements. In a search tree, the arrangement of nodes is based on some specific rules, such as the values of the elements being stored. The nodes are arranged in a way that allows for efficient searching and traversing of elements. Some examples of search trees include binary search trees, AVL trees, and others.

The most common type of search tree is the binary search tree, where each node has at most two children. The elements in a binary search tree are ordered in such a way that for each node, all elements in the left subtree are smaller than the node, and all elements in the right subtree are greater than the node.

The basic properties of search trees include:

• Search time: Search trees allow for efficient searching of elements, with an average time complexity of O(log n), where n is the number of nodes in the tree.
• Space complexity: Search trees require less memory compared to other data structures like arrays or linked lists, as they store elements in a hierarchical manner.
• Insertion and deletion: Search trees allow for efficient insertion and deletion of elements, with an average time complexity of O(log n).
• Ordering: Search trees maintain the order of elements, making it possible to traverse the elements in sorted order.
• Balancing: Some search trees, such as AVL trees and red-black trees, are self-balancing, meaning they maintain a balance in the tree even after multiple insertions and deletions. This ensures that the search tree remains efficient even with large numbers of elements.

These properties make search trees a useful data structure for various applications, such as database indexing, computer graphics, and algorithms for sorting and searching elements.

Note: “Search tree” and “binary search tree” are often used interchangeably to refer to the same type of data structure.

1. DFS/BFS Traversals

DFS (Depth-First Search) and BFS (Breadth-First Search) are algorithms for traversing and searching a graph or tree data structure.

DFS is a recursive algorithm that starts at the root node and explores as far as possible along each branch before backtracking. The algorithm visits all the vertices of a graph or all the nodes of a tree by going deep into the structure before backtracking.

BFS, on the other hand, is an iterative algorithm that visits all the vertices of a graph or all the nodes of a tree in a breadth-wise manner. It visits all the vertices at the same level before moving on to the vertices at the next level. BFS uses a queue to keep track of the vertices to be visited next.

                 1
               /   \
              2     3
            /   \
          4      5

1. Depth First Search (DFS) Traversals:
2. Inorder (Left, Root, Right) : 4 2 5 1 3
3. Preorder (Root, Left, Right) : 1 2 4 5 3
4. Postorder (Left, Right, Root) : 4 5 2 3 1
5. Breadth-First Search (BFS) or Level Order Traversal: 1 2 3 4 5

Time and space complexity:

• DFS: The space complexity of the function is O(h), where h is the height of the binary tree. This is because the function uses a recursive approach to traverse the binary tree, and at each recursion, a new function call is added to the call stack. The maximum number of function calls in the call stack would be equal to the height of the binary tree, so the space complexity is O(h). In the worst case, when the binary tree is a skewed tree, the height of the tree would be equal to the number of nodes in the tree, so the space complexity would be O(n). The time complexity is technically O(V + E) where V is vortex and E is edge, but that equates to O(n + (n-1)) = O(n) in binary search tree. This is because all trees have n - 1 edges, n being the number of nodes

• BFS: The space complexity of the BFS algorithm for a tree is also O(n), because in the worst case, all the nodes in the tree need to be stored in a queue to be processed in order. The size of the queue can grow up to n nodes, so the space complexity is O(n).

Let’s first create a class of tree to test algorithms:

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

class Tree:
    def __init__(self, root=None):
        self.root = root

The TreeNode class represents a node in a tree data structure. It has three instance variables: value, left, and right. value represents the value stored in the node, left is a reference to the left child node, and right is a reference to the right child node. The __init__ method is a constructor that is called when a new TreeNode object is created. The __init__ method takes in three arguments: value, left, and right. It sets the instance variables value, left, and right to the corresponding arguments. If left or right is not passed as an argument, it defaults to None.

The Tree class represents a tree data structure. It has one instance variable: root. root is a reference to the root node of the tree. The __init__ method is a constructor that is called when a new Tree object is created. The __init__ method takes in one argument: root. It sets the instance variable root to the corresponding argument. If root is not passed as an argument, it defaults to None.

Let’s create the above tree:

tree = Tree(TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3)))

1.1. Algorithms for Binary Tree

DFS: In-order

def in_order_traverse(tree, array):
    if tree is not None:
        in_order_traverse(tree.left, array)
        array.append(tree.value)
        in_order_traverse(tree.right, array)

    return array

Explanation:

The function uses a recursive approach to traverse the binary tree in-order. An in-order traversal of a binary tree visits the left subtree, then the current node, and then the right subtree. If the current node (tree) is not None, the following steps are performed:

1. The function calls itself recursively on the left child node of the current node (in_order_traverse(tree.left, array)).
2. The value of the current node (tree.value) is appended to the array list.
3. The function calls itself recursively on the right child node of the current node (in_order_traverse(tree.right, array)).

When the function returns from visiting all the nodes in the left and right subtrees, it returns array, which will contain the values of the nodes in the binary tree in the in-order order.

Test:

in_order_traverse(tree.root, [])

[4, 2, 5, 1, 3]

DFS: Pre-order

def pre_order_traverse(tree, array):
    if tree is not None:
        array.append(tree.value)
        pre_order_traverse(tree.left, array)
        pre_order_traverse(tree.right, array)

    return array

Explanation:

The function uses a recursive approach to traverse the tree. If the current node (tree) is not None, the following steps are performed:

1. The value of the current node (tree.value) is appended to the array list.
2. The function calls itself recursively on the left child node of the current node (pre_order_traverse(tree.left, array)).
3. The function calls itself recursively on the right child node of the current node (pre_order_traverse(tree.right, array)).

When the function returns from visiting all the nodes in the left and right subtrees, it returns array, which will contain the values of the nodes in the binary tree in the in-order order.

Test:

pre_order_traverse(tree.root, [])

[1, 2, 4, 5, 3]

DFS: Post-order

def post_order_traverse(tree, array):
    if tree is not None:
        post_order_traverse(tree.left, array)
        post_order_traverse(tree.right, array)
        array.append(tree.value)

    return array

Explanation:

The function uses a recursive approach to traverse the tree. If the current node (tree) is not None, the following steps are performed:

1. The function calls itself recursively on the left child node of the current node (post_order_traverse(tree.left, array)).
2. The function calls itself recursively on the right child node of the current node (post_order_traverse(tree.right, array)).
3. The value of the current node (tree.value) is appended to the array list.

When the function returns from visiting all the nodes in the left and right subtrees, it returns array, which will contain the values of the nodes in the binary tree in the in-order order.

Test:

post_order_traverse(tree.root, [])

[4, 5, 2, 3, 1]

BFS

def bfs(tree, array):
      queue = [tree]
      array = []

      while len(queue) > 0:
          current = queue.pop(0)
          array.append(current.value)

          if current.left:
            queue.append(current.left)
          if current.right:
            queue.append(current.right)
      return array

Explanation:

The algorithm starts by initializing an empty queue and an array, and adding the root node of the tree to the queue. Then, it enters a while loop that continues as long as there are nodes in the queue.

In each iteration of the while loop, the first node in the queue (the node at the front of the queue) is removed and its value is appended to the array. If the current node has a left child, it is added to the end of the queue. Similarly, if the current node has a right child, it is also added to the end of the queue.

Once all nodes have been processed, the final array that contains the values of the nodes in breadth-first order is returned.

Test:

bfs(tree.root, [])

[1, 2, 3, 4, 5]

1.2. Algorithms for N-array Tree

def pre_order_traverse_n_arr(tree, array):
    if tree is not None:
      for child in tree.children:
        array.append(child.value)
        pre_order_traverse_n_arr(child, array)
    return array

#------------------------------------------------------
def post_order_traverse_n_arr(tree, array):
    if tree is not None:
      for child in tree.children:
        post_order_traverse_n_arr(child, array)
        array.append(child.value)
    return array

#------------------------------------------------------
def bfs_n_arr(tree, array):
      queue = [tree.value]
      array = []

      while len(queue) > 0:
          current = queue.pop(0)
          array.append(current.name)

          for child in current.children:
              queue.append(child)
      return array

Explanation:

The main difference is that instead of checking left and right, it checks all of child of children. If the given tree node is not None, the function iterates through its children and appends the value of each child node to the array.

1.3. Algorithms for Graph

The time complexity of the DFS algorithm in a graph is O(V + E), where V is the number of vertices and E is the number of edges. This is because the algorithm visits every vertex and edge once.

The space complexity of the DFS algorithm is O(V), where V is the number of vertices. This is because the algorithm uses a stack to keep track of the vertices that need to be visited, and the maximum size of the stack is equal to the number of vertices.

The time complexity of the BFS algorithm in a graph is O(V + E), where V is the number of vertices and E is the number of edges. This is because the algorithm visits every vertex and edge once.

The space complexity of the BFS algorithm is O(V), where V is the number of vertices. This is because the algorithm uses a queue to keep track of the vertices that need to be visited, and the maximum size of the queue is equal to the number of vertices.

DFS

def dfs(graph, node, visited):
    if node not in visited:
        visited.append(node)
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)
    return visited

Explanation:

• If the current node has not been visited, it is added to the visited list.
• The algorithm then iterates over the neighbors of the current node and calls the function recursively on each neighbor.
• This process continues until all nodes connected to the starting node have been visited.
• Finally, the visited list is returned, which represents the nodes visited in a DFS order.

Test:

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
visited_dfs = dfs(graph, 'A', [])
print(visited_dfs)

['A', 'B', 'D', 'E', 'F', 'C']

BFS

def bfs(graph, start_node):
    visited = []
    queue = [start_node]
    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            neighbors = graph[node]
            for neighbor in neighbors:
                queue.append(neighbor)
    return visited

Explanation:

The algorithm starts with a given start_node, adds it to an initially empty queue, and adds it to the visited list to mark it as visited.

In each iteration of the while loop, it takes the first node from the queue, adds its unvisited neighbors to the end of the queue and marks the node as visited by adding it to the visited list.

The algorithm terminates when the queue is empty, and returns the visited list, which contains all the nodes visited in the order they were visited using the BFS algorithm.

Test:

visited_bfs = bfs(graph, 'A')
print(visited_bfs)

['A', 'B', 'C', 'D', 'E', 'F']

Note that the above code traverses only the vertices reachable from a given source vertex. In every situation, all the vertices may not be reachable from a given vertex (i.e. for a disconnected graph).

We can modify the BFS function to do traversal starting from all nodes one by one

def bfs_disconnected_graph(graph):
    visited = []
    for node in graph:
        if node not in visited:
            queue = [node]
            while queue:
                curr_node = queue.pop(0)
                if curr_node not in visited:
                    visited.append(curr_node)
                    for neighbor in graph[curr_node]:
                        queue.append(neighbor)
    return visited

disconnected_graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
    'G' : ['H'],
    'H' : ['G']
}

visited_bfs = bfs(graph, 'A')
print("Old function: ", visited_bfs)

visited_dfs = bfs_disconnected_graph(disconnected_graph)
print("Modified function function: ", visited_dfs)

Old function:  ['A', 'B', 'C', 'D', 'E', 'F']
Modified function function:  ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']

So old function cannot handle G – H connection.

2. Maximum Path Sum in a Binary Tree

Maximum Path Sum in a Binary Tree is a problem in computer science that involves finding the maximum sum of values that can be obtained by traversing a path in a binary tree. In this problem, a path is defined as a sequence of connected nodes in a tree, and the sum of the path is the sum of the values of the nodes in the path.

# Definition of a binary tree node
class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

# Function to find the maximum path sum in a binary tree
def max_path_sum(tree):
    _, max_sum = find_max_sum(tree)
    return max_sum

# Helper function to recursively find the maximum path sum
def find_max_sum(tree):
    if tree is None:
        return (0, float("-inf"))

    left_max_sum_as_branch, left_max_path_sum = find_max_sum(tree.left)
    right_max_sum_as_branch, right_max_path_sum = find_max_sum(tree.right)

    max_child_sum_as_branch = max(left_max_sum_as_branch, right_max_sum_as_branch)
    max_sum_as_branch = max(max_child_sum_as_branch + tree.value, tree.value)
    max_sum_as_root_node = max(left_max_sum_as_branch + tree.value + right_max_sum_as_branch, max_sum_as_branch)
    max_path_sum = max(left_max_path_sum, right_max_path_sum, max_sum_as_root_node)

    return (max_sum_as_branch, max_path_sum)

Explanation:

The find_max_sum function is a recursive helper function that helps to find the maximum path sum of a binary tree. It takes a binary tree node as its input and returns a tuple of two values: the maximum sum that can be achieved by a path that ends at the given node, and the maximum sum that can be achieved by any path in the subtree rooted at the given node.

The function first checks if the given node is None. If it is, it returns a tuple of (0, negative infinity) which indicates that the maximum sum is zero since there are no nodes to include in the path and negative infinity as the maximum sum is initially unknown.

If the node is not None, it calls the find_max_sum function recursively on the left and right subtrees of the node. The returned values represent the maximum sum that can be achieved by a path that ends at the left and right child nodes respectively, as well as the maximum sum that can be achieved in the left and right subtrees.

The function then calculates the maximum sum that can be achieved by a path that ends at the current node. This can be done by finding the maximum sum that can be achieved by a path that ends at the left or right child node, and adding the value of the current node to it. If the sum is negative, then the current node is not included in the path, so the sum is just the value of the current node.

Next, the maximum sum that can be achieved by any path that includes the current node as the root is calculated. This can be done by adding the maximum sum that can be achieved by a path that ends at the left child node, the value of the current node, and the maximum sum that can be achieved by a path that ends at the right child node. This value is then compared to the maximum sum that can be achieved by a path in the left or right subtrees, as well as the previously calculated maximum sum that can be achieved by a path that ends at the current node.

Finally, the function returns a tuple of the maximum sum that can be achieved by a path that ends at the current node, and the maximum sum that can be achieved by any path in the subtree rooted at the current node.

Space and time complexity The time complexity of the find_max_sum function is O(n), where n is the total number of nodes in the binary tree. This is because the function traverses each node in the tree exactly once.

The space complexity of the function is O(log(n)), where n is the total number of nodes in the binary tree. This is because the function uses the call stack to keep track of the recursive calls made to traverse the left and right sub-trees of the binary tree. The maximum depth of the call stack is the height of the binary tree, which is log(n) for a balanced binary tree.

Test:

# Test function to validate the implementation
def test_max_path_sum():
    # Test Case 1
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    assert max_path_sum(root) == 6

    # Test Case 2
    root = TreeNode(-10)
    root.left = TreeNode(9)
    root.right = TreeNode(20)
    root.right.left = TreeNode(15)
    root.right.right = TreeNode(7)
    assert max_path_sum(root) == 42

    # Test Case 3
    root = TreeNode(-3)
    assert max_path_sum(root) == -3

    print("All test cases passed.")

test_max_path_sum()

All test cases passed.

3. Check if a given array can represent Preorder Traversal of Binary Search Tree

def can_represent_preorder(preorder):
    stack = []
    root = float('-inf')

    for val in preorder:
        if val < root:
            return False

        while stack and stack[-1] < val:
            root = stack.pop()

        stack.append(val)

    return True

Explanation:

To check if a given array can represent the preorder traversal of a binary search tree, we can follow these steps:

1. Initialize an empty stack and set the root to be the minimum possible value.
2. Iterate through each element of the array.
3. If the current element is less than the stack’s top element, return False as it violates the BST property.
4. If the current element is greater than the stack’s top element, remove all the elements from the stack that are less than the current element and set the last removed element as the parent node of the current element.
5. Push the current element onto the stack.
6. If we reach the end of the array, return True.

Space and time complexity The time complexity of this algorithm is O(n), where n is the length of the preorder array, since we iterate through each element once. The space complexity is O(n) as well since the stack can store at most n elements.

4. Check whether a binary tree is a full binary tree or not

A full binary tree is a binary tree in which every node has either 0 or 2 children. To check whether a binary tree is a full binary tree, we can perform a traversal and check if each node has either 0 or 2 children.

class Node:
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_full_binary_tree(root):
    if not root:
        return True

    # If the node is a leaf node, it is a full binary tree
    if not root.left and not root.right:
        return True

    # If the node has both left and right children, recursively check the left and right subtrees
    if root.left and root.right:
        return is_full_binary_tree(root.left) and is_full_binary_tree(root.right)

    # If the node has only one child, it is not a full binary tree
    return False

Explanation:

The function checks if the root node is None, in which case it returns True because an empty tree is considered a full binary tree. If the root node has no children, the function returns True. If the root node has only one child, the function returns False because a full binary tree must have either no children or two children for every node.

If the root node has two children, the function recursively calls itself on both children to check if they are also full binary trees. If both children are full binary trees, the function returns True, otherwise it returns False.

Space and time complexity The time complexity of this function is O(n), where n is the number of nodes in the tree, because it needs to check every node in the tree to determine if it is a full binary tree. The space complexity of this function is O(h), where h is the height of the tree, because it uses recursive calls to check if the left and right subtrees are full binary trees.

Test:

# Create a full binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

print(is_full_binary_tree(root))  # Output: True

# Create a binary tree that is not full
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)

print(is_full_binary_tree(root))  # Output: False

True
False

5. Bottom and top View of a Binary Tree

• Bottum view

                  20
                /    \
              8       22
            /   \      \
          5      3      25
                / \
              10    14
  

For the above tree, the output should be 5, 10, 3, 14, 25.

• Top view

                  20
                /    \
              8       22
            /   \      \
          5      3      25
                / \
              10    14
  

Top view of the above binary tree is 5 8 20 22 25

def top_view(root, map, dist, level):

    # Base case
    if root is None:
        return

    # If current level is more than or equal
    # to maximum level seen so far for the
    # same horizontal distance or horizontal
    # distance is seen for the first time,
    # update the dictionary
    if dist in map:
        if map[dist][1] > level:
            map[dist] = [root.val, level]
    else:
        map[dist] = [root.val, level]

    # recur for left subtree by decreasing
    # horizontal distance and increasing
    # level by 1
    top_view(root.left, map, dist - 1, level + 1)

    # recur for right subtree by increasing
    # horizontal distance and increasing
    # level by 1
    top_view(root.right, map, dist + 1, level + 1)


def bottom_view(root, map, dist, level):

    # Base case
    if root is None:
        return

    # If current level is lwess than or equal
    # to maximum level seen so far for the
    # same horizontal distance or horizontal
    # distance is seen for the first time,
    # update the dictionary
    if dist in map:
        if map[dist][1] < level:
            map[dist] = [root.val, level]
    else:
        map[dist] = [root.val, level]

    # recur for left subtree by decreasing
    # horizontal distance and increasing
    # level by 1
    bottom_view(root.left, map, dist - 1, level + 1)

    # recur for right subtree by increasing
    # horizontal distance and increasing
    # level by 1
    bottom_view(root.right, map, dist + 1, level + 1)

Explanation:

The top_view function recursively traverses the binary tree and maintains a dictionary map which stores the values and levels of the nodes in the top view. The dist parameter is the horizontal distance of the current node from the root node, and the level parameter is the current level of the node in the tree.

The function first checks if the dist value is already present in the map dictionary. If it is, then it checks if the level of the current node is less than the level of the node already present in the map dictionary for the same dist. If it is less, then the current node is more towards the top view of the tree, so it replaces the existing node in the map dictionary with the current node.

If the dist value is not present in the map dictionary, then the current node is the first node seen at this horizontal distance. So, it adds the current node to the map dictionary.

The bottom_view function is similar to the top_view function, but it maintains a dictionary map for the bottom view of the binary tree. Here, the function checks if the level value of the current node is greater than the level of the node already present in the map dictionary for the same dist. If it is greater, then the current node is more towards the bottom view of the tree, so it replaces the existing node in the map dictionary with the current node.

Now we can write a function to print these views:

def print_top_bottom_view(root):

    map_top = {}
    top_view(root, map_top, 0, 0)

    print('Top View \n')
    for i in sorted(map_top.keys()):
        print(map_top[i][0], end = " ")

    map_bottom = {}
    bottom_view(root, map_bottom, 0, 0)

    print('\n')
    print('Bottom View \n')
    for i in sorted(map_bottom.keys()):
        print(map_bottom[i][0], end = " ")

The printTopBottomView function takes the root of the binary tree as input and calls two helper functions top_view and bottom_view to find the top and bottom views of the tree respectively. It then prints the values of the top and bottom views in separate lines.

class newNode:

    # Construct to create a newNode
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.dist = 0

root = newNode(20)
root.left = newNode(8)

root.left.left = newNode(5)
root.left.right = newNode(3)

root.left.right.left = newNode(10)
root.left.right.right = newNode(14)


root.right = newNode(22)

root.right.right = newNode(25)

print_top_bottom_view(root)

Top View

5 8 20 22 25

Bottom View

5 10 3 14 25

6. Validate BST

Write a Python code that checks whether a given binary tree is a valid binary search tree (BST).

# O(n) time | O(d) space (d is depth of the tree) --> space in call stack
def validate_bst(tree):
    return validate_bst_helper(tree, float("-inf"),  float("inf"))


def validate_bst_helper(tree, min_value, max_value):
    if tree is None:
        return True

    if tree.value < min_value or tree.value >= max_value:
        return False

    left_validate = validate_bst_helper(tree.left, min_value, tree.value)
    right_validate = validate_bst_helper(tree.right, tree.value, max_value)

    return left_validate and right_validate

Explanation:

The function works by recursively traversing the tree and keeping track of the minimum and maximum possible values that each node can take, based on the values of its parent and ancestors.

The validate_bst_helper() function takes three arguments: the current node, the minimum possible value for the current node, and the maximum possible value for the current node. It returns True if the current node satisfies the conditions for a valid binary search tree, and False otherwise.

The conditions for a valid binary search tree are:

1. The value of the current node should be greater than the minimum value for the node, and less than the maximum value for the node.
2. The left subtree of the current node should also be a valid binary search tree with a maximum value less than the current node’s value.
3. The right subtree of the current node should also be a valid binary search tree with a minimum value greater than the current node’s value.

If any of these conditions are violated, the function returns False. Otherwise, it recurses on the left and right subtrees, updating the minimum and maximum values accordingly.

The main validate_bst() function simply calls the validate_bst_helper() function with the root of the tree and the minimum and maximum possible values for a node.

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree, because it visits every node exactly once. The space complexity is O(d), where d is the depth of the binary tree, because the function calls itself recursively d times, and each call takes up a certain amount of space on the call stack.