## Amazon Interview Question

Software Engineer / Developers**Country:**India

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.

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

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.

Case 1: If the original root itself is choosen as the root and picked up, then the tree remains binary

- Murali Mohan January 11, 2014Case 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.