ashok.koyi
BAN USERCan u explain the problem a bit more clearly, From what I understood, it is asked that we need to find the siblings(only left and right) for the given node.
The questions I have are
1. Are you given a standard binary tree with just left and right pointers?
2. If so, are you allowed pre-process the tree before you can actually find the left and right siblings?
I don't think the algo has O(n*n) time complexity
The following are the cases I can think of
Case 1: If the tree is skewed completely (which means the original tree itself is a list), finding predecessor and successor is a const operation and algo runs in O(n)
Case 2: If the tree is perfectly balanced, Finding predecessor and successor for the root take O(lgn)
and for each of its childs O(lgn-1) and so on, going down the tree
overall time complexity is O(lgn+2*(lgn-1)+4*(lgn-2)+....)
lgn*(1+2+4+8+...2^(lgn-1)) - 2(1+2+4+...+2^(lgn-1)*logn) = O(nlgn)
I think O(nlgn) itself is not a very tight bound [need to brush up my math skills to solve this kinda recursion]
Lets say I make 2 draws one from the first and one form the second container, from then on the probability of losing is 0.12 which is very bad afterall..
- ashok.koyi November 02, 2011Lets say I make 2 draws one from the first and one form the second container, from then on the probability of losing is 0.12 which is very bad afterall..
- ashok.koyi November 02, 2011/**
* Returns the head of the transformed linked list
*/
public BinaryTreeNode convertBSTIntoSortedLL(BinaryTreeNode root){
convertBSTIntoSortedLLHelper(root);
return getLeftMostChild(root);
}
/**
* The actual meat of the algorithm
*/
private void convertBSTIntoSortedLLHelper(BinaryTreeNode root){
if(root == null){
return;
}
// Get the inorder successor and predecessors
BinaryTreeNode inorderPredesessor = null;
BinaryTreeNode inorderSuccessor = null;
if(root.getLeft() != null){
inorderPredesessor = getRightMostChild(root.getLeft());
}
if (root.getRight() != null){
inorderSuccessor = getLeftMostChild(root.getRight());
}
// Recurse into both left and right subtree
convertBSTIntoSortedLLHelper(root.getLeft());
convertBSTIntoSortedLLHelper(root.getRight());
// Set the references properly
if(inorderPredesessor != null){
inorderPredesessor.setRight(root);
}
if(inorderSuccessor != null){
root.setRight(inorderSuccessor);
}
}
private BinaryTreeNode getRightMostChild(BinaryTreeNode node){
while(node.getRight() != null){
node = node.getRight();
}
return node;
}
private BinaryTreeNode getLeftMostChild(BinaryTreeNode node){
while(node.getLeft() != null){
node = node.getLeft();
}
return node;
}
The steps are quite simple,
1. Find the in-order predecessor & successor of the current node
2. Recurse into each of the child
3. Once done with childs, point inorder predecessor next to current node and currentnode's next to inordersucessor
Can u plz explain on how do you solve whether the given point lies inside a ploygon in O(logn)?
- ashok.koyi September 19, 2011Cant we use two dimensional bit array?
- ashok.koyi September 17, 2011
I've ran the code I pasted here against testcases. It is giving inorder traversal of the original tree, when I followed the right pointer of each node
- ashok.koyi November 03, 2011However, I don't understand what you mean by above comment.