Home
How to Find Second Minimum Node In a Binary Tree (Java)?
Tags:, , , , ,

How to Find Second Minimum Node In a Binary Tree (Java)?

January 29, 2019 No Comments algorithms, BFS, DFS, java

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node’s value is the smaller value among its two sub-nodes.

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes’ value in the whole tree.

If no such second minimum value exists, output -1 instead.

Example 1:
Input: 

    2
   / \
  2   5
     / \
    5   7

Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.
Example 2:
Input:

2
/ \
2 2

Output: -1
Explanation: The smallest value is 2, but there isn’t any second smallest value.

The target is to find the second minimum in a special binary tree where the root nodes are the smallest (minimal heap). There are a few algorithms that could solve this problem.

Bruteforce with Breadth First Search

If we don’t make use of the mini-heap properties of the binary tree, we can simply bruteforce the binary tree, putting all nodes in an array, sort them, then we can easily obtain the second minimal value. However, we need to make sure duplicate nodes are only inserted in the array once.

The following BFS uses a queue to do the iterative search level by level.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) {
            return -1;
        }
        Queue<TreeNode> q = new LinkedList<>();
        Set<Integer> s = new HashSet<>();
        List<Integer> a = new ArrayList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode p = q.poll();
            if (!s.contains(p.val)) {
                a.add(p.val);
            }
            s.add(p.val);
            if (p.left != null) { q.add(p.left); }
            if (p.right != null) { q.add(p.right); }
        }
        Collections.sort(a);
        return a.size() >= 2 ? a.get(1) : -1;
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) {
            return -1;
        }
        Queue<TreeNode> q = new LinkedList<>();
        Set<Integer> s = new HashSet<>();
        List<Integer> a = new ArrayList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode p = q.poll();
            if (!s.contains(p.val)) {
                a.add(p.val);
            }
            s.add(p.val);
            if (p.left != null) { q.add(p.left); }
            if (p.right != null) { q.add(p.right); }
        }
        Collections.sort(a);
        return a.size() >= 2 ? a.get(1) : -1;
    }
}

The time complexity is O(nlogn) where the most time consuming part is sorting.

Bruteforce with Depth First Search in Recursion

The same idea as above could be implemented in DFS (Depth First Search) in the form of recursion where the compiler generates and maintains the stack automatically for you.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private void dfs(TreeNode root, Set<integer> s) {
        if (root == null) {
            return;
        }
        if (!s.contains(root.val)) {
            s.add(root.val);
        }
        dfs(root.left, s);
        dfs(root.right, s);
    }
        
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) {
            return -1;
        }
        Set<Integer&t; a = new HashSet<>();
        dfs(root, a);
        List<Integer> b = new ArrayList<>(a);
        Collections.sort(b);
        return b.size() >= 2 ? b.get(1) : -1;
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private void dfs(TreeNode root, Set<integer> s) {
        if (root == null) {
            return;
        }
        if (!s.contains(root.val)) {
            s.add(root.val);
        }
        dfs(root.left, s);
        dfs(root.right, s);
    }
        
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) {
            return -1;
        }
        Set<Integer&t; a = new HashSet<>();
        dfs(root, a);
        List<Integer> b = new ArrayList<>(a);
        Collections.sort(b);
        return b.size() >= 2 ? b.get(1) : -1;
    }
}

O(nlogn) time complexity.

Optimised DFS

The above two solutoins both use the set to avoid duplicate numbers. Let’s make min1 = root.val, as we are only interested in the second minimal number, if at any node we have the value larger than min1, we don’t need to search that sub-tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int min1;
    long ans = Long.MAX_VALUE;
    
    private void dfs(TreeNode root) {
        if (root == null) return;
        if (min1 < root.val && root.val < ans) {
            ans = root.val;
        } else if (min1 == root.val) {
            dfs(root.left);
            dfs(root.right);
        }
    }
    
    public int findSecondMinimumValue(TreeNode root) {
        min1 = root.val;
        dfs(root);
        return ans < Long.MAX_VALUE ? (int)ans : -1;
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int min1;
    long ans = Long.MAX_VALUE;
    
    private void dfs(TreeNode root) {
        if (root == null) return;
        if (min1 < root.val && root.val < ans) {
            ans = root.val;
        } else if (min1 == root.val) {
            dfs(root.left);
            dfs(root.right);
        }
    }
    
    public int findSecondMinimumValue(TreeNode root) {
        min1 = root.val;
        dfs(root);
        return ans < Long.MAX_VALUE ? (int)ans : -1;
    }
}

This approach is superior in terms of space complexity.

Depth First Search on Two Sub Trees

The second minimum would be the minimal of the first values of both sub tree that are bigger than the root value. If no such values are existent, we return -1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {    
    private int dfs(TreeNode root, int m) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        if (root.val > m) {
            return root.val;
        }        
        int min1 = dfs(root.left, m);
        int min2 = dfs(root.right, m);
        return Math.min(min1, min2);
    }
    
    public int findSecondMinimumValue(TreeNode root) {
        int v = dfs(root, root.val);
        return v == Integer.MAX_VALUE ? -1 : v;
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {    
    private int dfs(TreeNode root, int m) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        if (root.val > m) {
            return root.val;
        }        
        int min1 = dfs(root.left, m);
        int min2 = dfs(root.right, m);
        return Math.min(min1, min2);
    }
    
    public int findSecondMinimumValue(TreeNode root) {
        int v = dfs(root, root.val);
        return v == Integer.MAX_VALUE ? -1 : v;
    }
}

Similarly, we can compare the root value to each subtree, and return the minimal of both sub-min values.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {    
    public int findSecondMinimumValue(TreeNode root) {
        if(root.left == null)   return -1;
        
        int left  = (root.left.val  == root.val) ? findSecondMinimumValue(root.left)  : root.left.val;
        int right = (root.right.val == root.val) ? findSecondMinimumValue(root.right) : root.right.val;
 
        if(left  == -1)         return right;
        if(right == -1)         return left;
 
        return Math.min(left, right);
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {    
    public int findSecondMinimumValue(TreeNode root) {
        if(root.left == null)   return -1;
        
        int left  = (root.left.val  == root.val) ? findSecondMinimumValue(root.left)  : root.left.val;
        int right = (root.right.val == root.val) ? findSecondMinimumValue(root.right) : root.right.val;

        if(left  == -1)         return right;
        if(right == -1)         return left;

        return Math.min(left, right);
    }
}

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
949 words
Last Post: The GOTO Keyword in LOGO Turtle Programming
Next Post: How to Fix "Unsafe cannot be resolved to a type" in Eclipse/Java?

The Permanent URL is: How to Find Second Minimum Node In a Binary Tree (Java)?

Related posts:

  1. Fixing Profile Query Command due to API Change in Steem Blockchain Due to an API change in SteemIt see this post, the following code to get...
  2. The Secure Shell (SSH) Chrome Extension developed by Google Speaking about SSH tools, we often use the PuTTY or Termius, which are heavy weight...
  3. Teaching Kids Programming – Closest Binary Search Tree Value (Recursion + Inorder Traversal + Binary Search Algorithm) Teaching Kids Programming: Videos on Data Structures and Algorithms Given the root of a binary...
  4. How to Determine Sum of Two Square Numbers? Given a non-negative integer c, your task is to decide whether there’re two integers a...
  5. Algorithms to Determine a Palindrome Number Determine whether an integer is a palindrome. An integer is a palindrome when it reads...
  6. You need a Numeric Keypad to Start with Your HHKB! Getting a HHKB and being excited for a few days? Sooner or later, you ‘ll...
  7. The Young Prompt Engineers My sons were excited to show me the Text to Image feature using Microsoft Bing....
  8. Three ways of Running a continuous NodeJS Application on Your Server Let’s say, I have an application that is written in NodeJs, that process the latest...

Leave a Reply