## Amazon Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
2
of 2 vote

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

You mean balanced BT right ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

you mean a balance BST right ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

what's the max look up ti..

Comment hidden because of low score. Click to expand.
0
of 0 vote

worst case is order n, since the binary tree would become

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

*your

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I totallu agree with Karthik...

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n)

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.