Leetcode – Second Minimum Node In a Binary Tree Solution in Python

Spread the love

Introduction

Binary trees are a fundamental data structure in computer science, and traversing through them effectively is a common challenge. The “Second Minimum Node In a Binary Tree” problem on Leetcode tests the ability to traverse and analyze a binary tree. This article provides an in-depth understanding of the problem, the theoretical background required to solve it, and different algorithms for solving the problem with Python code.

Problem Statement

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero children. The root of the tree will be a minimum amongst all the values in the tree, and each of its children will have values which are either equal to the root or the minimum of the two children. The task is to find the second minimum value in the set made by the root and its children. If the second minimum value does not exist, output -1 instead.

Example:

Input:

    2
   / \
  2   5
     / \
    5   7

Output: 5

Explanation: The smallest value is 2, and the second smallest value is 5.

Solution

1. Depth-First Search (DFS) Traversal

One common approach to solving this problem is to use Depth-First Search (DFS). Since we know that the root of the tree will always contain the smallest value, we can use DFS to traverse the entire tree, looking for the second smallest value.

  1. Initialize two variables, root_val and second_min, to store the value of the root and the second minimum value, respectively. Set second_min initially to float('inf').
  2. Traverse the tree using DFS, starting from the root.
  3. For each node, if its value is greater than root_val and less than second_min, update second_min with the value of the node.
  4. If second_min is still float('inf') after the traversal, it means that no second minimum value was found, and -1 should be returned. Otherwise, return second_min.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def findSecondMinimumValue(self, root):
        def dfs(node):
            nonlocal second_min
            if not node:
                return
            if root.val < node.val < second_min:
                second_min = node.val
            dfs(node.left)
            dfs(node.right)
            
        root_val = root.val
        second_min = float('inf')
        dfs(root)
        
        return -1 if second_min == float('inf') else second_min

Time Complexity:

  • O(n), where n is the number of nodes in the binary tree.

Space Complexity:

  • O(h), where h is the height of the tree due to recursive stack space.

2. Breadth-First Search (BFS) Traversal

Alternatively, one could use Breadth-First Search (BFS) to traverse the tree level by level while looking for the second minimum value.

  1. Initialize two variables, root_val and second_min, to store the value of the root and the second minimum value, respectively. Set second_min initially to float('inf').
  2. Use a queue to perform BFS traversal from the root.
  3. For each node, if its value is greater than root_val and less than second_min, update second_min with the value of the node.
  4. If second_min is still float('inf') after the traversal, it means that no second minimum value was found, and -1 should be returned. Otherwise, return second_min.
from collections import deque

class Solution:
    def findSecondMinimumValue(self, root):
        root_val = root.val
        second_min = float('inf')
        
        queue = deque([root])
        
        while queue:
            node = queue.popleft()
            if root_val < node.val < second_min:
                second_min = node.val
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
                
        return -1 if second_min == float('inf') else second_min

Time Complexity:

  • O(n), where n is the number of nodes in the binary tree.

Space Complexity:

  • O(n), where n is the number of nodes in the binary tree, to store them in the queue.

Conclusion

In this article, we delved into the “Second Minimum Node In a Binary Tree” problem, a classic binary tree traversal challenge. We discussed two distinct approaches for solving this problem: Depth-First Search (DFS) and Breadth-First Search (BFS). Both approaches have their merits and can be used effectively to solve this problem.

Leave a Reply