Interview Question for Software Engineer at Google:

Each tree node only contains a maximum of 2 children nodes maintained in a particular order. For instance, left child has a value less than the right child. The parent node typically has a value in between the 2 children. (greater than left child, but less than right child).

When ordering of elements in the data structure matters. for instance, keep the root node as the node with the largest or smallest value for fast retrieval. Also when the hierarchical parent children relationship is important for a complete traversal. for instance when a parent is marked as invisible, all of its children are also considered invisible, e.g. scene graph bounding tree.

Thanks for the answers Neakor. It all looks good, but I think we need to include emphasis on the "balanced" part of balanced binary tree, which means that the insert & delete operations are specialized to keep the tree's height relatively low. For example, an AVL tree does this by trying to keep all leaves close to the same level of the tree. This "balanced" constraint keeps the tree from degenerating into a linear linked list.

thanks for the clarification chris! very helpful!

(assume "balanced binary tree" means "balanced binary search tree", else the question doesn't really make sense)

A balanced binary search tree is a tree-based data structure where each node has at most two children and each level is complete except possibly the deepest. The left descendants of a given node have keys less than the node’s key and the right descendants have keys greater than the node’s key. Finding an item in a balanced binary search tree runs in O(log n). Insertion and deletion run in O(log n). Finding an item in a hashmap runs in constant time, but one would want to use a balanced binary tree if the hashmap function is imperfect and many key collisions are expected to occur. With a balanced binary tree, there will never be more than one value per node. One may also want to use a balanced binary search tree if the hash function is particularly slow.

ellemeno nailed it but a little more info.

The reason you want balanced tree is to have all the operations be O(logn) where an unbalanced tree would have O(n) for all operations.

A hash has constant insert and O(n) search. It does have average constant time search but if you need to minimize O(), a balanced tree gets you a better search time (though worse on average)