Amazon Interview Question Software Engineer / Developers
Country: United States
Though this is gives a right result,it is not an efficient approach(i.e takes O(N) ).Use Divide and Conquer Solution for getting a result in O(logN)
@zuzu : The tree is BST, so searching a node require only O(log n) time, now once you have found that node, you need to find all the element. which require O(# element which lies in [a,b])
@sonesh, Have you thought about how you are going to do an inorder traversal starting from the middle of the tree? Are you going to have parent links or maintain kind of stack? Try coding this and I bet you'll see why this is a much better solution:
if tree is null, you're done
if min <= root, traverse left
if min <= root <= max, output root
if root <= max, traverse right
@showell: Sonesh has interpreted the question to get _all_ the nodes and not just _any_ node, so outputting just the root is not enough.
Good thing about this solution is it is composed of well known operations, Find and Successor, which will likely exist in implementations which support ordered iteration, and can be shown to be O(h + S) where h is the height of tree and S is the number of elements to be output.
Of course, the interviewer might ask you to implement those and might be looking for something simpler, in which case a modified version of showell's solution will work.
@Anonymous, the recursive calls to traverse make it so that you output _all_ the nodes. Change "output" to "visit" or "yield" to be more general.
@showell: Yes, there is no denying we can write the recursive version, but we do need to recurse both left and right in some cases, and not just one subtree (which you seemed to be implying).
The point is, sonesh's solution is not as bad as your comments seemed to imply (not claiming you actually did, just what it seemed). It is quite reasonable. In fact, in production code, that will probably be the one to use: simplicity and ease of maintenance etc, especially if the off-the-shelf supports ordered iteration.
Here is a working example of code that doesn't require any special operations from a binary tree other than "right" and "left."
def test():
lst = [1,2,3,4,4,5,6,7,7,7,8,9,10,11,12,13,14,15]
tree = create_tree(lst)
assert [4,4,5,6,7,7,7,8,9,10,11,12] == list(traverse_range(tree, 4, 12))
assert [] == list(traverse_range(tree, 16, 100))
assert lst == list(traverse_range(tree, 0, 100))
def traverse_range(tree, min, max):
def traverse(t):
if t is None:
return
left, root_val, right = t
if min <= root_val:
for v in traverse(left):
yield v
if min <= root_val <= max:
yield root_val
if root_val <= max:
for v in traverse(right):
yield v
for item in traverse(tree):
yield item
# In Python a simple way to represent a binary
# tree is as a tuple: (left_tree, val, right_tree)
def create_tree(lst):
def _maketree(low, high):
# Making a balanced tree is simply a matter
# of taking the middle value as the root
# and recursively building the subtrees
# on the left and right.
if low > high:
return None
if low == high:
return (None, lst[low], None)
mid = (low + high) / 2
val = lst[mid]
left = _maketree(low, mid - 1)
right = _maketree(mid + 1, high)
return (left, val, right)
return _maketree(0, len(lst) - 1)
test()
@Anonymous, of course there are occasions where you traverse both subtrees. Nothing in my answer implied otherwise. If @sonesh's approach is easy, then somebody should post the code.
@showell, Your using yield like that could make it potentially Omega(h(h+s)), and not O(h + S) (i.e. an extra multiplicative factor of the height).
As for the "easy" code, assuming there is a find and successor implemented by the underlying tree, it could be as easy as
/// C++ like code.
RangeVisit(const Tree<T> &tree, T a, T b, Visitor &v) {
auto it = tree.find(a); // finds element of tree >= a
while (it != tree.end() && *it <= b) {
v.Visit(*it);
it++; // Successor
}
}
The above code is probably much more easier to debug/maintain that a custom recursive implementation.
Of course, for an interview the interviewer would probably say successor is not available, as they actually want you to write some "reasonable amount" of code, which they can judge. Or perhaps their next question would be to discuss how such an iterator/successor/find can be implemented... Of course, depends on the interviewer.
Debating which solution is better is quite pointless without the context.
There is no multiplicative factor for height in my algorithm. Even in the worst-case scenario, where the tree is completely vertical, it visits every node once, for a running time of 2H. I have no idea where you're getting the H-squared from.
People often implement BSTs without parent pointers to save space and maintenance overhead. Without parent pointers, it's tough to write a successor function. With parent pointers and/or some other storage scheme that allows for a reasonable successor function, I see the merits of your solution.
@showell: Think about how yield is actually implemented by the compiler/interpreter.
Perhaps it is not applicable to python (hence the usage of the word "potentially"), but the C# version would have problems. Read this:
stackoverflow. com/questions/3969963/when-not-to-use-yield-return
See the answer by Eric Lippert.
btw, you don't need parent pointers to implement successor. Of course you would need some auxiliary storage like a stack, but that can be made O(h), just like your recursive version.
Ok, I think I see what you mean. Let's say you have a pretty deep tree, say 1M elements and about 20 deep. All the elements in the bottom layer require 20 touches before they're finally yielded. Python does have a "yield from" in recent versions, I believe, that prevents this problem. In earlier versions, I would just change the code to pass in a visitor function to collect the elements.
There's a PEP called "Syntax for Delegating to a Subgenerator" that's been accepted in Python, but I'm not sure if they actually optimise for the delegated-yield issue.
@showell30 : I think you guys have wrote enough already, but I just wanna say that First : to find a node in BST does not require a stack, secondly once we found such node, consider that node as root node and apply our inorder algorithm.(Inorder algorithm only require a node and nothing else about tree)
@sonesh. Yes to find the first node we don't need a stack. But you are mistaken about rooting the tree at the node found. I suggest you rethink.
(Of course, there are tree versions like threaded trees where you don't need a stack or extra space to be able to find the successor...)
@sonesh: Consider the tree 1 <- 2 -> 3. If you want to find numbers in the range 1 to 3 (inclusive), then your algorithm will first find 1 as the root. An inorder traversal with 1 as the root won't get you back to 2 and 3, unless you have parent pointers or a stack. It's really that simple.
@showell :
If tree is
2
/\
1 3
and i need to find nodes between 1 and 3, then the root node which is 2 is the node from where we start in order algo.
if tree is
6
/ \
4 8
/ \ / \
2 5 7 10
Now in this question if the range is [1 5] then at root node which 6 in not belong to [1,5] and is greater then 5, so we go left, Now 4 is in [1,5], so we consider 4 as root and start inorder traveling
How ?
Here is how, If we consider 4 as root, then the new tree is
4
/ \
2 5
so we can see that all 2,4,5 are inside [1,5].
Divide and Conquer Solution:
If the tree is empty, return not found. If min <= root <= max, then return root. If root < min, recursively search the right subtree. Otherwise, recursively search the left subtree.
Assuming the tree is balanced, this runs in O(log N) time, vs. O(N) time for an inorder traversal.
It's reasonable to assume that the interviewer is talking about a balanced binary tree, even though the question doesn't explicitly state it. Even for a horribly imbalanced tree, this approach is better than a naive inorder traversal.
Interviewers actually don't take kindly to unnecessary assumptions... just say O(h) instead of O(log N), then discuss that random binary trees have expect h = O(log N) etc.
You don't have to assume balanced...
This is not correct answer.
suppose BST contains numbers from 20 to 30. Suppose [min, max] = [19, 31].
1. first problem is that it will return from the root itself.
2. your solution will go to the else part and recursively search the left subtree.
Instead of printing the whole tree, your solution will print only the left sub tree from the tree root.
Down voted !!
I agree with Vinod...
It actually doesn't matter if the tree is BST or not. If min value is less than the least value of the BST and max value if greater than the greatest value in the BST, all the nodes in the BST would have to be visited. Hence, the worst case running time should be O(n)...
@Vinod, Read the awkwardly worded question again and you'll see that's it's a valid interpretation to find just one element in the range. It says "print the node," which suggests you're just trying to find one match.
@Rahul, The long thread on this page that starts with "find the first one" has a detailed discussion of the running times for two different implementations, using the interpretation that you have to report all values in the range, not just one.
Python Iterative Search.
This code avoids recursion by maintaining its own stack. It's an inorder traversal of the tree, but it only yields elements that are within range, and it short circuits traversing the parts of the tree that are out of range, as well as short circuiting stack pushes for parts of the tree that are more than max.
def traverse_range(tree, min, max):
stack = []
while tree or stack:
if tree:
left, val, right = tree
if val <= max:
stack.append(tree)
tree = left
if val < min:
tree = None
else:
tree = stack.pop()
left, val, right = tree
if val > max:
return
if min <= val:
yield val
tree = right
I have done simple in-order traversal with additional return condition.
bst_print_range(root r, int lo , int max)
{
if(r==NULL || r->data < lo || r-> data > max)
return ;
bst_print_range(r->left,lo,max);
print("%d",r->data);
bst_print_range(r->right,lo,max);
}
C++ lazy iterator using stack. Since C++ does not have yield, it is trickier to provide the lazy iteration. (note, quick proof-of-concept code, so not exemplary and probably buggy).
The stack invariant is that the from bottom to top (along the stack), the nodes are from the path starting at the root to the top node (in the tree), but only those nodes which are of value >= the value of the top node.
Even though the code looks verbose, the core are moveToFirst and next, which are quite simple to code up, actually.
#include "tree.h" // Tree definition.
#include <stack>
#include <iostream>
using std::stack;
// Won't bother with making this generic.
// implements JAVA style iterator hasNext and next.
class BSTRangeIterator {
public:
BSTRangeIterator(Tree *t, int l, int u) {
_tree = t;
_lower = l;
_upper = u;
if (_tree == NULL) {/*throw*/;}
if (_upper < _lower) {/*throw*/;}
moveToFirst();
}
bool hasNext() {
if (_stack.empty()) return false;
Tree *next = pop();
if (next->Value > _upper) {
return false;
}
push(next);
return true;
}
int next() {
if (!hasNext()) {
// throw
}
Tree *top = pop();
Tree *right = top->Right;
int val = top->Value;
while (right != NULL) {
if (right->Value <= _upper) {
push(right);
}
right = right->Left;
}
return val;
}
private:
// Moves to smallest element >= _lower.
// Stack contains path to the required element
// Only elements >= _lower are on the stack.
void moveToFirst() {
push(_tree);
while (!_stack.empty()) {
Tree *cur = pop();
if (cur == NULL) {
return;
}
if (_lower > cur->Value) {
push(cur->Right);
} else {
push(cur);
push(cur->Left);
}
}
}
void push(Tree *t) {
_stack.push(t);
}
Tree *pop() {
Tree *top = _stack.top();
_stack.pop();
return top;
}
Tree *_tree;
int _lower;
int _upper;
stack <Tree *> _stack;
};
void Test(Tree *t, int l, int u, int start, const char *message) {
std::cout << message << ":";
BSTRangeIterator iter(t, l,u);
int expected = start;
bool failed = false;
while(iter.hasNext()){
int cur = iter.next();
if (cur != expected) {
failed = true;
break;
}
expected++;
std::cout << " " << cur << ",";
}
if (failed) {
std::cout << " Failed\n";
} else {
std::cout << " Passed\n";
}
}
int main(int argc , char **argv) {
int values[] = {15,1,4,8,7,2,3,6,9,10,11,12,13,14,5,16,17,18,19,20};
int len = sizeof(values)/sizeof(int);
Tree *t = NULL;
for (int i = 0; i < len; i++) {
if (t == NULL) {
t = new Tree(values[i]);
}else {
t->Insert(values[i]);
}
}
Test(t, 5, 14,5, "Left Only");
Test(t, 16, 20,16, "Right Only");
Test(t, -1,15,1, "Left incl root");
Test(t, 15,111,15, "Right incl root");
Test(t, -1, 1000, 1, "All");
}
class TreeNode {
int val;
TreeNode leftchild;
TreeNode rightchild;
public TreeNode(int val) {
this.val = val;
leftchild = null;
rightchild = null;
}
}
public class Solution {
public static ArrayList<Integer> search(TreeNode root, int max, int min) {
ArrayList<Integer> ret = new ArrayList<Integer>();
if (root == null || max < min) {
return ret;
}
traverse(root, max, min, ret);
// binarySearch(root, max, min, ret);
return ret;
}
private static void traverse(TreeNode root, int max, int min, ArrayList<Integer> ret) {
if (root == null) return;
traverse(root.leftchild, max, min, ret);
if (root.val>=min && root.val<=max) {
ret.add(root.val);
}
traverse(root.rightchild, max, min, ret);
}
private static void binarySearch(TreeNode root, int max, int min, ArrayList<Integer> ret) {
if (root == null) return;
if (root.val < min) binarySearch(root.rightchild, max, min, ret);
else if (root.val > max) binarySearch(root.leftchild, max, min, ret);
else {
ret.add(root.val);
binarySearch(root.rightchild, max, min, ret);
binarySearch(root.leftchild, max, min, ret);
}
}
}
Print left first, then mine, then right so order is preserved in printing.
void printRange( TreeNode *root, int min, int max ) {
if ( root == NULL ) return;
if ( root->data > min ) {
printRange( root->left, min, max );
}
if ( ( root->data > min ) && (root->data < max) ) {
std::cout << root->data << ",";
}
if (root->data < max) {
printRange( root->right, min, max);
}
}
It doesn't work if (min & max ) < root->data || > root->data
Here range must be min < root < max like this.
I think this is not a target solution, Can u improve it.
This method prints the first node , whose value lies between i and j
private void findNodeBetweenValues(Node node ,int i, int j) {
if(i > j){
throw new IllegalArgumentException();
}
if(node.data > i && node.data < j){
System.out.println("value between "+i+" & "+j+" is "+this.root.data);
}else if(node.data < i){
findNodeBetweenValues(node.left,i,j);
}else if(node.data > j){
findNodeBetweenValues(node.right,i,j);
}
}
public Node findNode(Node root, int max, int min){
if(root == null) throw new RuntimeException("Tree root null");
Node currNode;
// doing a DFS approach
Queue<Node> queue = new LinkedList<Node>();
queue.enqueue(root);
while(!queue.isEmpty()){
currNode = queue.dequeue();
if(currNode.data > min && currNode.data< max){
return currNode;
}
else{
if(currNode.left != null && currNode.data > max)
queue.enqueue(currNode.left);
if(currNode.right != null && currNode.data < min)
queue.enqueue(currNode.right);
}
}
return null;
}
void PrintRange(struct tNode *root, int min, int max){
if (root == NULL)
return;
else if (min <= root->data && root->data <= max) {
PrintRange(root->left, min, max);
printf("root->data: %d \t", root->data);
PrintRange(root->right, min, max);
}
else if (root->data < min)
{
if (root->right)
PrintRange(root->right, min, max);
else
printf("no element in range \n");
}
else if (root->data > max) {
if (root->left)
PrintRange(root->left, min, max);
else
printf("no element in range \n");
}
}
Solution :
step 1 :
- sonesh February 23, 2013