Google Interview Question Software Engineer / Developers
inorder + merge(merge in mergesort)
using namespace std;
struct Node{
int val;
Node* left;
Node* right;
};
void inorder(Node* T1, Node* T2)
{
Node* cursor1 = T1;
Node* cursor2 = T2;
bool done = false;
stack<Node*> s1;
stack<Node*> s2;
while (!done)
{
if (cursor1)
{
s1.push(cursor1);
cursor1 = cursor1->left;
}
else if (cursor2)
{
s2.push(cursor2);
cursor2 = cursor2->left;
}
else
{
if (!s1.empty() && !s2.empty())
{
if (s1.top()->val < s2.top()->val)
{
cursor1 = s1.top()->right;
s1.pop();
}
else if (s1.top()->val > s2.top()->val)
{
cursor2 = s2.top()->right;
s2.pop();
}
else
{
cout << s1.top()->val << endl;
cursor1 = s1.top()->right;
s1.pop();
cursor2 = s2.top()->right;
s2.pop();
}
}
else
{
done = true;
}
}
}
}
Simple and sweet
function printSorted($node1, $node2) {
$current1 = $node1;
$current2 = $node2;
$stack1 = new Stack();
$stack2 = new Stack();
while (true) {
if ($current1 || $current2) {
if ($current1) {
$stack1->push($current1);
$current1 = $current1->left;
}
if ($current2) {
$stack2->push($current2);
$current2 = $current2->left;
}
continue;
}
if ($stack1->isEmpty() && $stack2->isEmpty()) {
break;
}
if ($stack1->top() < $stack2->top()) {
$next = $stack1->pop();
$current1 = $next->right;
} else {
$next = $stack2->pop();
$current2 = $next->right;
}
echo $next->data . "\t";
}
}
void PrintMerged(struct node* root1, struct node* root2)
{
if(root1 == NULL || root 2 == NULL)
return;
PrintMerged(root1->left);
PrintMerged(root2->left);
if(root1->data < root2 -> data)
{
cout << root1->data;
PrintMerged(root1->right);
}
else
{
cout << root2->data;
PrintMerged(root2->right);
}
}
let me know of any errors.
If everything in 1 tree is smaller than everything in tree2 then this will print out everything in tree1 but stop never anything in tree2
What abrahm has written is correct (just that the function calls must contain 2 arguments like PrintMerged(root1->left,root2) and PrintMerged(root1,root2->left)).
It's basically a Merge Sort for trees. Just like we'd do for sorted arrays A[] and B[] - take 2 pointers *a and *b to the end of each array and compare elements and decrease the respective pointers to merge the array together.
Here with trees, we do the same. A Search tree is sorted because the in-order traversal printing yields sorted numbers.
So here we simultaneously start doing in-order traversal on both trees and print the lesser number.
abrahm's recursive function can be made non-recursive using a user-defined stack.
Why abrahm's code is fundamentally wrong? What he is trying to do is switch between the nodes of a tree. I think its genius
Abraham code is incorrect due to the fact it compares the elements present at the same level in the two trees.Due to recursion, in case Node1-value> Node2-value, Node-2 is printed , and Node1 is compared with Node2->right. However, if Node2->right=null or Node2->right->value< Node1-value, in this case Node2-right->value gets printed and control is returned to block which compared parent of Node1, (hence, Node1 value is not printed at all in the final list).
ahh... I think I missed the case:
N1->value >N2->value, then code traverses left tree of N2 but we missed N2 itself
e.g.
Tree1:
100
50
10
20
Tree2:
70
30
5
9
12 17
in this case it will print 5,10,12 (and will miss 9)
correct me if i am wrong.. thanks !!
indentation got screwed up
ahh... I think I missed the case:
N1->value >N2->value, then code traverses left tree of N2 but we missed N2 itself
e.g.
Tree1:
{
100
50
10
20
}
Tree2:
{
70
30
5
9
12 17
}
in this case it will print 5,10,12 (and will miss 9)
correct me if i am wrong.. thanks !!
The dude's post above works, but however destroys the structure of the tree.
A multi-threaded approach would work, but may be balked at due to reentrant and synchronization issues.
Here's another approach.
Make a iterator for each tree using a modified Moris-traversal algorithm.
Now it's standard merge...
In-order tree walk gives you sorted array. so you iterate over two trees together, no? Why moris traversal needed?
public static void inorder(Node node1, Node node2)
{
if(node1==null || node2==null)
return;
if (node1.value < node2.value) {
inorder(node1,node2.left) ;
}
else {
inorder(node1.left,node2) ;
}
if (node1.value > node2.value ) {
// Append to Sorted list and add only if node isn't repeated....
inorder(node1,node2.right);
}
else {
// Append to Sorted list and add only if node isn't repeated....
inorder(node1.right,node2);
}
}
@Softy
i tried the running code, it's printing all the nodes in the ascending order, except the last node, which gets missed out because of the comparison. This can be printed in the last.
Overall the concept is INORDER traversal but on two trees...so there are multiple comparison, which results in redundancy. We need to make sure not appending duplicates to the list.
void PrintMerged(struct node* root1, struct node* root2)
{
if(root1 == NULL || root 2 == NULL)
return;
if (root1->data > root2->data)
{
if (root1->left) {
PrintMerged(root1->left, root2);
}
else {
printTreeInAscOrder(root2->left);
print(root2->data);
}
if (root2->right) {
PrintMerged(root2->right, root1);
}
else {
print(root1->data);
printTreeInAscOrder(root1->right);
}
}
else {
PrintMerged(root2, root1);
}
}
I think this should work. This algorithm works with O(n) and no extra space. Idea is to make sure we print a node only when we know the node is in order even considering the other tree. Otherwise we move one level in first tree in the direction where the root node from the other tree is going to be in order.
Just had this question on my onsite interview. Best answer is to build an iterator based on a stack. Its is basically doing a depth first search.
Iterator logic:
1. from root add right node (if has one), current node and left node, repeat this step for left node.
2. when poping from stack, check if the node at top is the right node of the poped one. If so, then repeat step 1 for the left node of the node at the top of stack.
3. use the iterator to print in sorted order.
Time: O(n)
Space: O(log). By the way, you algorithm is also O(n), because thats the size of the stack used in your recursion.
public class TreeIterator {
private Stack<TreeNode> stack = new Stack<TreeNode>();
public TreeIterator(TreeNode root) {
addInOrder(root);
}
private void addInOrder(TreeNode node) {
if (node == null) return;
if (node.right != null)
stack.add(node.right);
stack.offer(node);
addInOrder(node.left);
}
public boolean hasNext() {
return !stack.isEmpty();
}
public TreeNode next() {
if (stack.isEmpty())
return null;
TreeNode next = stack.poll();
if (!stack.isEmpty() && stack.peek() == next.right)
addInOrder(next.right.left);
return next;
}
}
Almost right, except the following change. You need to pop the next's rightChild and then call addInOrder(rightChild).
{{addInOrder(next.right.left); --> addInOrder(stack.pop());}}
Almost right, except the following change. You need to pop the next's rightChild and then call addInOrder(rightChild).
addInOrder(next.right.left); --> addInOrder(stack.pop());
/// -- Time Complexity is O(2*max(n,m)), where n is size of root1, and m is size of root2, let me know of any errors.
void inorder(struct node * root, int min, int max)
{
if(root == NULL) return;
inorder(root->left, min, max);
if((min <= root->val) && (root->val <=max))cout<<root->val<<" ";
inorder(root->right, min, max);
}
void print(struct node * root1, struct node * root2, int min, int max)
{
if((root1 == NULL) && (root2 == NULL)) return ;
if(root1 != NULL && root2 == NULL) {inorder(root1, min, max); return ;}
if(root2 != NULL && root1 == NULL) {inorder(root2, min, max); return ;}
if(root1->val < root2->val)
{
print(root1->left, root2, min, root1->val);
if((root1->val >= min) && (root1->val <= max)) cout<<root1->val<<" ";
print(root1->right, root2, root1->val, max);
}
else
{
print(root2->left, root1, min, root2->val);
if((root2->val >= min) && (root2->val <= max)) cout<<root2->val<<" ";
print(root2->right, root1, root2->val, max);
}
}
time: o( |n1| + |e1| ) + o(|n1| + |n2| + |e2|)
e1 and e2 are the non-leaf nodes in the tree.
space: O (|n1| * 2 + |e1| + |n2| + |e2|)
Is that correct?
rightDFSToStack(stack, root1);
dfsPrint(stack, root2);
void rightDFSToStack(stack, node) {
if (node == null) return;
rightDFSToStack(stack, node.right);
stack.push(node.val);
rightDFSToSTack(stack, node.left);
}
void dfsPrint(stack, node) {
if (node == null) return;
dfsPrint(stack, node.left);
while (!stack.isEmpty() && stack.peek() < node.val) {
print(stack.pop());
}
dfsPrint(stack, node.right);
}
A solution with O(n + m) time and O(1) space would be iterating through node successors on each tree and compare them node by node. Here is the Java code bellow:
public void printAsc(TreeNode aRoot, TreeNode bRoot) {
TreeNode nextA = minNode(aRoot);
TreeNode nextB = minNode(bRoot);
//Iterate node by node on each tree
while (nextA != null || nextB != null) {
if (nextA != null && nextB != null) {
if (nextA.data.compareTo(nextB.data) < 0) {
nextA = nextPrint(nextA);
else
nextB = nextPrint(nextB);
}
else if (nextA != null)
nextA = nextPrint(nextA);
else
nextB = nextPrint(nextB);
}
}
private TreeNode nextPrint(TreeNode n) {
System.out.println(n.data);
return successor(n);
}
private TreeNode successor(TreeNode n) {
if (n.right != null)
n = minNode(n.right);
else {
TreeNode child = n;
TreeNode p = child.parent;
while(p != null && child == p.right) {
child = p;
p = child.parent;
}
n = p;
}
return n;
}
private TreeNode minNode(TreeNode node) {
while (node.left != null)
node = node.left;
return node;
}
The right solution, already tested.
Idea, inorder travel two binary trees at the same time, and output the smaller one.
void print_two_binary_trees(Node* root1, Node *root2){ bool done = false; Node *cursor1 = root1, *cursor2= root2; stack<Node*> s1,s2; while(!done) { if(cursor1 != NULL && cursor2 != NULL) { s1.push(cursor1); cursor1 = cursor1->left; s2.push(cursor2); cursor2 = cursor2->left; } else if(cursor1 != NULL && cursor2 == NULL) { s1.push(cursor1); cursor1 = cursor1->left; } else if(cursor1 == NULL && cursor2 != NULL) { s2.push(cursor2); cursor2 = cursor2->left; } else if(cursor1 == NULL && cursor2 == NULL) { if(!s1.empty() && s2.empty()) { cursor1 = s1.top(); s1.pop(); cout << cursor1->data<<" "; cursor1 = cursor1->right; } else if(s1.empty() && !s2.empty()) { cursor2 = s2.top(); s2.pop(); cout << cursor2->data<<" "; cursor2 = cursor2->right; } else if(!s1.empty() && !s2.empty()) { if(s1.top()->data <= s2.top()->data) { cursor1 = s1.top(); s1.pop(); cout << cursor1->data<<" "; cursor1 = cursor1->right; } else { cursor2 = s2.top(); s2.pop(); cout << cursor2->data<<" "; cursor2 = cursor2->right; } } else { done = true; } } } }P.S
Inorder travel one tree will output the elements in one tree in ascending order
- Nova2358 January 24, 2012void stack_inorder_visit(Node *root){ bool done = false; stack<Node*> s; Node* cursor = root; while(!done) { if(cursor != NULL) { s.push(cursor); //place pointer to node on the stack //before traversing the node's left subtree cursor = cursor->left; //traverse the left subtree } else //backtrack from the empty subtree and //visit the node at the top of the stack; //however, if the stack is empty, you are //done { if (!s.empty()) { cursor = s.top(); s.pop(); cout << cursor->data<<" "; cursor = cursor->right; } else done = true; } } }