## VMWare Inc Interview Question for Interns

Country: India
Interview Type: Phone Interview

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

By using extra space, you can do an inorder traversal, and write the elements to the array.
After that, use binary search to find the middle element of the array and make it the root. Recursively invoke binary search on the left half and right half of the array to create left subtree and right subtree. This will give you a tree of min-height.

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

will not work unless you sort the array..we have to create BST out of binary tree

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

Read the question carefully
>> You are given a *sorted* skewed binary tree

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

No need to use binary search. The middle of the array is given by arr[arr.length / 2].

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

@eugene.yarovoi

You are right. That occurred to me a bit late :-)

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

Without using extra space, you can first run a recursive procedure, which at each step, determines the heights of the left-subtree and right-subtree, and then does 'rotations' with either of the left/right children as pivot according to their heights.

This method would be terribly slow because at each recursive invocation to find the height of the tree, the whole sub-tree would be traversed.

It can be sped up by storing a height variable at each node of the tree and computing it's value only once, but then it amounts to using extra space.

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

You could also manipulate the tree pointers to flatten the tree nodes into a sorted linked list, and then convert the linked list into a perfectly balanced tree.

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

``````Since the tree is sorted ..we can use a binary search style mid-point finding algorithm to get the root at each level...from skewed i assume that one sub-tree has more elements than the other sub-tree..meaning..in the array -- elements in one side of the mid-point is greater than the other...this could be handled by a simple if condition in the code..logic below---

space -- O(N) ==> one node element for each number .. time -- O(N.LogN) -==> binary search

// find midpoint
int mid-point(int left, int right){
if(left==right) return left;
return floor ((left+right) / 2)
}

// sample helper function to create a class node of type Node on a global array (in our case, input array) -- say 'a'

Node node( int index){
Node node = null;
if (index >0) { return (new node (a[index]) )
else return node
}

// form recursive BST from root at each level

void formBST (Node root, int left, int right) {
if(left < 0 || right > a.size-1 || root == null) return;
int x = mid-point(left, right);
root.left (node (mid-point(left, x-1) ) ) ;
root.right (node (mid-point(X+1, right) ) ) ;
formBST (root.left, left, x-1) ;
formBST (root.right, x+1, right);
}``````

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

You do not need this mid-point function. Because once we have sorted array picking mid element suffices to construct balanced tree.

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

Suppose I have been given root of the skewed BinaryTree:

``````//Helper function to find size of tree
int size(BinaryTreeNode root){
if(root == null) return 0;
else{
retrun(size(root.getLeft()) + 1+ size(root.getRight());
}
}

// Inorder traversal

int[] inrderTraversal(BinaryTreeNode root){
int[] inOrder = new int[size(root)];
int index = 0;
if(root != null){
inrderTraversal(root.getLeft());
inOrder[index++] = root.getData();
inrderTraversal(root.getRight());
}
}
// Minimum height tree creation
BinaryTreeNode buildBalancedTree(int[] inOrder, int start, int end){
BinaryTreeNode treeNode;
if(start>end) return null;
treeNode = new BinaryTreeNode();
if(start == end){
treeNode.setData(inOrder[start]);
treeNode.setLeft(null);
treeNode.setRight(null);
}else{
int mid = start + (end-start)/2;
treeNode.setData(inOrder[mid]);
treeNode.setLeft(buildBalancedTree(inOrder, start, mid-1));
treeNode.setRight(buildBalancedTree(inOrder, mid+1,end));
}
return treeNode;
}

// testing the APIs, rrot is the root of skewed binary tree in question
int n = size(root);
int startIndex= 0;
int[] inOrder = inrderTraversal(root);
BinaryTreeNode balancedTree = buildBalancedTree(inOrder, 0, n-1);``````

Add a Comment
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.

Learn More

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

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More