## Google Interview Question for Software Engineer Interns

• 1
of 1 vote

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
8
of 8 vote

after calling this function, "minDiff" will hold the minimum difference. O(n) time.

``````static void findBSTMinimumValueDifference(Node root) {
if (root != null) {
findBSTMinimumValueDifference(root.left);
if (previous != null && minDiff > root.value - previous.value) {
minDiff = root.value - previous.value;
}
previous = root;
findBSTMinimumValueDifference(root.right);
}
}

static int minDiff = Integer.MAX_VALUE;
static Node previous;``````

Comment hidden because of low score. Click to expand.
2
of 2 vote

do inorder traversal, compare current node to the previously visited one.
While traversing maintain "minDiff" variable.
If current (node - previous) is greater than "minDiff" then update "minDiff".
Return "minDiff" in the end.

Comment hidden because of low score. Click to expand.
2
of 2 vote

I am going to do inorder traversal of BST tree and in the meanwhile will check the mininum difference between each two successive elements (they are in ascending order) and take the minimum value. O(n) complexity

Comment hidden because of low score. Click to expand.
2
of 2 vote

O(n), For every node get max from left branch and get min from right branch and check which one gives min diff compare to the node. Do recursively for each node in a tree and keep latest min result in variable. Both getting min/max from sub trees and recursion can be done in same tree recursion.

``````class Node:
def __init__(self, value, left, right):
self.value = value
self.left = left
self.right = right

min_pair = None
min_diff = None

def find_min_pair(node, return_max):
global min_diff
global min_pair
if node is not None:
left_max = find_min_pair(node.left, True)
right_min = find_min_pair(node.right, False)

if left_max is not None:
diff = abs(node.value - left_max)
if min_diff is None or diff < min_diff:
min_diff = diff
min_pair = (left_max, node.value)
if right_min is not None:
diff = abs(node.value - right_min)
if min_diff is None or diff < min_diff:
min_diff = diff
min_pair = (right_min, node.value)

if return_max is None:
return None
elif return_max == True:
if right_min is not None:
return right_min
else:
return node.value
else:
if left_max is not None:
return left_max
else:
return node.value
else:
return None

min_pair = None
min_diff = None
bst = Node(10, Node(5, None, None), Node(16, Node(12, None, None), Node(20, None, None)))
find_min_pair(bst, None)
print(min_pair)

min_pair = None
min_diff = None
bst = None
find_min_pair(bst, None)
print(min_pair)

min_pair = None
min_diff = None
bst = Node(10, None, None)
find_min_pair(bst, None)
print(min_pair)

min_pair = None
min_diff = None
bst = Node(10, Node(100, None, None), None)
find_min_pair(bst, None)
print(min_pair)

min_pair = None
min_diff = None
bst = Node(10, None, Node(100, None, None))
find_min_pair(bst, None)
print(min_pair)``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

I realized the example is not added correctly. I add it here again:

Given an input BST, find the minimum value difference between any two nodes in the tree.

...10
.../....\
5.....16
......./.....\
....12.....20

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import sys

class Node:

def __init__(self, v):
self.v = v
self.left = None
self.right = None

class BST:

def __init__(self, node):

self.root = node
self.distanceD = sys.maxsize
self.tested = set()

for n in nList:
current = self.root
#print('n:: ', n, ' and current:: ', current.v)

while True:
if  n < current.v:
if current.left:
current = current.left
else:
newNode = Node(n)
current.left = newNode
break
elif n > current.v:
if current.right:
current = current.right
else:
newNode = Node(n)
current.right = newNode
break
else:
break

def updateDistance(self, lList):

for i in range(0, len(lList)-1):
for j in range(i+1, len(lList)):
if (lList[j], lList[i]) not in self.tested:
d = lList[j] - lList[i]
if d < self.distanceD :
self.distanceD = d

def traverseInorder(self, current):

l = []
r = []
c = []
if current.left:
l = self.traverseInorder(current.left)

c = list([current.v])
#print(c)

if current.right:

r = self.traverseInorder(current.right)
z = l + c + r
#print(z)
self.updateDistance(z)
return z

aList = [34, 23, 78, 12, 19, 77, 21, 101, 52]
#aList = [16,5, 12, 20]
r = Node(10)
myBST = BST(r)
bList = myBST.traverseInorder(myBST.root)
#print(bList)
#print(myBST.tested)
print(myBST.distanceD)
#print('total subcases: ', len(myBST.tested))``````

Sample Output:

[10, 12, 19, 21, 23, 34, 52, 77, 78, 101]
1

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public int GetMinDiff(TreeNode root)
{
if (root == null)
return 0;

Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
int minValue = int.MaxValue;

// Using Breath Search/Traversal
while (queue.Count > 0)
{
var node = queue.Dequeue();
if (node.Left != null)
{
queue.Enqueue(node.Left);
int value = GetMaxValue(node.Left);
minValue = Math.Min(minValue, node.Value - value);
}
if (node.Right != null)
{
queue.Enqueue(node.Right);
int value = GetMinValue(node.Right);
minValue = Math.Min(minValue, value - node.Value);
}
}

return minValue;
}

private int GetMinValue(TreeNode root)
{
var node = root;
while (node.Left != null)
node = node.Left;

return node.Value;
}

private int GetMaxValue(TreeNode root)
{
var node = root;
while (node.Right != null)
node = node.Right;

return node.Value;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<iostream>

using namespace std;

struct node
{
int key;
struct node *left, *right;
};

// A utility function to create a new BST node
struct node *newNode(int item)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

// A utility function to do inorder traversal of BST
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left);
printf("%d \n", root->key);
inorder(root->right);
}
}

/* A utility function to insert a new node with given key in BST */
struct node* insert(struct node* node, int key)
{
/* If the tree is empty, return a new node */
if (node == NULL) return newNode(key);

/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);

/* return the (unchanged) node pointer */
return node;
}

int *InorderTraversalOfBST(node *binarySearchTreeRoot)
{
int i = 0, arr_size = 7;
int *tempArr = new int[arr_size];

for (int j = 0; j < arr_size; j++)
tempArr[j] = 0;

while (binarySearchTreeRoot != NULL)
{
InorderTraversalOfBST(binarySearchTreeRoot -> left);
printf("%d", binarySearchTreeRoot -> key);
if (i < arr_size)
{
tempArr[i++] = binarySearchTreeRoot -> key;
}
InorderTraversalOfBST(binarySearchTreeRoot -> right);
}
return 	tempArr;
}

/* The function assumes that there are at least two elements in array. The function returns a negative value if the array is sorted in decreasing order. Returns 0 if elements are equal  */

int minDiff(int arr[], int size)
{
int min_diff = arr[1] - arr[0];
int min_element = arr[0];
int i;
for (i = 1; i < size; i++)
{
if (arr[i] - min_element < min_diff)
min_diff = arr[i] - min_element;
if (arr[i] < min_element)
min_element = arr[i];
}
return min_diff;
}

/* Driver program to test above function */
int main()
{
struct node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);

int *arr = InorderTraversalOfBST(root);
int size = sizeof(arr) / sizeof(arr[0]);
printf("Minimum difference is %d", minDiff(arr, size));
getchar();
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>

using namespace std;

struct node
{
int key;
struct node *left, *right;
};

// A utility function to create a new BST node
struct node *newNode(int item)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

// A utility function to do inorder traversal of BST
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left);
printf("%d \n", root->key);
inorder(root->right);
}
}

/* A utility function to insert a new node with given key in BST */
struct node* insert(struct node* node, int key)
{
/* If the tree is empty, return a new node */
if (node == NULL) return newNode(key);

/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);

/* return the (unchanged) node pointer */
return node;
}

int *InorderTraversalOfBST(node *binarySearchTreeRoot)
{
int i = 0, arr_size = 7;
int *tempArr = new int[arr_size];

for (int j = 0; j < arr_size; j++)
tempArr[j] = 0;

while (binarySearchTreeRoot != NULL)
{
InorderTraversalOfBST(binarySearchTreeRoot -> left);
printf("%d", binarySearchTreeRoot -> key);
if (i < arr_size)
{
tempArr[i++] = binarySearchTreeRoot -> key;
}
InorderTraversalOfBST(binarySearchTreeRoot -> right);
}
return tempArr;
}

/* The function assumes that there are at least two elements in array. The function returns a negative value if the array is sorted in decreasing order. Returns 0 if elements are equal */

int minDiff(int arr[], int size)
{
int min_diff = arr[1] - arr[0];
int min_element = arr[0];
int i;
for (i = 1; i < size; i++)
{
if (arr[i] - min_element < min_diff)
min_diff = arr[i] - min_element;
if (arr[i] < min_element)
min_element = arr[i];
}
return min_diff;
}

/* Driver program to test above function */
int main()
{
struct node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);

int *arr = InorderTraversalOfBST(root);
int size = sizeof(arr) / sizeof(arr[0]);
printf("Minimum difference is %d", minDiff(arr, size));
getchar();
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

You can do it just using in-order traversal

``````public int minDiff() {
return minDiff(new TreeNode(null), root, -1);
}

private int minDiff(TreeNode prev, TreeNode cur, int min) {
if(cur.left != null) {
min = minDiff(prev, cur.left, min);
}
if(prev.data != null) {
int diff = Math.abs(prev.data - cur.data);
min = min == -1 ? diff : Math.min(diff, min);
}

prev.data = cur.data;

if(cur.right != null) {
min = minDiff(prev, cur.right, min);
}
return min;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

for a none leaf node of BST, elements in its left sub tree are smaller than it, and elements in its right sub tree are bigger than it. So, min difference can only happen between a none leaf node and its direct children nodes. So, the min difference of a BST is the min difference of each none leaf node and their direct children node. We can use dynamic programming to compute difference between a none leaf node and its children nodes, and propagate the difference up to it parent.

let MD(n) is the min difference than can be gotten from the sub tree that are rooted at node n. Then:
MD(n) = min(value(n)-value(child of n), MD(child of n))

The time complexity is in linear to the size of the tree.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Not sure if this is the most efficient solution, but it is working:

``````import java.io.*;
import java.util.*;

class Solution {
private static final int NOT_FOUND = -1;

public static Tree buildTree() {
Node node5 = new Node(5);
Node node10 = new Node(10);
Node node16 = new Node(16);
Node node12 = new Node(12);
Node node20 = new Node(20);

node10.setLeft(node5);
node10.setRight(node16);
node16.setLeft(node12);
node16.setRight(node20);

return new Tree(node10);
}

public static int findMinimalDiffRec(Node node, int num) {
int diffFromValue = Math.abs(node.getValue() - num);

if (node.getLeft() != null) {
int leftMinFromNum = findMinimalDiffRec(node.getLeft(), num);
int leftMinFromValue = findMinimalDiffRec(node.getLeft(), node.getValue());
int minLeftTemp = Math.min(leftMinFromNum, leftMinFromValue);
int minLeftResult = Math.min(minLeftTemp, diffFromValue);

if (node.getRight() != null) {
int rightMinFromNum = findMinimalDiffRec(node.getRight(), num);
int rightMinFromValue = findMinimalDiffRec(node.getRight(), node.getValue());
int minRightTemp = Math.min(rightMinFromNum, rightMinFromValue);
int minRightResult = Math.min(minRightTemp, diffFromValue);

return Math.min(minLeftResult, minRightResult);
}

return minLeftResult;
}

if (node.getRight() != null) {
int rightMinFromNum = findMinimalDiffRec(node.getRight(), num);
int rightMinFromValue = findMinimalDiffRec(node.getRight(), node.getValue());
int minRightTemp = Math.min(rightMinFromNum, rightMinFromValue);
return Math.min(minRightTemp, diffFromValue);
}

return diffFromValue;
}

public static int findMinimalDiff(Node node) {
if (node == null) {
return NOT_FOUND;
}

if (node.getLeft() == null && node.getRight() == null) {
return node.getValue();
}

if (node.getLeft() == null) {
return findMinimalDiffRec(node.getRight(), node.getValue());
}

if (node.getRight() == null) {
return findMinimalDiffRec(node.getLeft(), node.getValue());
}

int leftMin = findMinimalDiffRec(node.getLeft(), node.getValue());
int rightMin = findMinimalDiffRec(node.getRight(), node.getValue());

return Math.min(leftMin, rightMin);
}

public static void main(String[] args) {
Tree tree = buildTree();
System.out.println(findMinimalDiff(tree.getRoot()));
}
}

class Node {
private int value;
private Node left;
private Node right;

public Node(int value) {
this.value = value;
this.left = null;
this.right = null;
}

public void setRight (Node right) {
this.right = right;
}

public void setLeft (Node left) {
this.left = left;
}

public Node getLeft() {
return left;
}

public Node getRight() {
return right;
}

public int getValue() {
return value;
}
}

class Tree {
private Node root;

public Tree(Node root) {
this.root = root;

}

public Node getRoot() {
return root;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.*;

class Node {
int val;
Node left,right;

Node(int x) {
val = x;
}
}

class minDiffTree {
public static void main(String args[]) {
Node x = new Node(10);
x.left = new Node(5);
x.right = new Node(16);
x.right.left = new Node(12);
x.right.right = new Node(20);
System.out.println(inorder(x));
}

public static int inorder(Node x) {
Stack<Node> s = new Stack();
int min = Integer.MAX_VALUE;
Node current = x;
Node prev = null;
while(true) {
if(current!=null) {
s.push(current);
current = current.left;
}
else if(!s.isEmpty()) {
current = s.pop();
if(prev!=null) {
int temp = Math.abs(current.val-prev.val);
if(temp<min) {
min = temp;
}
}
prev = current;
current = current.right;
}
else {
break;
}
}
return min;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````template<class T>
T Tree<T>::MinDiffInBST()
{
return m_root ? MinDiffInBST(m_root, nullptr) : -1;
}
template<class T>
T Tree<T>::MinDiffInBST(Node<T>* current, Node<T>* previous)
{
T min = LONG_MAX;
// Use In-Order traversal to find min diff between any 2 nodes
if (current) {
min = MinDiffInBST(current->Left(), current);
if (previous)
min = MIN(min, abs(current->Item() - previous->Item()));
min = MIN(min, MinDiffInBST(current->Right(), current));
}
return min;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right

def min_two_node_diff(tree):
if tree == None:
return float("inf")
compare_with_left, compare_with_right = float("inf"), float("inf")
if tree.left:
compare_with_left = tree.val - right_most_val(tree.left)
if tree.right:
compare_with_right = left_most_val(tree.right) - tree.val
return min(compare_with_left, \
compare_with_right, \
min_two_node_diff(tree.left), \
min_two_node_diff(tree.right))

def right_most_val(tree):
if (tree.right == None):
return tree.val
return right_most_val(tree.right)

def left_most_val(tree):
if (tree.left == None):
return tree.val
return left_most_val(tree.left)

bst = Node(10, Node(5), Node(16, Node(12), Node(20)))
print(min_two_node_diff(bst))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is O(n) solution. For every node, get min value for left sub tree and max value from right subtree. Check difference between node and min from left subtree. Calculate difference between node and max from right subtree.

``````static int min_diff = Integer.MAX_VALUE;

static int minDiff(Node root)
{
findMinMax(root);
return min_diff;
}

static int[] findMinMax(Node root) {
int[] val = new int[2];
int min = - 1, max = -1;
if (root.left != null) {
min = findMinMax(root.left)[0];
val[0] = min;
} else {
val[0] = root.val;
}
if (root.right != null) {
max = findMinMax(root.right)[1];
val[1] = max;
} else {
val[1] = root.val;
}
if (max > 0 && max - root.val < min_diff) min_diff = (max - root.val);
if (min > 0 && root.val - min < min_diff) min_diff = (root.val - min);
return val;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hello

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <stack>
#include <limits>
#include <algorithm>

struct Node {
Node() : left( NULL ), right( NULL ) {}

size_t val;
Node* left;
Node* right;
};

size_t minDiff( Node root ) {
std::stack<Node*> stack;
Node* n = &root;
Node* prev = NULL;
size_t min = std::numeric_limits<size_t>::max();

while ( !stack.empty() || n != NULL ) {
if ( n ) {
stack.push( n );
n = n->left;
}
else {
n = stack.top();
stack.pop();

if ( prev ) {
min = std::min( min, n->val - prev->val );
}
prev = n;

n = n->right;
}
}
return min;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

If we had a (sorted) list of integers, then the minimum difference between any two numbers in the list would necessarily be the smallest difference between two adjacent nodes.

In this case we don't have a list, however we can still visit a BST in sorted order through an in-order visit. This reduces the problem to keeping track of the minimum difference between every step of an in-order visit.

``````static Node prev;
int findMin(Node bst, int currentMin) {
if (bst == null) {
return currentMin;
}

currentMin = findMin(bst.left, currentMin);
if (prev != null) {
int diff = Math.abs(bst.value - prev.value);
if (diff < currentMin) {
currentMin = diff;
}
prev = node;
}
currentMin = findMin(bst.right, currentMin);

return currentMin;
}

int min = findMin(root, Integer.MAX_VALUE, null);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import numpy as np

class Node:
def __init__(self, val):
self.left = None
self.right = None
self.data = val
def insert(root, node):
if root is None:
root = node
else:
if (root.data > node.data):
if(root.left is None):
root.left = node
else:
insert(root.left, node)
else:
if(root.right is None):
root.right = node
else:
insert(root.right, node)

def postorder(root, nodes=[]):
if not root: return []

postorder(root.left)
nodes.append(root.data)
postorder(root.right)

return nodes

def solution(root):
nodes = postorder(root)
minim = np.inf
for i in range(len(nodes)-1):
tmp = nodes[i+1] - nodes[i]
if (tmp < minim):
minim = tmp
return minim``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.