Second Minimum Node In a Binary Tree


  • 0

    Click here to see the full article post


  • 0
    I

    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 !


  • 0
    Z

    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
    }
    

  • 0
    L

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


  • 0
    C

    @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?


  • 0
    D

    @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.


Log in to reply
 

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