Problem Description
Given a non-empty special binary tree consisting of nodes with non-negative values, where each node has exactly two or zero sub-nodes. If a node has two sub-nodes, then the node's value is the smaller value among its two sub-nodes. You need to output the second minimum value in the set of all node values in the tree. If no such second minimum value exists, output -1 instead.
Key Insights
- Each internal node in the tree satisfies the property that its value is the minimum of its two children.
- The smallest value will always be at the root of the tree.
- We need to traverse the tree to find the second smallest value, considering nodes that can be equal to the smallest value.
- A depth-first search (DFS) can be used to explore the tree and track unique values.
Space and Time Complexity
Time Complexity: O(N), where N is the number of nodes in the tree, since we visit each node once. Space Complexity: O(H), where H is the height of the tree due to the recursion stack in DFS.
Solution
To solve this problem, we utilize a depth-first search (DFS) approach to traverse the binary tree. We start from the root and explore its left and right children recursively. We maintain a set to track unique values encountered in the tree. After the traversal, we check if the set has more than one unique value. If it does, we return the second smallest value; otherwise, we return -1.