## Amazon Interview Question for SDE1s

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
5
of 7 vote

O(n) method....

``````void BalancePavanIdiotsTree(TreeNode *root)
{
1) in order traverse and store in array A[]
2) create balanced tree from A[] using divide and conquer (Pavan said this was easy)
}``````

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

hey you forgot to write class :)

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

Heapify the binary tree after getting into an array. O(n) solution.

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

I have a doubt.. We cannot heapify a tree unless it maintains the structural property right? Then how can we apply heapify

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

Heaps requires that the key in each node is comparable. Since this is a binary tree and not a binary search tree (also note that a BST would maintain a different property than a heap) this would not work on all data types.

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

Can we change the root of this tree ??

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

From Wikipedia: A balanced binary tree is commonly defined as a binary tree in which the depth of the left and right subtrees of every node differ by 1 or less...

So, in theory, we could maintain depth of the left and right subtrees in each node. At the root node, we will have the degree of imbalance between the left and right subtrees. If left subtree has more depth, then we move nodes from left to right subtree until the imbalance has been corrected to a difference of <= 1. Perhaps a recursive approach may be useful...

I have not coded this up, but will try now...just thought I will post the idea first.

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

1.) Flatten the input tree [inplace ]
2.) Use Binary search to create a balanced tree it just needs to be a tree and not a BST

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

Binary search approach will not result in a BST because flattening of the tree in place will not necessarily result in a sorted linked list

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.