PrateekS.
BAN USER- 4of 4 votes
AnswersGiven a binary tree where all the right nodes are leaf nodes, flip it upside down and turn it into a tree with left leaf nodes.
Keep in mind: ALL RIGHT NODES IN ORIGINAL TREE ARE LEAF NODE.
- PrateekS. in United States/* for example, turn these: * * 1 1 * / \ / \ * 2 3 2 3 * / \ * 4 5 * / \ * 6 7 * * into these: * * 1 1 * / / * 2---3 2---3 * / * 4---5 * / * 6---7 * * where 6 is the new root node for the left tree, and 2 for the right tree. * oriented correctly: * * 6 2 * / \ / \ * 7 4 3 1 * / \ * 5 2 * / \ * 3 1 */
| Report Duplicate | Flag | PURGE
Linkedin
If space is not an issue, then another idea besides the
product / array[i]
method is
Let N be the length of the array.
1. Create two temporary arrays,
prodLeft[ N ] & prodRight[ N ],
where, prodLeft[i] contains the product of all elements to the left of array[i], and prodRight[i] contains the product of all elements to the right of array[i]
2. for each element, replace
array[i] = prodLeft[i] * prodRight[i]
So the implementation of this code would look like
public void ReplaceWithProducts(int[] array)
{
if (array.length == 1)
return;
int count = CountZeroes(array);
if (count > 1)
{
// If there are more than 1 0's,
// all the elements will be ultimately 0
replaceWithZeros(array);
return;
}
if (count == 1)
{
// If there's only 1 zero, only the zero
// element will have a non-zero value.
// All other elements will be 0.
long product = 1;
int index = 0;
for (int i = 0; i < array.length; i++)
{
if(array[i] == 0)
{
index = i;
continue;
}
// Compute the product so far.
product = product * array[i];
// Keep setting the element to zero since
// we already have the element's contribution
// in the product.
array[i] = 0;
}
array[index] = product;
return;
}
// If there are no 0's.
int[] prodLeft = new int[array.length];
int[] prodRight = new int[array.length];
prodLeft[0] = 1; // Since there're no elements to the left
prodRight[array.length - 1] = 1; //Since there're no elements to the right of the last one.
for (int i = 1; i < array.length; i++)
{
prodLeft[i] = array[i-1] * prodLeft[i-1];
}
for (int i = array.length -2; i >= 0; i--)
{
prodRight[i] = array[i+1] * prodRight[i+1;]
}
for (int i = 0; i < array.length; i++)
{
array[i] = prodLeft[i] * prodRight[i];
}
}
public int CountZeroes(int[] array)
{
int count = 0;
for (int i = 0; i < array.length; i++)
{
if(array[i] == 0)
{
count++;
}
}
return count;
}
public void replaceWithZeros(int[] array)
{
for (int i=-; i<array.length; i++)
{
array[i] = 0;
}
}
Yes it will
lets say
pTrav->Left
has exactly K nodes.
Then
pTrav = pTrav->left
starts the loop again.
Now
pTrav->Left
will have less than k nodes so it will shift to the right subtree as
pTrav= pTrav->Right
Eventually ending up at the
rightmost node of the left subtree.
which will be the kth smallest number
- PrateekS. August 05, 2014I think you're on the right path, but there might a small thing you missed
In the LargestBST Method,
largestSubTree(R->left);
largestSubTree(R->right);
you return node but, you never actually compare the result of these two recursive calls. It should be something like
struct node* largestSubTree(struct node *root, int *count)
{
int countLeft = 0, countRight = 0;
static int tmp_count=0;
static struct node *node=NULL;
if(!root) return NULL;
if(isBST(root,INT_MIN,INT_MAX,&count))
if(count>tmp_count)
{
tmp_count=count;
node=root;
return node;
}
node* left = largestSubTree(R->left, &countLeft);
node* right = largestSubTree(R->right, &countRight);
if(countLeft > countRight)
node = left;
else
node = right;
return node;
}
the conditions inside your while loops should be &&
Otherwise, for instance, when start->left is null, the while loop exits before you can finish heading down to the leftmost child of the right subtree.
Same for the rightmost leaf one.
Also, anyone would think that for the leftmost and rightmost nodes you simply traverse down root->left-> left->left-> ....
and
root->right->right...
so far but your solution raises a good point of ambiguity. What do we classify as the leftmost/rightmost leaf node here
It should be able to handle negative numbers just fine.
Some pseudocode..
Let the number we're trying to sum upto be SUM
Step 1.
foreach(int n in array)
{
int complement = SUM - n;
if(hashTable.containsKey(complement)
return true; // found the pair {n, complement}
hashTable.Add(n, complement);
// You can simply choose to add true or 1 here. I chose to add the complement value as the
// value part of the key,value pair thing.
}
Step2. There is no step 2.
It should work wiht -ve numbers just fine
for example
a = [2, -2, 5, 6, 9, -14, -3]
sum = 3
hashtable[-2] = 5
so -2, and 5 will be a valid pair
For this piece of code, arent the conditions reversed?
if (leftNodes == -1 ||
(leftNodes != 0 && p->data <= max))
isBST = false;
And
if (rightNodes == -1 ||
(rightNodes != 0 && p->data >= min))
isBST = false;
Shouldnt they be "
//if data is greater than max or less than min then its not a bst
if (leftNodes == -1 ||
(leftNodes != 0 && p->data <= min))
isBST = false;
And
if (rightNodes == -1 ||
(rightNodes != 0 && p->data >= max))
isBST = false;
My answer
class TreePrinter {
static class Node {
int value;
Node left;
Node right;
}
public void printTree(Node root) {
Queue<Node> queue = new Queue<Node>();
if(root == NULL)
return;
queue.enqueue(root);
List<Node> list;
while(!queue.IsEmpty())
{
list = new List<node>(); // Initialize a new list
while(!.queue.IsEmpty())
{
Node u = queue.dequeue(); //Remove the first element in the queue
if(u.Left != NULL) { list.add(u.Left); }
if(u.Right != NULL) { list.add(u.Right); }
Console.Print(u.data + " ");
}
Console.PrintLine();
// Add the enxt level to the queue
foreach(Node n in list)
{
queue.enqueue(n);
}
}
}
}
My Answer
1. Recursively traverse to the leftmost node.
2. This becomes the NewRoot, and keep returning this value, up the chain.
3. Make the following changes
- CurrentRoot. Left.Left = CurrentRoot.Right
- CurrentRoot.Left.Right = CurrentRoot
- CurrentRoot.Left = CurrentRoot.Right = NULL
Node FlipTree ( Node root )
{
if (root == NULL)
return NULL;
// Working base condition
if( root.Left == NULL && root.Right == NULL)
{
return root.Left;
}
Node newRoot = FlipTree(root.Left);
root.Left.Left = root.Right;
root.Left.Right = root;
root.Left = NULL;
root.Right = NULL;
return newRoot;
}
The idea is to sort the given people based on when they entered/exited the conference room.
Since logically a valid data set will have at least one exit time after all the entry times are finished, we sort the entry and exit times. And simply increment/decrement a counter accordingly.
- PrateekS. July 18, 2017