671. Second Minimum Node In a Binary Tree

EasyTreeDepth-First SearchBinary Tree
Leetcode Link

Problem Description

The problem presents a special binary tree where every node has either two or zero child nodes (sub-nodes). The key property of this tree is that the value of a non-leaf node is the minimum of the values of its two children. The task is to find the second smallest value in the entire tree. If all the node values are the same or there is no second minimum value, the function should return -1.

Intuition

To find the second minimum value, we need to traverse the tree and keep track of the values we encounter. Since the smallest value in the tree is at the root (due to the property of the tree), we can ignore it in our search for the second minimum. We're interested in the smallest value that is larger than the root's value.

Here's the intuition for the provided solution approach:

  1. Start a Depth-First Search (DFS) traversal from the root. Since the problem only needs us to find a value, DFS is preferred over Breadth-First Search (BFS) as it's simpler to implement and can short-circuit faster.

  2. Each time we visit a node, we check if it has a value greater than the value of the root (since the root's value is the minimum of the entire tree).

  3. If the current node's value is greater than the root's value, it is a candidate for being the second minimum value. If we haven't found a candidate before (ans is -1), we set our answer to the current node's value. If we have found candidates before, we update the answer to be the minimum of the current node's value and the current answer.

  4. We keep updating the answer as we find new candidates during our traversal. Once the traversal is complete, ans will hold the second smallest value if it exists; otherwise, it remains as -1.

  5. The nonlocal keyword is used to modify the ans and v variables that are defined outside the nested dfs function.

The reason we can't just compare all the node values directly is because of the special property of this kind of tree. The second smallest value must be the value of a node's child, where the node itself has the smallest value. So, we don't need to consider all nodes but can focus on leaf nodes and nodes one level above leaf nodes.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Solution Approach

The solution uses a recursion-based DFS (Depth-First Search) to traverse the tree. The goal is to maintain the second minimum value as we go through each node. Let's discuss the implementation details using the reference solution approach provided above:

  1. TreeNode Class: Before diving into the algorithm, it's important to understand that the input tree is composed of instances of TreeNode, where each TreeNode object represents a node in the binary tree with a val, a pointer left to a left subtree, and a pointer right to a right subtree.

  2. Depth-First Search (DFS): We perform DFS starting from the root node. The DFS is realized through the function dfs.

    1def dfs(root):
2    if root:
3        dfs(root.left)
4        dfs(root.right)
5        nonlocal ans, v
6        if root.val > v:
7            ans = root.val if ans == -1 else min(ans, root.val)

    This algorithm recursively explores both sub-trees (root.left and root.right) before dealing with the current root node, which is characteristic of the post-order traversal pattern of DFS.

  3. Post-Order Traversal: We use the post-order traversal here because we want to visit each child before dealing with the parent node. This allows us to find the candidate for the second minimum value from the leaf upwards, respecting the special property of this binary tree (the node's value is the minimum of its children).

  4. Tracking the Second Minimum: We maintain two variables, ans and v.

    • v is assigned the value of the root and represents the smallest value in the tree.
    • ans is used to track the second smallest value, initialized as -1, which also represents the condition when there's no second minimum value.

  5. Local vs. Global Scope: The use of the keyword nonlocal is significant. Since ans and v are modified within the dfs function, and Python functions create a new scope, we must declare these variables nonlocal to indicate that they are not local to dfs, allowing us to modify the outer scope variables ans and v.

By the end of DFS execution, ans will contain the second minimum value or -1 if there's no such value. Then, the main function findSecondMinimumValue just needs to return ans.

The given solution efficiently leverages recursion for tree traversal and runs in O(n) time where n is the number of nodes in the tree, since it visits each node exactly once. The space complexity is also O(n) due to the recursion call stack, which can go as deep as the height of the tree in the worst-case scenario (although for this special type of binary tree, that would mean a very unbalanced tree).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Example Walkthrough

Let's go through a small example using the solution approach. Consider a binary tree:

1    2
2   / \
3  2   5
4     / \
5    5   7

We need to find the second minimum value in the special binary tree. In the given binary tree, the root node has the minimum value, which is 2.

  • We start our DFS traversal from the root node (2). We set v as the value of the root node, which is 2, and ans is set to -1.
  • We visit the left child (2). As its value is not greater than v, we continue our traversal.
  • We then proceed to the right child (5). Its value is greater than v, so ans is updated from -1 to 5.
  • Next, we visit the left child of the right child, which again is (5). Since 5 is already our current ans, and it's not less than the current ans, we don't update ans.
  • The last node we visit is the right child of the right child (7). The value of this node is greater than v and greater than our current ans of 5, so we do not update ans.

After completing the DFS traversal, ans contains the value 5, which is the second minimum value in the tree. If there were no value greater than 2 in the example tree, ans would have remained as -1. This corresponds to the situation where either all node values are the same or there's no second minimum value.

By performing DFS, we minimized unnecessary checks and efficiently found the second minimum value, if it existed. This approach ensures that every node is visited only once, leading to an O(n) time complexity, where n is the number of nodes in the tree. The space complexity is also O(n), which is attributed to the recursion call stack.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
10        # Initialize variables for the final answer and the root value.
11        # The root value is the minimum value by definition of the problem.
12        self.second_minimum = -1
13        self.root_value = root.val
14      
15        # Define a Depth-First Search (DFS) recursive function.
16        def dfs(node):
17            if node:
18                # Recurse left sub-tree.
19                dfs(node.left)
20                # Recurse right sub-tree.
21                dfs(node.right)
22                # If the current node's value is greater than the root's value, 
23                # it's a candidate for the second minimum.
24                if node.val > self.root_value:
25                    # If the second minimum hasn't been found yet, use this value,
26                    # else update it only if we find a smaller value.
27                    self.second_minimum = min(self.second_minimum, node.val) if self.second_minimum != -1 else node.val
28
29        # Perform DFS starting from the root.
30        dfs(root)
31      
32        # Return the second minimum value found; -1 if it doesn't exist.
33        return self.second_minimum
34
1// Definition for a binary tree node.
2class TreeNode {
3    int val;
4    TreeNode left;
5    TreeNode right;
6    TreeNode() {}
7    TreeNode(int val) { this.val = val; }
8    TreeNode(int val, TreeNode left, TreeNode right) {
9        this.val = val;
10        this.left = left;
11        this.right = right;
12    }
13}
14
15class Solution {
16    private int secondMinValue = -1; // Variable to store the second minimum value
17
18    public int findSecondMinimumValue(TreeNode root) {
19        // Start depth-first search with the root node's value as the initial value
20        depthFirstSearch(root, root.val);
21        // After DFS, return the second minimum value found
22        return secondMinValue;
23    }
24
25    // Helper method to perform a depth-first search on the tree
26    private void depthFirstSearch(TreeNode node, int firstMinValue) {
27        // If the current node is not null, proceed with DFS
28        if (node != null) {
29            // Recursively traverse the left subtree
30            depthFirstSearch(node.left, firstMinValue);
31            // Recursively traverse the right subtree
32            depthFirstSearch(node.right, firstMinValue);
33            // Check if node's value is greater than first minimum value
34            // and update the second minimum value accordingly
35            if (node.val > firstMinValue) {
36                // If secondMinValue hasn't been updated yet, use the current node's value
37                // Else, update it to be the minimum of the current node's value and the existing secondMinValue
38                secondMinValue = secondMinValue == -1 ? node.val : Math.min(secondMinValue, node.val);
39            }
40        }
41    }
42}
43
1#include <algorithm> // For using the min() function
2
3// Definition for a binary tree node.
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    int secondMinimumValue = -1; // initialized with -1 to indicate no second minimum found
16
17    int findSecondMinimumValue(TreeNode* root) {
18        // Start DFS with root value as reference
19        depthFirstSearch(root, root->val);
20        // Return the second minimum value found
21        return secondMinimumValue;
22    }
23  
24    // Perform a depth-first search to find the second minimum value
25    void depthFirstSearch(TreeNode* node, int firstMinValue) {
26        // Base condition: If node is nullptr, return immediately
27        if (!node) return;
28
29        // Recursively search left subtree
30        depthFirstSearch(node->left, firstMinValue);
31        // Recursively search right subtree
32        depthFirstSearch(node->right, firstMinValue);
33      
34        // Check if the current node's value is greater than the first minimum value
35        if (node->val > firstMinValue) {
36            // Update second minimum value if it's either not set or found a smaller value
37            secondMinimumValue = (secondMinimumValue == -1) ? node->val : std::min(secondMinimumValue, node->val);
38        }
39    }
40};
41
1// TypeScript definition for a binary tree node.
2interface TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6}
7
8/**
9 * Finds the second minimum value in a special binary tree,
10 * where each node in this tree has exactly two or zero sub-node.
11 * If the second minimum value does not exist, return -1.
12 * 
13 * @param {TreeNode | null} root - The root node of the binary tree.
14 * @return {number} The second minimum value in the given binary tree.
15 */
16const findSecondMinimumValue = (root: TreeNode | null): number => {
17    // Initialize the answer to -1, assuming the second minimum value might not exist.
18    let answer: number = -1;
19  
20    // Store the value of the root, which is the minimum value in the tree.
21    const rootValue: number = root.val;
22
23    // Define a depth-first search function to traverse the tree.
24    const dfs = (node: TreeNode | null): void => {
25        // If the node is null, we've reached the end of a branch and should return.
26        if (!node) {
27            return;
28        }
29
30        // Continue the DFS on the left and right children.
31        dfs(node.left);
32        dfs(node.right);
33
34        // If the node's value is greater than that of the root (minimum value)
35        // and if this value is smaller than the current answer or if the answer
36        // is still set to the initial -1, then we update the answer.
37        if (node.val > rootValue) {
38            if (answer === -1 || node.val < answer) {
39                answer = node.val;
40            }
41        }
42    };
43
44    // Start the DFS traversal with the root node.
45    dfs(root);
46
47    // Return the answer, which is either the second minimum value or -1.
48    return answer;
49};
50
51// This part of the code would be used to call the function and pass the tree root.
52// Example usage:
53// const root: TreeNode = { val: 2, left: { val: 2, left: null, right: null }, right: { val: 5, left: { val: 5, left: null, right: null }, right: { val: 7, left: null, right: null } } };
54// console.log(findSecondMinimumValue(root));
55
Not Sure What to Study? Take the 2-min Quiz๏ผš

In a binary min heap, the maximum element can be found in:

Time and Space Complexity

The provided code implements a Depth-First Search (DFS) to find the second minimum value in a binary tree. Hereโ€™s an analysis of its time and space complexity:

Time Complexity

The time complexity of the DFS is O(N), where N is the number of nodes in the binary tree. In the worst case, the algorithm visits every node exactly once to determine the second smallest value.

Space Complexity

The space complexity is O(H), where H is the height of the tree. This space is required for the call stack during the recursion, which in the worst case is equivalent to the height of the tree. For a balanced tree, it would be O(log N), but in the worst case of a skewed tree, it could be O(N).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Binary Tree Min Depth

Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ