Google Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
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)
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()
def addNodes(self, nList):
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]
self.tested.add((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)
myBST.addNodes(aList)
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
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;
}
#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;
}
#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;
}
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;
}
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.
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;
}
}
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;
}
}
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;
}
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))
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;
}
#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;
}
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);
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
after calling this function, "minDiff" will hold the minimum difference. O(n) time.
- ikoryf February 18, 2016