## Bloomberg LP Interview Question

Financial Software Developers**Country:**United States

**Interview Type:**In-Person

A Binary Tree is a tree in which each node can have maximum of 2 children.

Uses could be like a folder structure or the organizational hierarchy. It is used when there are no specific rules as to which node should be where, unlike in the case of a BST or a balanced tree which follow a set f rules.

An AVL tree is a balanced BST,it basically assures that the height of your tree is k*log n where k is a constant and n is the number of nodes in the tree. This in turn reduces the time complexity of an add, delete or a search operation to O(log n) which would normally be O(n) in a binary tree and O(h) in a BST.

I guess this answers the question for which is most efficient.

I do not know much about RB trees, but it too is a balanced BST like AVL trees and I believe that the implementation of operations in an RB tree are a lot more complex than that of an AVL tree but RB trees are apparently more secure and are used by several java libraries.

Please correct me if I'm wrong.

Most of what you said isn't right.

You wouldn't want to use a binary tree for a folder structure, because a folder can have many sub-folders, not just 2.

An AVL tree's leaf nodes differ in height by at most one.

RB trees have nothing to do with security. They are often used instead of AVL trees because their insertion and deletion times have a lower constant factor.

All that you said makes a lot of sense, thanks for correcting me.

Could you please also give a scenario where a Binary Tree would be more useful compared to an AVL tree? It would be very helpful.

An AVL tree is a type of binary search tree, which is a type of binary tree. I don't know what it means to compare an AVL tree to a binary tree because an AVL tree is a type of binary tree.

A binary search tree is a type of binary tree. Asking to compare the two is like asking to compare dogs to animals.

B-Tree is used for large data, like file system or where we used external storage.It is used with multiple keys in the node w.r.t to degree of the tree and height of the tree will be lower than AVL and RB-Tree .

AVL and RB-Tree use for smaller date and could be computed on internal memory and each node can have max one key only.

1. I would ask the interviewer if they meant a binary search tree, and not a basic binary tree. A simple binary tree isn't used for searching it is simply a way to store data with left and right nodes, so really has no comparison with the other two types of trees.

- Kyle April 06, 2013I'll assume they clarified after my question that it is in fact a binary search tree to compare against.

Binary Search trees do not need to be balanced, so depending on the order of insertions the tree can become unbalanced quickly and search times could potentially vary a lot. This is the most basic search tree, and inserts and deletes have very simple logic.

AVL trees are always at the optimal balance point, but can slow down inserts and deletes because they never allow that tree height to be outside the -1 to 1 range. But you will have the fastest look times.

Red black trees are also self balancing but can become slightly imbalanced to improve insert and delete times, with a small potential hit to search times.

So if a system updates the tree often I would lean toward using a red black tree, and if the tree is updated very rarely then a AVL tree would be the better direction.

If the data will come in a "controlled manner" that we will not likely have a large imbalance than a BST could be an option but it would still be good to look at one of the self balancing tree structures.