Second Minimum Node In a Binary Tree

Problem Statement
This is LeetCode problem 671: "Second Minimum Node In a Binary Tree," commonly appearing in LinkedIn coding interviews with tags Tree, DFS, and Binary Tree. You are given a non-empty special binary tree where each node has either exactly two children or zero children (no nodes with one child), all node values are non-negative integers, and for any node with children, its value equals the minimum of its two children's values: root.val = min(root.left.val, root.right.val). The task is to find and return the second smallest distinct value among all nodes in the tree; if no such second minimum exists (all nodes have the same value), return -1.[1][3][7]

Key Properties

• The root always holds the smallest value in the tree due to the min-heap-like property.
• Every internal node propagates the minimum value from its children upward.
• The tree is "full" in the sense that non-leaf nodes have exactly two children.[3][1]

Input/Output Examples

| Example | Tree Structure | Input Representation | Output | Explanation | |---------|----------------|----------------------|--------|-------------| | 1 | <br> 2<br> / \<br> 2 5<br> / \<br> 5 7<br> | root = [2][2][5][5][7] | 5 | Values are {2,5,7}; smallest is 2, second smallest is 5. [1][5] | | 2 | <br> 2<br> / \<br> 2 2<br> / \<br>2 2<br> | root = [2,2,2,null,null,2,2] | -1 | All values are 2; no second minimum. [3] |

Constraints

• The number of nodes in the tree is in the range.[2]
• Each node's value is an integer in [1, 231 - 1].
• The tree is guaranteed to be valid per the special properties (full binary tree with min-child property).[7][1][3]