Facebook Interview Question iOS Developers
Country: United States
Interview Type: In-Person
Binary Search Tree is not AVL tree. An AVL tree can be implemented as Balanced BST.
This was a question asked to my friend 1 week ago by Google recruiter
Q) Which one of these Data Structures have Log N traverse time
Red Black Tree
Binary Search Tree
Hash Table
Array
Directed Acyclic Graphs
He included BST in his answer which was wrong.
Watch out for these differences in interviews.
Are you sure it's "traverse" time?
Even for "retrieval" time, of course BST is not the answer since is doesn't have to be balanced.
But a AVL tree has to be a BST, except it's self-balancing.
AVL is a self-balancing BST by definition. You are right that BST is not AVL but question clearly tells its AVL tree, so we can use its BST property to do in-order traversal to get sorted values to find the median. The answer looks correct, I don't understand your comment. Can you kindly clarify more if am missing something.
@byteattack
AVL is a self-balancing BST by definition. You are right that BST is not AVL but question clearly tells its AVL tree, so we can use its BST property to do in-order traversal to get sorted values to find the median. The answer looks correct, I don't understand your comment. Can you kindly clarify more if am missing something.
For any balanced BST, maintain a count of number of nodes in its left sub-tree and number of nodes in right subtree + 1 (for itself). This can be maintained in constant time during insertion and deletion. Now finding a median is just finding the key with rank n/2 where n is total number of elements.
Time complexity - O(log n) in worst case.
Space Complexity - O(1)
What's the explanation for the space complexity to be O(1)? Where are the n BST nodes held?
The root of an AVL tree has the balance factor -1, 0 or 1.
If the balance factor is 0 the root's value is the median.
If the balance factor is -1 the median is the average of the root's value and the maximum value of root's left subtree.
If the balance factor is 1 the median is the average of root's value and the minimum of root's right subtree.
Complexity is logarithmic in N.
If the AVL structure is adjusted to keep track of max and min values then finding the median can be done in constant time.
Updating the min & max values when inserting/deleting from the tree adds overhead that is (worse case) logarithmic. For each node the min value is the min value of left child, the max value is the max value of the right child.
No, it doesn't work. AVL tree are balanced based on just the height of the left subtree and right subtree. There could be a big difference between the actual number of nodes in the two subtree.
For example, assume left subtree is a full binary tree of height k and right subtree is a full binary tree of size k minus one leaf deleted for all the nodes in the second to last level. The balance factor is 1 but the difference between the nodes in the subtrees are huge.
AVL tree seem to do jack squat for reducing the order of finding median. You can use it to get a sorted order and find the median which is still going to be O(n) which is order equivalent to finding the median in an array in the first place.
Anyone knows anyway which actually reduces the order, please email me. I am really interested to know.
I agree with Navid and that's why i subscribed to this question.
I would like to know:
is the tree already full?
or
we fill in values
also do we have access to the node.balance method?
We can implement BST using AVL tree
Keep counts
1) elements larger than median
2) elements smaller than median
calculate the median for first two elements
for third element onwards keep the track of the counters. If the counters differ by more than 2 then you know the tree might be out of order
then maybe we can do something at that step
to prove the point AVL BST is not a good median holder see this example
(insert into AVL BST with max diff = 1)
12 - 9 - 18 - 7- 10
This tree is still in balance ( the height differ by just 1 of left and right subtree of 12)
but the median should be 10.
12
9 18
7 10
@navid, no, it's not correct. "right subtree is a full binary tree of size k minus one leaf deleted for all the nodes in the second to last level." cannot be an AVL tree. In an AVL tree, The height of the tree may grow only after you fill completely, as otherwise there should be two subtree whose heights differ by >1.
As mdc said, you should use in-order DFS to traverse tree from minimal value up to the bigger values.
For memory consumption optimization you can do following things:
- maintain amount of added values to tree
- calculate amount of values at tree before actually getting median value
After that you know total amount of values at tree and you can find median just like that (python):
class Tree(object):
...
def inorder(self, node):
if node:
for i in self.inorder(node.left):
yield i
yield node.value
for i in self.inorder(node.right):
yield i
count = amount_of_value_at_tree
m_list = list(islice(tree.inorder(t.root), count/2+1))
if count % 2 == 1:
median = m_list[-1]
else:
median = (m_list[-1] + m_list[-2])/2
print median
But the question is - why do we need balanced tree here? We can do that calculation for any BST.
AVL tree with 2 modifications
1. Balance based on count of elements in left subtree and right
2. Balance all subtrees as well
I propose using 2 heaps - min-heap for the greater, and max-heap for the lesser. These heaps ensure O(1) in retrieving the minimal and maximal elements and O(logN) for insertion.
When inserting new values, we use the minimal and maximal to of the heaps to choose and update the right median.
We maintain balance (max diff of 1 between the heap sizes) by moving the minimal of the greater-heap, or the maximal of the lesser-heap to the opposite heap as needed. If the heaps are of same size, we can add the new value to either heap.
The median is the root of the heap with the +1 size, or the average of both roots, in case the sizes are equal.
To put it simply , I ve used Binary Search Tree (didn't add up the balancing -rotation)
bottom line here is to traverse to capture all the value of the nodes
here's java code
public static void main(String[] args){
BinaryTree bt = new BinaryTree();
bt.insert(11);
bt.insert(5);
bt.insert(6);
bt.insert(9);
bt.insert(10);
bt.insert(15);
bt.insert(3);
bt.display();
bt.storeValue(bt.root);
System.out.println(bt.findMedian());
}
public class BinaryTree {
ArrayList<Integer> ar;
class Node{
int data;
Node leftChild;
Node rightChild;
public Node(int d){
this.data=d;
ar=new ArrayList<Integer>();
}
}
Node root;
public void insert(int d){
Node n=new Node(d);
if(root==null){
root=n;
}
else{
Node curr=root;
Node parr=null;
while(true){
parr=curr;
if(d<curr.data){
curr=curr.leftChild;
if(curr==null){
parr.leftChild=n;
return;
}
}
else{
curr=curr.rightChild;
if(curr==null){
parr.rightChild=n;
return;
}
}
}
}
}
public int getMaxDepth(Node n){
Node curr=n;
int count=0;
if(curr!=null){
count++;
if(curr.leftChild!=null && curr.rightChild==null)
return count+getMaxDepth(curr.leftChild);
else if(curr.leftChild==null && curr.rightChild!=null)
return count+getMaxDepth(curr.rightChild);
else {
if(getMaxDepth(curr.leftChild)>getMaxDepth(curr.rightChild))
return count+getMaxDepth(curr.leftChild);
else
return count+getMaxDepth(curr.rightChild);
}
}
else
return count;
}
public void display(){
Stack<Node> parr = new Stack<Node>();
Stack<Node> curr = new Stack<Node>();
boolean isEmptyRow=false;
parr.push(root);
while(isEmptyRow==false){
isEmptyRow=true;
while(parr.isEmpty()==false){
Node n=(Node)parr.pop();
if(n!=null){
System.out.print(" "+n.data+" ");
curr.push(n.leftChild);
curr.push(n.rightChild);
if(n.leftChild!=null || n.rightChild!=null)
isEmptyRow=false;
}
else{
System.out.print(" ** ");
curr.push(null);
curr.push(null);
}
}
while(curr.isEmpty()==false){
parr.push(curr.pop());
}
System.out.println("\r\n");
}
}
public void storeValue(Node n){
if(n!=null){
ar.add(n.data);
if(n.leftChild!=null && n.rightChild==null)
storeValue(n.leftChild);
else if(n.leftChild==null && n.rightChild!=null)
storeValue(n.rightChild);
else if (n.leftChild!=null && n.rightChild!=null){
storeValue(n.leftChild);
storeValue(n.rightChild);
}
}
}
public Integer findMedian(){
Collections.sort(ar);
if(ar.size()%2==1)
return ar.get(((ar.size())+1)/2 - 1);
else
return (ar.get((ar.size()/2) -1 ) + ar.get(((ar.size()/2) + 1)) -1 )/2;
}
AVL trees are balanced height not count
I'd go with the following:
count left side, count right side, add 1 for the root and calculate tree size. O(n)
calculate if the median is to the left or to the right by subtracting the right0count from the left-count and divide by 2.
This will provide how many hops we should do and to which side.. O(k) - k is the imbalance count / 2
No additional memory usage
Cheers
The question is a little vague. It states "given" the tree, therefore I think that methods that take advantage of adding features to an AVL tree wouldn't be acceptable. Also, taking the node (or close to the node) seems a little easy, so I would have to say that the traversal methods are the only acceptable ones. Would like clarification on the question.
psuedo code -
1) Every node contains its left and right node counts
2) starting from root, check if leftsize == lowermedian if yes, then we found it -
a) check if n == odd, return (root->data)
b) else return( its successor + root->data ) /2;
3) Else check for left or right recursively.
T = O(logn) //As tree is balanced
int median(tree *root,int n, int orgN,int suc)
{
if(!root) return 0;
if(n == 0) {
if(orgN & 1) return root->data;
else {
if(root->right) {
int elem = min(root->right);
return (root->data + elem)/2;
} else {
return (root->data+suc)/2;
}
}
}
if(root->lsize == n)
return median(root,0,orgN,0);
else if(root->lsize < n)
return median(root->right,n-root->lsize-1,orgN,0);
else
return median(root->left,n,orgN,root->data);
}
//caller
median(root,(n-1)/2,n,0);
psuedo code -
1) Every node contains its left and right node counts
2) starting from root, check if leftsize == lowermedian if yes, then we found it -
a) check if n == odd, return (root->data)
b) else return( its successor + root->data ) /2;
3) Else check for left or right recursively.
T = O(logn) //As tree is balanced
int median(tree *root,int n, int orgN,int suc)
{
if(!root) return 0;
if(n == 0) {
if(orgN & 1) return root->data;
else {
if(root->right) {
int elem = min(root->right);
return (root->data + elem)/2;
} else {
return (root->data+suc)/2;
}
}
}
if(root->lsize == n)
return median(root,0,orgN,0);
else if(root->lsize < n)
return median(root->right,n-root->lsize-1,orgN,0);
else
return median(root->left,n,orgN,root->data);
}
//caller
median(root,(n-1)/2,n,0);
psuedo code -
1) Every node contains its left and right node counts
2) starting from root, check if leftsize == lowermedian if yes, then we found it -
a) check if n == odd, return (root->data)
b) else return( its successor + root->data ) /2;
3) Else check for left or right recursively.
T = O(logn) //As tree is balanced
int median(tree *root,int n, int orgN,int suc)
{
if(!root) return 0;
if(n == 0) {
if(orgN & 1) return root->data;
else {
if(root->right) {
int elem = min(root->right);
return (root->data + elem)/2;
} else {
return (root->data+suc)/2;
}
}
}
if(root->lsize == n)
return median(root,0,orgN,0);
else if(root->lsize < n)
return median(root->right,n-root->lsize-1,orgN,0);
else
return median(root->left,n,orgN,root->data);
}
//caller
median(root,(n-1)/2,n,0);
I used a depth first traversal of an AVL Tree to recursively create a sorted array of all node keys. Using this array It was a simple matter of writing a method to find the mean of a sorted array (findMedianOfArray:_)
//Traverse the AVL Tree and keep track of node keys in the mutable array
-(double)findMedian:(AVLTreeNode*)node array:(NSMutableArray*)array {
if (node != nil) {
[self findMedian:node.left array:array];
[array addObject:[NSNumber numberWithInteger:node.key]];
[self findMedian:node.right array:array];
}
return [self findMedianOfArray:array.copy];
}
-(double)findMedianOfArray:(NSArray*)array {
NSNumber *medianNumber = @0;
if (array.count == 0) {
return 0;
}
if (array.count == 1) {
id medianObject = array.firstObject;
if ([medianObject isKindOfClass:[NSNumber class]]) {
return ((NSNumber*)medianObject).integerValue;
}
}
if (array.count % 2 == 1) { // is even
NSInteger medianIndex = (array.count / 2);
id medianObject = array[medianIndex];
if ([medianObject isKindOfClass:[NSNumber class]]) {
medianNumber = medianObject;
}
} else { //is odd
NSInteger medianIndex = (array.count / 2);
id medianObjectA = array[medianIndex];
id medianObjectB = array[medianIndex - 1];
if ([medianObjectA isKindOfClass:[NSNumber class]] && [medianObjectB isKindOfClass:[NSNumber class]]) {
medianNumber = [NSNumber numberWithDouble:(((NSNumber*)medianObjectA).doubleValue + ((NSNumber*)medianObjectB).doubleValue) / 2.0];
}
}
return medianNumber.doubleValue;
}
An in-order, depth-first traversal of a binary search tree (which an AVL is by definition) produces a sorted list of all elements in O(n) time. Simply take the middle element of this list in order to retrieve the median.
typedef void (^AVLTreeTraversalBlock)(AVLTree *tree, BOOL *stop); @implementation AVLTree (CCPMedian) - (void)ccp_depthFirstInOrderTraversalWithBlock:(AVLTreeTraversalBlock)block { [self.left ccp_depthFirstInOrderTraversalWithBlock:block]; if (block) { BOOL stop = NO; block(self, &stop); if (stop) { return; } } [self.right ccp_depthFirstInOrderTraversalWithBlock:block]; } - (NSNumber *)ccp_median { __block NSMutableArray *values = [NSMutableArray array]; [self ccp_depthFirstInOrderTraversalWithBlock:^(AVLTree *tree, BOOL *stop){ [values addObject:tree.value]; }]; // Assume we have a method ccp_middleValue that returns // the middle element of a sorted list, or the mean of the two // middle values if there are an even number of elements // (the definition of the median according to Wikipedia). return [values ccp_middleValue]; } @endSome optimizations could be made as well; for example, if the tree maintains a count of its nodes, we could stop our traversal once we reach the middle element (the median).
- mdc May 21, 2014