algoadvance

Leetcode 671. Second Minimum Node In a Binary Tree

Problem Statement

You are given a binary tree where each node has the same value, except for one node which has a different value. You need to find the second minimum value in the binary tree. If all the nodes have the same value, return -1.

Clarifying Questions

1. What is the minimum number of nodes in the tree?
   • The binary tree will have at least one node.
2. Can the binary tree be unbalanced?
   • Yes, the tree can be unbalanced.
3. What is the range of values that the nodes can have?
   • Node values can be any valid integer.
4. How should the function behave if there is no second minimum value?
   • If there is no second minimum value, return -1.

Strategy

1. Edge Case Handling:
   • If the root is nullptr, return -1.
   • If the tree has only one node, return -1.
2. Recursive Inorder Traversal:
   • Traverse the tree starting from the root. Keep track of the minimum and the second minimum values encountered during the traversal.
   • If a node’s value is smaller than the current minimum, update the second minimum to be the current minimum, and update the minimum to be the node’s value.
   • If a node’s value is larger than the current minimum and smaller than the current second minimum, then update the second minimum.
3. Initial Setup:
   • Initialize the minimum value to root->val.
   • Initialize the second minimum to -1 (or a suitable large value that won’t be in the tree).
4. Recursive Traversal:
   • Implement a helper function to traverse the tree, updating the necessary values.

Code

#include <iostream>
#include <climits>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int findSecondMinimumValue(TreeNode* root) {
        if (!root) return -1;
        
        long first_min = root->val;
        long second_min = LONG_MAX;
        
        traverse(root, first_min, second_min);
        
        if (second_min == LONG_MAX) {
            return -1;
        } else {
            return static_cast<int>(second_min);
        }
    }
    
private:
    void traverse(TreeNode* node, long first_min, long &second_min) {
        if (!node) return;

        if (node->val > first_min && node->val < second_min) {
            second_min = node->val;
        } else if (node->val == first_min) {
            traverse(node->left, first_min, second_min);
            traverse(node->right, first_min, second_min);
        }
    }
};

int main() {
    // Example Tree: [2,2,5,null,null,5,7]
    TreeNode* root = new TreeNode(2);
    root->left = new TreeNode(2);
    root->right = new TreeNode(5);
    root->right->left = new TreeNode(5);
    root->right->right = new TreeNode(7);

    Solution solution;
    int result = solution.findSecondMinimumValue(root);
    std::cout << "Second Minimum Value: " << result << std::endl; // Output: 5

    return 0;
}

Time Complexity

• Time Complexity: O(N), where N is the number of nodes in the binary tree. This is because we potentially need to visit each node once.

• Space Complexity: O(H), where H is the height of the binary tree due to the call stack space used by the recursion. In the worst case, this could be O(N) for an unbalanced tree, but for a balanced tree, it will be O(log N).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?