## Amazon Interview Question for Software Engineer / Developers

Country: India

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

Case 1: If the original root itself is choosen as the root and picked up, then the tree remains binary
Case 2: Otherwise, the original root will have one child. Internal nodes with k children become nodes with k+1 children, where 1<=k<=2. Leaf nodes will have zero or one(in case a leaf is picked as the root) children.

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

Case 2 could rather be split into case 2 and case 3 for a clearer exposition.

Case 2: If an internal node is chosen as a root, the original root will have one child. The nternal node chosen to be the root will have one more child than before. Leaf nodes will have zero children

Case 3: If a leaf node is chosen as a root, the original root will have one child. The chosen leaf node will have one child and all other leaf nodes have 0 children. All internal nodes will have the same number of children as before.

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

it would be a splay tree its like we are accessing a node that will become root and remaining tree will be adjusted as a binary tree by single or double rotation

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

But the rotations would come into play only if the resulting tree will have to be balanced again to retain any properties. If, for instance, there is a constraint that the resulting tree must be a valid binary tree, then rotations will be required in order to ensure than every node has at most 2 children.

The worst that can happen is when an internal node that has two children is chosen, in which case this node will now have 3 children - 2 of its original children and the root (along with the entire left/right subtree attached to the root). So we have some kind of 2-3 tree, of course, satisfying none of the cornerstone conditions which actually makes these kind of trees useful.

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

@copyconstructor- If we choose internal node then also we have the rotations rules(single or double rotation) defined for splay tree which will maintain the binary tree and we will not have the 2-3 kind of structure.
Please let me know if I am wrong at any point.

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

In my perspective it ll become a unbalanced tree with left subtree containing more nodes than right or vice verse. Any suggestions ??

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

one more case: if it will choose internal node which has 2 child than this won't be Binary tree.... than root will have 3 child...

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.