CareerCup

Haha, good point... a sorted, balanced tree is O(log n), otherwise O(n)

It would be O(log n) if sorted (which is what they must be looking for), else O(n)

O(n) - for the max time you would ahve to look at each node

Well, assuming it's a sorted binary tree, it's O(log n)

You mean balanced BT right ?

you mean a balance BST right ?

There's actually three different cases:
1. Sorted and balanced
2. Sorted (not necessarily balanced)
3. Unsorted

Is there any such thing as unsorted BST??? I don't think so...the data given to you can be sorted or unsorted which results in a unbalanced and balanced (not necessarily...but is more balanced than the tree resulting from sorted data) tree respectively.

i.e sorted data => O(n)
unsorted data => O(log n) avg case

what's the max look up ti..

worst case is order n, since the binary tree would become
a linked list.

What about if the data is totally unordered? A binary tree can be unsorted. Then you end up searching all the nodes. So O(n).

Also, what if you're binary tree doesn't exist? Say null? Then O(1).

*your

IMO the important word here is "max", which I have translated to worst. Also no property of the tree is mentioned, that is, full or complete or almost complete or ordered etc.

Max (worst case) look up time for a Binary Tree:

1. Ordered and Balanced (i.e BST) : O(log n)
2. Ordered and Unbalanced : O(n)
3. Unbalanced : O(n)

There is nothing like ordered in a binary tree. Either it is balanced or unbalanced.

Balanced is the one which has a depth of log(n) where n is the number of nodes. Unbalanced have a depth more than log(n). Worst case depth is n.

Worst case scenario is that a binary tree is so unbalanced it becomes a linked list in which case the search time is O(n) because the depth is n.

Binary tree is always sorted when you do an inorder traversal of that tree.

Binary tree need not always be sorted. A Binary Search Tree is always sorted. When u do an inorder traversal of a "BST" u get the sorted (ascending) order.

I totallu agree with Karthik...
I have the same answer......

Wondering: What is the cost of keeping a binary tree balanced while you keep inserting nodes?

Wondering: What is the cost of keeping a binary tree balanced while you keep inserting nodes?

Max (worst case) look up time for a Binary Tree:

1. Ordered and Balanced (i.e BST) : O(n)
2. Ordered and Unbalanced : O(n)
3. Unbalanced : O(n)

In each case, the worst case occurs when the tree behaves like a linked-list

O(n)