Google Interview Question Software Engineers
Country: 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:
int Tree::countRange(int start, int end) { // step1. find common root node of start and end Node *nroot = findCommonRoot(start, end); if(!nroot) return 0; // step2. get the number of nodes rooted by nroot int count = nroot->getNodeCnt(); // step3. subtract the nodes whose value is less than range start count -= countSmallerNode(nroot, start); // step4. subtract the nodes whose value is larger than range end count -= countLargerNode(nroot, end); return count; }The auxiliary method implementations are:
Node *Tree::findCommonRoot(int start, int end) { Node *nroot = dynamic_cast<Node*>(root); while(nroot){ if(end < nroot->getValue()) nroot = nroot->getLeft(); else if(start > nroot->getValue()) nroot = nroot->getRight(); else break; } return nroot; } int Tree::countSmallerNode(Node *nroot, int start) { int count = 0; Node *cur = nroot; while(cur){ if(start < cur->getValue()){ // take left cur = cur->getLeft(); } else { // all left nodes are smaller if(cur->getLeft()){ count += cur->getLeft()->getNodeCnt(); } if(start == cur->getValue()) break; // cur node is also smaller count++; // take right cur = cur->getRight(); } } return count; } int Tree::countLargerNode(Node *nroot, int end) { int count = 0; Node *cur = nroot; while(cur){ if(end > cur->getValue()){ // take right cur = cur->getRight(); } else { // all right nodes are larger if(cur->getRight()){ count += cur->getRight()->getNodeCnt(); } if(end == cur->getValue()) break; // cur node is larger count++; // take left cur = cur->getLeft(); } } return count; }Those are test results
- linuxchain August 10, 2016[TREE] 8 -12 14 -13 3 11 -15 -9 7 -10 -4 4 6 nodes in [-11, 5]: 5 nodes in [-16, -4]: 6 nodes in [-8, 1]: 1 nodes in [-9, 0]: 2 nodes in [6, 7]: 2 nodes in [3, 5]: 2 nodes in [-8, 12]: 7 nodes in [-3, 8]: 5 nodes in [-4, 8]: 6 nodes in [4, 2]: 0 nodes in [-15, 9]: 11 nodes in [-18, -6]: 5 nodes in [-2, 9]: 5 nodes in [-9, -5]: 1 nodes in [7, 9]: 2 nodes in [2, 12]: 6 nodes in [6, 13]: 4 nodes in [-9, -12]: 0 nodes in [9, 14]: 2 nodes in [-15, -8]: 5