Google Interview Question
SDETsCountry: United States
Referring to above solution, LBorder value may or may not be the top node of subtree having all the values less than x and similarly RBorder value may or may not be the top most node of subtree holding all values larger than y. Above algorithm will fail in this scenario.
Worst case complexity of this solution is O(n), but it may take much less time depending on tree structure.
public static void parseTree(Node n, int start, int end, int count) {
if(node == null)
return;
if(node.value < start)
parseTree(n.right, start, end, count);
else if(node.value > end)
parseTree(n.left, start, end, count);
else {
count++;
parseTree(n.left, start, end, count);
parseTree(n.right, start, end, count);
}
}
rit, could you provide an example where the algorithm fails?
I provide my examples. In a BST bellow each node contains a number and count in braces.
____________8(10)____________
| |
____4(6)____ ____10(3)____
| | | |
_2(3)_ 6(2)_ 9(1) 12(1)
| | |
1(1) 3(1) 7(1)
Some test cases:
[x, y]: [2, 6]
A: 4(6)
LBound: 1(1)
RBound: 7(1)
Result: 6-1-1=4
[x, y]: [2, 12]
A: 8(10)
LBound: 1(1)
RBound: NULL
Result: 10-1-0=9
____________8(10)____________
| |
____4(6)____ ____10(3)____
| | | |
2(3)_ 6(2)_ 9(1) 12(1)
| |
3(1) 7(1)
I think your approach fails at Test Case:
[x,y] = [3,6]
Your solution considers node 2's count to be excluded from the result, but node 3 should be included.
____________8(10)____________
| |
____4(6)____ ____10(3)____
| | | |
2(3)_ 6(2)_ 9(1) 12(1)
| |
3(1) 7(1)
I think your approach fails at Test Case:
[x,y] = [3,6]
Your solution considers node 2's count to be excluded from the result, but node 3 should be included.
function bfs(G, v, x, y) {
var Q = [];
var S = [];
var count = 0;
Q.enqueue = Q.unshift
Q.dequeue = Q.pop;
Q.enqueue(v);
v.visited = true;
while (Q.length) {
v = Q.dequeue();
if (v.left && !v.left.visited) {
if (v.value > x) {
Q.enqueue(v.left);
}
v.left.visited = true;
}
if (v.right && !v.right.visited) {
if (v.value < y) {
Q.enqueue(v.right);
}
v.right.visited = true;
}
S.push(v);
}
while (S.length) {
v = S.pop();
var left = !v.left;
if (v.left) {
left = v.left.value > x && v.left.itCounts;
}
var right = !v.right;
if (v.right) {
right = v.right.value < y && v.right.itCounts;
}
v.itCounts = left && right;
if (!v.left && !v.right) {
if (v.value <= x || v.value >= y) {
v.itCounts = false;
}
}
if (v.itCounts) {
count++;
}
}
return count;
}
var Node = function (value) {
this.value = value;
};
var four = new Node(4);
var two = new Node(2);
var seven = new Node(7);
var one = new Node(1);
var three = new Node(3);
var five = new Node(5);
var six = new Node(6);
four.left = three;
two.right = four
two.left = one;
five.left = two;
seven.left = six;
five.right = seven;
console.log(bfs(null, five, 0, 5));
/// <solution>
/// For each node , if we know right and left sub tree satisfy the criteria, we increment the count.
/// If self node also satisfy the criteria we retun true to parent node to account that for counting
/// Algoritham: Traverse each node's left and right child recursively to know the min Left child and max Right child value.
/// If the min and max value are in the range [x,y] we increase count by one.
/// If self value is in range of [x,y] return true to parent that we all are in range
///
/// </solution>
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Testyourskills
{
/// <summary>
/// Problem:
/// Given a Binary search tree of integer values, return the count of nodes where
/// all the nodes under that sub-tree lies between a given range [x, y].
/// Assume there are more than 100,000 nodes
/// </summary>
///
/// <solution>
/// For each node , if we know right and left sub tree satisfy the criteria, we increment the count.
/// If self node also satisfy the criteria we retun true to parent node to account that for counting
/// Algoritham: Traverse each node's left and right child recursively to know the min Left child and max Right child value.
/// If the min and max value are in the range [x,y] we increase count by one.
/// If self value is in range of [x,y] return true to parent that we all are in range
///
/// </solution>
/// <author>
/// Pramod Kumar Chandoria
/// </author>
public class BSTNodeCountByRange
{
public static int CountNodeBySubTreeValueInGivenRange(Node tree, int minRange, int maxRange)
{
int count = 0;
recusiveCountNode(tree, minRange, maxRange, ref count);
return count;
}
private static bool recusiveCountNode(Node tree, int minRange, int maxRange, ref int count)
{
if (tree == null)
{
return true;
}
bool isLeft = recusiveCountNode(tree.left, minRange, maxRange, ref count);
bool isRight = recusiveCountNode(tree.right, minRange, maxRange, ref count);
if ( isLeft && isRight)
{
if (tree.left != null || tree.right != null) // This check to avoid counting leaf nodes
{
count++;
}
if (tree.data >= minRange && tree.data <= maxRange)
{
return true;
}
}
return false;
}
public static void Main(string[] args)
{
var count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(null, 100, 100);
Console.WriteLine("Null tree expected count 0, actual count is:" + count);
Node tree = new Node(5);
count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 1, 3);
Console.WriteLine("Tree with only 1 node (5) for range [1,3], expected 0, actual count is:" + count);
tree = new Node(4);
tree.left = new Node(2);
tree.right = new Node(6);
tree.left.left = new Node(1);
tree.left.right = new Node(3);
count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 1, 3);
Console.WriteLine("Tree (Preorder 4,2,1,3,6) with range [1,3], expected 1, actual count is:" + count);
count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 1, 6);
Console.WriteLine("Tree (Preorder 4,2,1,3,6) with range [1,6], expected 1, actual count is:" + count);
count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 6, 6);
Console.WriteLine("Tree (Preorder 4,2,1,3,6) with range [1,6], expected 0, actual count is:" + count);
tree = new Node(20);
tree.left = new Node(10);
tree.right = new Node(25);
tree.left.left = new Node(5);
tree.left.right = new Node(16);
tree.left.right.left = new Node(14);
tree.left.right.right = new Node(18);
tree.right.left = new Node(24);
tree.right.right = new Node(30);
tree.right.right.left = new Node(28);
tree.right.right.right = new Node(40);
tree.right.right.right.left = new Node(35);
tree.right.right.right.right = new Node(45);
count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 24, 45);
Console.WriteLine("Tree with range [24, 45], expected count is 3, actual count is:" + count);
count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 35, 45);
Console.WriteLine("Tree with range [35, 45], expected count is 1, actual count is:" + count);
count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 14,18);
Console.WriteLine("Tree with range [14, 18], expected count is 1, actual count is:" + count);
count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 5, 18);
Console.WriteLine("Tree with range [5, 18], expected count is 2, actual count is:" + count);
count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 4, 46);
Console.WriteLine("Tree with range [4, 46], expected count is 6, actual count is:" + count);
}
}
public class Node
{
public Node(int data)
{
this.data = data;
left = right = null;
}
public Node left;
public Node right;
public int data;
}
}
public int countNodesBetweenRange(NodeB root, int l, int r) {
if (root == null) {
return 0;
} else if (root.val >= l && root.val =< r) {
return 1 + countNodesBetweenRange(root.left, l, r) +
countNodesBetweenRange(root.right, l, r);
} else if (root.val < l) {
return countNodesBetweenRange(root.right, l, r);
} else if (root.val > r) {
return countNodesBetweenRange(root.left, l, r);
}
return 0;
}
Imagine you want to search all nodes between range 4 - 6 , you start from Root of tree, it's value is 3, so now you know the only possible nodes between that range must be in the right side, if there are any, so return any counts you can find starting from the right child. The other case is the opposite, it's when the range is lower than the current root's value, so only possible nodes remains in the left side.
For the last two else conditions, is it not sufficient to check root.val < l for the first and root.val > r for the second? Since l <= r.
@JW You're right no need for the additional (v < l && v < r ) and ( v > l && v > r ) checks since we always will have l < r
the problem indicates that there are more than 100,000 so using recursive call may cause stack overflow , so I am using a stack to do inorder traverse , the time complexity is O(n)
public int getRange (TreeNode root, int x, int y){
int c = 0 ;
Stack<TreeNode> stack = new Stack<> ();
TreeNode cur = root ;
while (!stack.isEmpty() || cur != null) {
if (cur != null) {
stack.push(cur) ;
cur = cur.left ;
} else {
TreeNode tmp = stack.pop() ;
if (tmp.val >= x && tmp.val <= y) {
c++;
}
cur = tmp.right ;
}
}
return c ;
}
You're going to end up spending a linear amount of memory in both recursive and stack versions. I believe the memory footprint would be roughly equal.
you can put the additional condition (tmp.val >= x && tmp.val <= y) in while loop itself and let increment the counter at each push operation , this will reduce the unnecessary nodes traversal till the end.
But stack memory << main memory.
Stack memory can be around 64Kb per thread while main memory can be 4 Gb.
this will only enter the element that are in range on the stack
stack <TreeNode> s;
TreeNode temp = rootNode;
int sum = 0;
int nodeCount = 0;
while(!s.empty() || temp != null)
{
while(temp != null)
{
if(temp.data >= x && temp.data <= y)
{
nodeCount++;
sum=sum+temp.data;
if(temp.rightNode != null)
{
s.push(temp.rightNode);
}
temp=temp.leftNode;
}
else if(temp.data < x)
{
temp=temp.rightNode;
}
else if (temp.data >y)
{
temp=temp.leftNode;
}
}
if(!s.empty())
{
temp = s.top();
s.pop();
}
}
}
#include <iostream>
#include <stack>
using namespace std;
template <class T>
class Node{
public:
Node *left, *right;
T value;
Node(T v):value(v),left(NULL),right(NULL) {}
};
template <class T>
int countNodesInRange(Node<T> *root, T l, T r)
{
if(root == NULL)
return 0;
stack<Node<T>*> s;
int count = 0;
s.push(root);
while(!s.empty())
{
Node<T>* temp = s.top();
s.pop();
if(temp->value >= l && temp->value <= r)
{
count++;
if(temp->right != NULL)
{
s.push(temp->right);
}
if(temp->left != NULL)
{
s.push(temp->left);
}
}
else if(temp->value < l)
{
if(temp->right != NULL)
{
s.push(temp->right);
}
}
else if (temp->value > r)
{
if(temp->left != NULL)
{
s.push(temp->left);
}
}
}
return count;
}
int main() {
Node<int> A(5),B(3),C(7);
A.left = &B;
A.right = &C;
cout << "[1,9]=" << countNodesInRange(&A,1,9) << endl;
cout << "[1,6]=" << countNodesInRange(&A,1,6) << endl;
cout << "[4,9]=" << countNodesInRange(&A,4,9) << endl;
cout << "[4,6]=" << countNodesInRange(&A,4,6) << endl;
cout << "[1,4]=" << countNodesInRange(&A,1,4) << endl;
cout << "[6,9]=" << countNodesInRange(&A,6,9) << endl;
cout << "[1,2]=" << countNodesInRange(&A,1,2) << endl;
cout << "[8,9]=" << countNodesInRange(&A,8,9) << endl;
return 0;
}
#include <iostream>
#include <stack>
using namespace std;
template <class T>
class Node{
public:
Node *left, *right;
T value;
Node(T v):value(v),left(NULL),right(NULL) {}
};
template <class T>
int countNodesInRange(Node<T> *root, T l, T r)
{
if(root == NULL)
return 0;
stack<Node<T>*> s;
int count = 0;
s.push(root);
while(!s.empty())
{
Node<T>* temp = s.top();
s.pop();
if(temp->value >= l && temp->value <= r)
{
count++;
if(temp->right != NULL)
{
s.push(temp->right);
}
if(temp->left != NULL)
{
s.push(temp->left);
}
}
else if(temp->value < l)
{
if(temp->right != NULL)
{
s.push(temp->right);
}
}
else if (temp->value > r)
{
if(temp->left != NULL)
{
s.push(temp->left);
}
}
}
return count;
}
int main() {
Node<int> A(5),B(3),C(7);
A.left = &B;
A.right = &C;
cout << "[1,9]=" << countNodesInRange(&A,1,9) << endl;
cout << "[1,6]=" << countNodesInRange(&A,1,6) << endl;
cout << "[4,9]=" << countNodesInRange(&A,4,9) << endl;
cout << "[4,6]=" << countNodesInRange(&A,4,6) << endl;
cout << "[1,4]=" << countNodesInRange(&A,1,4) << endl;
cout << "[6,9]=" << countNodesInRange(&A,6,9) << endl;
cout << "[1,2]=" << countNodesInRange(&A,1,2) << endl;
cout << "[8,9]=" << countNodesInRange(&A,8,9) << endl;
return 0;
}
I guess we need to read the problem again. All nodes in that subtree should be in range.
Here is my code that returns 3 for this example with range[2,6] (which I believe is the right answer).
____________8_____________
| |
___5____ ______10____
| | | |
_3_ 6_ 9 12
| | |
2 4 7
public class SameInorder {
static int count;
static int start;
static int end;
private static boolean inRange(Node root) {
if (root == null)
return true;
if ((int) root.data > end) {
if (root.left == null && root.right == null)
return false;
return inRange(root.left);
}
if ((int) root.data < start) {
if (root.left == null && root.right == null)
return false;
return inRange(root.right);
} else {
boolean r = inRange(root.right);
boolean l = inRange(root.left);
if (r && l) {
count++;
return true;
}
return false;
}
}
public static void main(String[] args) {
count = 0;
start = 2;
end = 6;
Node tree = new Node(8);
{
tree.setLeft(5);
{
tree.left.setLeft(3);
{
tree.left.left.setLeft(2);
tree.left.left.setRight(4);
}
tree.left.setRight(6);
{
tree.left.right.setRight(7);
}
}
tree.setRight(10);
{
tree.right.setRight(12);
tree.right.setLeft(9);
}
}
if (inRange(tree))
count++;
System.out.println(count);
}
}
I think we need to read the question again. All nodes in subtree of counting nodes should be in range. Here is my code that returns 3 for this tree with range[2,6] which I believe is the right answer:
____________8____________
| |
__5____ ____10____
| | | |
_ 3_ 6_ 9 12
| | |
2 4 7
Code:
public class SameInorder {
static int count;
static int start;
static int end;
private static boolean inRange(Node root) {
if (root == null)
return true;
if ((int) root.data > end) {
if (root.left == null && root.right == null)
return false;
return inRange(root.left);
}
if ((int) root.data < start) {
if (root.left == null && root.right == null)
return false;
return inRange(root.right);
} else {
boolean r = inRange(root.right);
boolean l = inRange(root.left);
if (r && l) {
count++;
return true;
}
return false;
}
}
public static void main(String[] args) {
count = 0;
start = 2;
end = 6;
Node tree = new Node(8);
{
tree.setLeft(5);
{
tree.left.setLeft(3);
{
tree.left.left.setLeft(2);
tree.left.left.setRight(4);
}
tree.left.setRight(6);
{
tree.left.right.setRight(7);
}
}
tree.setRight(10);
{
tree.right.setRight(12);
tree.right.setLeft(9);
}
}
if (inRange(tree))
count++;
System.out.println(count);
}
}
Suppose, we are allowed to precompute & strore some info in the tree data struct.
Once done, we can handle many queries with O(logN) time.
We precompute the # of inorder successors for each node. This could be done
with postorder traversal:
struct node {
int val; // BST value
int sum; // # of inorder successors
node *left; // children
node *right;
};
// returns # nodes in a subtree
//! for each node compute the number of inorder successors in the tree
int inorder_sum(node *x, int right_sum) {
if(x == 0)
return 0;
int tmp = inorder_sum(x->right, right_sum);
x->sum = tmp + 1 + right_sum;
tmp += inorder_sum(x->left, x->sum);
return tmp + 1;
}
inorder_sum(root, 0);
Then, for each "range query" we just need to find 2
nodes 'xleft' and 'xright' that mark the boundaries of the given interval [vmin; vmax]:
node *xleft = 0, *xright = 0;
void find_subtree(node *x, int vmin, int vmax) {
if(x == 0)
return;
if(vmin <= x->val && x->val <= vmax) {
// we know that this node lies within the interval =>
// could improve the bounds if needed
if(xleft == 0 || xleft->val > x->val)
xleft = x;
if(xright == 0 || xright->val < x->val)
xright = x;
find_subtree(x->left, vmin, x->val);
find_subtree(x->right, x->val, vmax);
} else if(x->val > vmax) { // no need to explore right subtree
find_subtree(x->left, vmin, vmax);
} else { // x->val < vmin => no need to expolore left subtree
find_subtree(x->right, vmin, vmax);
}
}
find_subtree(root, vmin, vmax);
if(xleft != 0 && xright != 0) {
printf("# of nodes: %d\n",
xleft->sum - xright->sum + 1);
}
Simplest approach is, find node (lt) having data just immediate >= X (O(log(n))), similarly, find node (rt) with data just immediate <= Y (O(log(n))). Now, simply do in order traversal from lt to rt and count if node is in between[X, Y]. Total worst case complexity would be (O(n + 2log(n))).
function countNodes(root, lb, rb) {
if (root === null) {
return 0;
}
if (root.val < lb) {
return countNodes(root.right, lb, rb);
}
if (root.val > rb) {
return countNodes(root.left, lb, rb);
}
return 1 + countNodes(root.left, lb, rb) + countNodes(root.right, lb, rb);
}
small tweak needed in inorder code..
public static int inorder(Node root, int lbound, int ubound){
Int count=new Int();
// short-circuit to get new root
while(root.data<lbound){
root=root.rightChild;
}
inorder(root, count, lbound, ubound);
return count.val;
}
public static void inorder(Node root, Int count, int lbound, int ubound){
if(root==null){
return;
}
// Left
inorder(root.leftChild, count, lbound, ubound);
// Data with short-circuit
if(root.data>= lbound){
if(root.data > ubound){
return;
}
else{
count.val++;
}
}
// Right
inorder(root.rightChild, count, lbound, ubound);
}
private static class Int{
int val;
Int(){this(0);}
Int(int val){
this.val=val;
}
}
The problem states that all the nodes in the sub-tree should be within the specified range. So we can't just do a simple traversal and count every node within the range.
We count the nodes that are within range for the left tree and then the right tree.
The catch is that if we find any invalid nodes within the tree, then the results returned by the function will be zero.
We can use the BST property (left <= current < right) to help save some time.
I am maintaining the results outside the function which is bad but it can be fixed by having a private Result class.
int maxcount = 0;
Node rootedat = null;
public int countRange(Node node, int x, int y, int min, int max) {
if( x > max || y < min || node == null ) return 0;
int lCount = countRange( node.lChild, x, y, min, node.data);
int rCount = countRange( node.rChild, x, y, node.data+1, max);
// if the left or right subtree are not null, they should return a non-zero number of
// nodes if all the nodes match the criteria. If return is zero, something is out of range.
if( node.lChild != null && lCount == 0 || node.rChild != null && rCount == 0 ) return 0;
int count = 0;
if( x <= node.data && node.data <= y) {
count = lCount + rCount + 1;
if( count > maxcount ) {
maxcount = count;
rootedat = node;
}
}
return count;
}
To solve this , we need an augmented data structure. where at each node(r) of BST, we maintain the number of nodes in the subtree rooted at r.(refer
page 340 CLRS). Now given a range first we try to reach to a node(n) such that x<=n<y. ie node lies between the given range. this can be done recursively.
Total nodes lying in the range = nodes > x on the left subtree rooted at n + nodes < y on the right subtree rooted at y + 1 ( the root node, n)
(part 1) (part2)
to calculate part1:
1. start from node n
2. if x < n, go left other wise go right
3. while travering the BST if you find a node greater than x the keep a running count of node->right->size +1
4. continue this procedure till the search terminates.
to calculate part2:
everything remains same, except step 3
3. while travering the BST if you find a node less than x the keep a running count of node->left->size +1
Finally total = part1 + part2 + 1
Comments/Issues ?
If we can modify each node in BST, it is easy; but I am not sure about this since the size of BST is huge (more than 0.1 million).
Step 1. For each node, we add (min:minimum of subtree where root is this node, max:maximum of subtree where root is this node, count:# of all nodes in the subtree)
Step 2. Do breadth-first search from root to find a node (i.e., sub-tree) where x <= min and max <= y, and return this node's count.
For step 1, the data structure looks like this
E.g., Node (min, max, count)
2 (1, 3, 2)
1 (1, 1, 1) 3 (3,3,1)
and recursively update min, max, count by in-order traverse
For step 2, BFS will work for finding the largest subtree that satisfies the condition (i.e., all sub nodes should be between x and y).
public int rangeCount(T lo, T hi){
if(lo==null || hi==null || this.root==null){
return 0;
}
return rangeCount(this.root, lo, hi);
}
private int rangeCount(Node n, T lo, T hi){
if(n==null)
return 0;
int temp=0,leftCount=0,rightCount=0;
if(min(n).data.compareTo(lo)>=0 && max(n).data.compareTo(hi)<=0){
return n.count;
}
if(n.data.compareTo(lo)>=0 && n.data.compareTo(hi)<=0)
temp++;
if(n.data.compareTo(lo)>=0)
leftCount = rangeCount(n.left, lo, hi);
if(n.data.compareTo(hi)<=0)
rightCount=rangeCount(n.right, lo, hi);
return temp+leftCount+rightCount;
}
public int rangeCount(T lo, T hi){
if(lo==null || hi==null || this.root==null){
return 0;
}
return rangeCount(this.root, lo, hi);
}
private int rangeCount(Node n, T lo, T hi){
if(n==null)
return 0;
int temp=0,leftCount=0,rightCount=0;
if(min(n).data.compareTo(lo)>=0 && max(n).data.compareTo(hi)<=0){
return n.count;
}
if(n.data.compareTo(lo)>=0 && n.data.compareTo(hi)<=0)
temp++;
if(n.data.compareTo(lo)>=0)
leftCount = rangeCount(n.left, lo, hi);
if(n.data.compareTo(hi)<=0)
rightCount=rangeCount(n.right, lo, hi);
return temp+leftCount+rightCount;
}
Is it possible to store additional data with tree node? If so, we can store "count" field in the node that holds the number of elements in the subtree including this element. Then the algorithm can be:
- Ivan April 24, 20151. Find the node A where x <= A <= y.
2. Find the biggest node that is less than x in the A->left subtree. Lets call it LBorder.
3. Find the smallest node that is greater than y int the A->right subtree. Lets call it RBorder.
4. The result is: A->count - LBorder->count - RBorder->count.
The complexity is O(log N).
If it is not possible to store additional info I am afraid the complexity cannot be better than O(N), but it's quite easy and not interesting :).