Google Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
At each node in the BST, store the order value at that node ( the 4th smallest node in the tree stores 4, the smallest stores 1, etc.) according to the ordering on the BST. Then, for a interval range (i,j), i <= j, navigate to the smallest element great than i. Let this element's order value be A. Navigate to the largest element less than j and let it's order value be B. Return B - A.
Note: If we use a balanced BST (Treap, AVL Tree) this solution is O(log(n)). Otherwise the solution is O(n).
Unlike the previous answer, this approach tries to optimize the search by not travelling to completely redundant sub-trees.For example, when range is 15-25 and our root is 10, searching left sub-tree would be a waste.
class Node:
def __init__(self,v):
self.v=v
self.left=None
self.right=None
def nodesInRange(a,b,root):
if root==None: return []
ans=left=right=[]
if a<=root.v<=b: ans=[root]
if root.v>a:
left=nodesInRange(a,min(root.v-1,b),root.left)
if root.v<b:
right=nodesInRange(max(root.v,a),b,root.right)
return ans+left+right
Unlike the previous answer, this approach tries to optimize the search by not travelling to completely redundant sub-trees. For example, when range is 15-25 and our root is 10, it would be a waste to search left sub-tree.
class Node:
def __init__(self,v):
self.v=v
self.left=None
self.right=None
def nodesInRange(a,b,root):
if root==None: return []
ans=left=right=[]
if a<=root.v<=b: ans=[root]
if root.v>a:
left=nodesInRange(a,min(root.v-1,b),root.left)
if root.v<b:
right=nodesInRange(max(root.v,a),b,root.right)
return ans+left+right
abstract class Tree {
int value;
}
class Node extends Tree{
Tree left;
Tree right;
}
class Leaf extends Tree {
}
void printNodesInRange(Tree t, int from /* inclusive */, int to /* inclusive */) {
// if this is a leaf node, then just test if value is within the range
if (t instanceof Leaf) {
if (t.value >= from && t.value <= to) {
println (t.value);
}
}
else {
Node n = (Node)t;
if (n.value < from) {
// search only right subtree
printNodesInRange(n.right, from, to);
}
else if (n.value > to) {
// search only left subtree
printNodesInRange(n.left, from, to);
}
else {
// search both left and right with divided range
printNodesInRange(n.left, from, n.value);
printNodesInRange(n.right, n.value, to);
}
}
}
O(n) simple in-order traversal with conditions solution
public static void CountNodesInRange(TreeNode tree, int low, int high, ref int count)
{
if (tree == null)
return;
if (tree.Value >= low)
CountNodesInRange(tree.Left, low, high, ref count);
if (tree.Value >= low && tree.Value <= high)
count++;
if (tree.Value <= high)
CountNodesInRange(tree.Right, low, high, ref count);
}
Can be solved using level order traversal in O(n) time.
private static int getCountBetweenRange(Node root, int min, int max){
if (root == null) {
return 0;
}
Queue<Node> helperQueue = new LinkedList<Node>();
helperQueue.add(root);
int count =0;
while(!helperQueue.isEmpty()){
Node temp = helperQueue.remove();
if(temp.data>= min && temp.data<=max){
count++;
}
if (temp.left != null) {
helperQueue.add(temp.left);
}
if (temp.right != null) {
helperQueue.add(temp.right);
}
}
return count;
}
We can do this simply by augmenting a tree node with the total number of nodes in the sub-tree rooted by the given node.
Pseudo code for doing this is:
The auxiliary method implementations are:
Those are test results
- linuxchain August 10, 2016