Linkedin Interview Question
Senior Software Development EngineersCountry: United States
Interview Type: Phone Interview
Do we really have to recurse to left or right child node to find Min? I mean, if root is the current minimum of the tree, then either left or right child will be the 2nd minimum. So, why to go down? Some additional example trees will be helpful.
Try this one : 1, 2, 3, 4, 5, 6, 7, 8.
Here 1 and 2 will compete first and 2 will be sitting on the leaf level. Unless we recurse all the way down we will not find 2. Basically we are trying to find all the competitors of (1) that lost to (1) and find the min of those losers.
int FindSecondMinimun(Node *node, int smallest)
{
if ((node->left == nullptr) || (node->data > smallest))
{
return node->data;
}
int left_data = FindSecondMinimun(node->left, node->data);
int right_data = FindSecondMinimun(node->right, node->data);
// Not 100% std::min is a thing but i think it is =P
return std::min(left_data, right_data);
}
int FindSecondMinimun(Node *node)
{
if (node == nullptr)
{
throw new Exception("Invalid Parameter");
}
int left = FindSecondMinimun(node->left, node->data);
int right = FindSecondMinimun(node->right, node->data);
return std::min(left, right);
}
// Then we just FindSecondMinimun(Node*) from the root node.
int result = FindSecondMinimun(tree);
public class SecondMinElement {
public static void main(String[] args) {
BTN N7 = new BTN(3, null, null);
BTN N6 = new BTN(5, null, null);
BTN N5 = new BTN(2, null, null);
BTN N4 = new BTN(4, null, null);
BTN N3 = new BTN(3, N6, N7);
BTN N2 = new BTN(2, N4, N5);
BTN N1 = new BTN(2, N2, N3);
int[] arr = new int[2];
arr[0] = Integer.MAX_VALUE;
arr[1] = Integer.MAX_VALUE;
int[] res = getMin(N1, arr);
System.out.println("Second min - " + res[1]);
}
static int[] getMin(BTN node, int[] arr){
if(node == null) return arr;
arr = getMin(node.left, arr);
arr = getMin(node.right, arr);
if(node.val < arr[0]){
arr[0] = node.val;
}if(node.val < arr[1] && node.val > arr[0]){
arr[1] = node.val;
}
return arr;
}
}
class BTN{
int val;
BTN left;
BTN right;
public BTN(int val, BTN left, BTN right) {
super();
this.val = val;
this.left = left;
this.right = right;
}
}
Algo
1. If leaf node, then return
2. Hold on larger child and go down the smaller one
3. If either of the value in 2 is same as node, then return other value; else return min
private static Node getSecondMin(Node node){
if(node.left==null && node.right==null) return node;
Node n1, n2;
if(node.left.val == node.val){
n1 = node.right;
n2 = getSecondMin(node.left);
} else {
n1 = node.left;
n2 = getSecondMin(node.right);
}
if(n1.val == node.val) return n2;
if(n2.val == node.val) return n1;
return n1.val < n2.val ? n1 : n2;
}
private static Node getSecondMin(Node node){
if(node.left==null && node.right==null) return node;
Node n1, n2;
if(node.left.val == node.val){
n1 = node.right;
n2 = getSecondMin(node.left);
} else {
n1 = node.left;
n2 = getSecondMin(node.right);
}
if(n1.val == node.val) return n2;
if(n2.val == node.val) return n1;
return n1.val < n2.val ? n1 : n2;
}
public Integer secondMin(int minValue, int secondMinValue) {
if (value < minValue) {
secondMinValue = minValue;
minValue = value;
} else if (value < secondMinValue && value > minValue) {
secondMinValue = value;
}
if (leftNode != null) {
return leftNode.secondMin(minValue, secondMinValue);
}
if (rightNode != null) {
return rightNode.secondMin(minValue, secondMinValue);
}
return secondMinValue;
}
Ok, my solution in php.
class Solution{
public function secondMin($root){
if ($root===null)
return null;
if ($root->left===null)
return $root->value;
$left=$this->secondMin2($root->left,$root->value);
$right=$this->secondMin2($root->right, $root->value);
if ($root->value<$left && $root->value<$right)
return min($left,$right);
return max($left,$right);
}
public function secondMin2($root, $min ) {
if ( $root->left ===null || $root->value > $min ) //var_dump($root);
return $root->value;
$left=$this->secondMin2($root->left,$min);
$right=$this->secondMin2($root->right,$min);
if ($min < $left && $min < $right)
return min($left,$right);
return max($left,$right);
}
}
In PHP:
class Solution{
public function secondMin($root){
if ($root===null)
return null;
if ($root->left===null)
return $root->value;
$left=$this->secondMin2($root->left,$root->value);
$right=$this->secondMin2($root->right, $root->value);
if ($root->value<$left && $root->value<$right)
return min($left,$right);
return max($left,$right);
}//function nodeRoot
public function secondMin2($root, $min ) {
if ( $root->left ===null || $root->value > $min ) //var_dump($root);
return $root->value;
$left=$this->secondMin2($root->left,$min);
$right=$this->secondMin2($root->right,$min);
if ($min < $left && $min < $right)
return min($left,$right);
return max($left,$right);
}
}
class Solution{
public function secondMin($root){
if ($root===null)
return null;
if ($root->left===null)
return $root->value;
$left=$this->secondMin2($root->left,$root->value);
$right=$this->secondMin2($root->right, $root->value);
if ($root->value<$left && $root->value<$right)
return min($left,$right);
return max($left,$right);
}
public function secondMin2($root, $min ) {
if ( $root->left ===null || $root->value > $min )
return $root->value;
$left=$this->secondMin2($root->left,$min);
$right=$this->secondMin2($root->right,$min);
if ($min < $left && $min < $right)
return min($left,$right);
return max($left,$right);
}
}
class Solution{
public function secondMin($root){
if ($root===null)
return null;
if ($root->left===null)
return $root->value;
$left=$this->secondMin2($root->left,$root->value);
$right=$this->secondMin2($root->right, $root->value);
if ($root->value<$left && $root->value<$right)
return min($left,$right);
return max($left,$right);
}
public function secondMin2($root, $min ) {
if ( $root->left ===null || $root->value > $min )
return $root->value;
$left=$this->secondMin2($root->left,$min);
$right=$this->secondMin2($root->right,$min);
if ($min < $left && $min < $right)
return min($left,$right);
return max($left,$right);
}
}
/**
* This should return the minimum
* int value in the given tournament tree
*/
public static Integer findMin(Tree root, int min, int secondmin) {
if(root.left == null && root.right == null)
return min;
min = Math.min(min, root.value);
return Math.min(findMin(root.left, min, secondmin), findMin(root.right, min, secondmin));
}
/**
* This should return the second minimum
* int value in the given tournament tree
*/
public static Integer secondMin(Tree root, int min, int secondmin) {
if(root == null) {
return secondmin;
}
if (root.value > min && root.value < secondmin) {
secondmin = root.value;
}
return Math.min(secondMin(root.left, min, secondmin), secondMin(root.right, min, secondmin));
}
/**
* This should return the minimum
* int value in the given tournament tree
*/
public static Integer findMin(Tree root, int min, int secondmin) {
if(root.left == null && root.right == null)
return min;
min = Math.min(min, root.value);
return Math.min(findMin(root.left, min, secondmin), findMin(root.right, min, secondmin));
}
/**
* This should return the second minimum
* int value in the given tournament tree
*/
public static Integer secondMin(Tree root, int min, int secondmin) {
if(root == null) {
return secondmin;
}
if (root.value > min && root.value < secondmin) {
secondmin = root.value;
}
return Math.min(secondMin(root.left, min, secondmin), secondMin(root.right, min, secondmin));
}
/**
* This should return the minimum
* int value in the given tournament tree
*/
public static Integer findMin(Tree root, int min, int secondmin) {
if(root.left == null && root.right == null)
return min;
min = Math.min(min, root.value);
return Math.min(findMin(root.left, min, secondmin), findMin(root.right, min, secondmin));
}
/**
* This should return the second minimum
* int value in the given tournament tree
*/
public static Integer secondMin(Tree root, int min, int secondmin) {
if(root == null) {
return secondmin;
}
if (root.value > min && root.value < secondmin) {
secondmin = root.value;
}
return Math.min(secondMin(root.left, min, secondmin), secondMin(root.right, min, secondmin));
}
/**
* This should return the minimum
* int value in the given tournament tree
*/
public static Integer findMin(Tree root, int min, int secondmin) {
if(root.left == null && root.right == null)
return min;
min = Math.min(min, root.value);
return Math.min(findMin(root.left, min, secondmin), findMin(root.right, min, secondmin));
}
/**
* This should return the second minimum
* int value in the given tournament tree
*/
public static Integer secondMin(Tree root, int min, int secondmin) {
if(root == null) {
return secondmin;
}
if (root.value > min && root.value < secondmin) {
secondmin = root.value;
}
return Math.min(secondMin(root.left, min, secondmin), secondMin(root.right, min, secondmin));
}
- rsrs3 April 06, 2017