Balanced vs Unbalanced Binary Tree - Clarification Needed

Question

I am in need of some clarification, this may be a really stupid question and I have done research but cannot find a clear answer to my question. My question is, What are some property differences between a balanced binary tree and an unbalanced binary tree? I was asked this on an interview (java questions) and I had explained to the interviewer the differences however he mentioned that he wants to know the properties that differentiate between the two (binary tree - unbalanced vs balanced).

If someone can please clarify this for me, i'd greatly appreciate it.

Rhinencephalon

What specifically would you like clarification on? Have you found some resources explaining balanced binary trees which you didn't understand? – Rightist

What does it mean exactly by "properties"? – Rhinencephalon

That's a bit vague, it could be implementation details, the time complexity of the operations, the formal conditions defining whether a tree is "balanced" or not... I suggest investigating all of them, and if that kind of question comes up in an interview again, ask for clarification from the interviewer. – Rightist

I see, well thank you so much for explaining this. I will definitely look into these to prepare in case it does pop up again. Will do, thank again! – Rhinencephalon

There is only one 'property' that may be different, and that is the difference between the heights under each node, which is constrained in the case of a balanced tree and unconstrained otherwise, and that in turn leads to a performance upper bound in the case of a balanced tree. It's a poorly phrased question, if that's what the interviewer really said. – Unlay

Thank you for the clarification! But yes, I believed so as well. – Rhinencephalon

Answer 1

By "properties", I believe the interviewer was asking about Big-O performance complexity.

With a balanced tree, access¹ is O(log n).
With an unbalanced tree, access¹ is O(n) (worst case).

That is because an unbalanced tree built from sorted data is effectively the same as a linked list.

The space complexity is the same for both types of trees.

^{1) Access covers lookup, insert, and remove operations.}

Jacobba

Simple and direct thank you! – Quincentenary

Answer 2

I think Andreas's answer is on point, but you need to know the inner workings of a binary tree and linked list to appreciate it. Seems this is what the interviewer is quizzing you on: do you know what he's talking about when he brings up the structure, and can you comfortably walk through it to derive a reasonable answer?

Another way to think about the question is to shift the focus on the balanced tree. What makes it balanced? For each level, the height of the left subtree is the same as the right one, so every root at that level has either two nodes or one node. An unbalanced one is the opposite.

Now that you understand what an unbalanced vs balanced tree looks like, you can start comparing their implementations. What is the implementation for binary search? You keep halving the tree until the target is located. As a pattern, every time you deal with a problem that involves halving the amount of inputs, that's log(N), since we're working with base of x,

log(aN) = x => a^x = N  

So the worst case runtime of a balanced search tree is O(log(N)), where the target is either not found or at the very last position, you're halving N inputs (log(N)).

For the unbalanced search tree, the worst case scenario is the same where the target is not found or at the very last position, but because the tree is unbalanced, instead of halving, you're going through every item in a linear way. Therefore, the runtime is O(N).

What does the runtime of the unbalanced tree mean in relation to the balanced tree? If you consider the runtime order, O(N) is slower than O(logN), which is why a balanced tree is usually the better structure.

Witter

Answer 3

There are multiple properties that distinguish balanced and unbalanced binary trees as listed bellow.

Height: -In a balanced tree, the height is logarithmic with regards to the number of nodes, and is O(log n), where n is the number of nodes. -However, the height of an unbalanced binary tree may differ based on the manner in which the nodes are inserted and could potentially be closer to O(n) as is the case with a linked list.

Node Distribution:

• Balanced Binary trees have nodes that are distributed evenly accross levels. This allows the tree to remain balanced and efficient in its use for insertion, deletion and search.
• However in an unbalanced binary tree, the nodes are skewed to one side and this results in an uneven distribution. This could result in the tree becoming a linear structure which defeats the purpose of using a binary tree.

Complexity of Operations:

• In a balanced binary tree, operations including insertion and deletion have a time complexity of O(longN) with n representing the number of nodes. This time complexity is a result of the balanced nature of the tree.
• The time complexity of these operations is closer to O(n) when performed using the unbalanced Binary tree. This is due to the fact that traversing the tree will require them to visit each node in the worst-case scenario.

Williwaw