# Second Minimum Node In a Binary Tree

• Approach's 2 analysis say:
Space Complexity: O(N) ... our depth-first search may store up to O(h) = O(N)

good analysis! Indeed, although the problem defines some special binary tree, the tree is still not a balanced one !

• Swift non-recursive approach:

``````func findSecondMinimumValue(_ root: TreeNode?) -> Int {
guard let root = root else {
return -1
}

var minimumValue = Int.max
var secondMinimumValue = Int.max

var nodes: [TreeNode] = [root]
while nodes.count > 0 {
let node = nodes.popLast()!

if let _ = node.left {
nodes.append(node.left!)
nodes.append(node.right!)
}

if node.val < minimumValue {
secondMinimumValue = minimumValue
minimumValue = node.val
} else if node.val < secondMinimumValue && node.val > minimumValue {
secondMinimumValue = node.val
}
}

return secondMinimumValue == Int.max ? -1 : secondMinimumValue
}
``````

• For this particular problem, there is a O(1) running time solution. For detail, ask me privately.

• @lqian-udel.edu not sure how to reach you privately, but I am reasonably sure there isn't and 0(1) solution, as the right child can also be == the parent node.. or am I missing something?

• @cattiveria You're right. I see no way of having a O(1) for this as the children can be equal in which case the solution must go down to the leaves.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.