Google Interview Question Software Engineer / Developers
Team: ChromeCast
Country: United States
Interview Type: In-Person
Sounds reasonable!
Except the condition of one node as the child of another node. I guess that case needs to be exempted or else the given question cannot be solved.
This can work for any node in my opinion. If you swap a root node with any other node you can end up with 2 trees. That is one possibility. This is something that I would ask the interviewer though.
you can't. the root edge case is just one example. you have to find the split node of both nodes and verify that it isn't one of them before making the swap. you can find the split node relatively easily if you have parent pointers but otherwise you have to find (and store, since it's not a BST) the paths of both nodes from the root.
What about the case some is swapping the root with another element?
5
/ \
3 7
/ \ /
2 4 6
swap 5 and 7.
This should be something to ask the interviewer about.
#include <iostream>
typedef struct TreeNode{
TreeNode *right;
TreeNode *left;
int value;
}TreeNode;
bool swapTrees(TreeNode *root, TreeNode *node1, TreeNode *node2){
if (node1 == root || node2 == root){
return false;
}
std::pair<TreeNode*, int> p1 = findParent(root, node1);
std::pair<TreeNode*, int> p2 = findParent(root, node2);
if (p1.second == 0){
p1.first->left = node2;
} else if (p1.second == 1){
p1.first->right = node2;
}
if (p2.second == 0){
p2.first->left = node1;
} else if (p2.second == 1){
p2.first->right = node2;
}
}
std::pair<TreeNode*, int> findParent (TreeNode *root, TreeNode *node){
TreeNode* curr == root;
TreeNode* parent;
int side;
while (curr){
if (curr->value == node->value){
if (curr == node){
std::pair<TreeNode*, int> p;
return p;
}
}
if (curr->value < node->value){
child = 0;
parent = curr;
curr = node->left;
} else if (curr->value > node->value){
child = 1;
parent = curr;
curr = node->right;
}
}
return nullptr;
}
#include <iostream>
#include <algorithm>
using namespace std;
struct node {
int value;
struct node *left;
struct node *right;
explicit node(int value) : value(value),
left(nullptr), right(nullptr) {}
};
void tree_insert(node **root, int value) {
if (*root == nullptr) {
*root = new node(value);
}
else if ((*root)->value > value) {
tree_insert(&(*root)->left, value);
}
else {
tree_insert(&(*root)->right, value);
}
}
void tree_print(node *root) {
if (root == nullptr) return;
cout << root->value << " ";
tree_print(root->left);
tree_print(root->right);
}
void tree_free(node **root) {
if (*root == nullptr) return;
tree_free(&(*root)->left);
tree_free(&(*root)->right);
delete *root;
}
void find_node(node **root, int value, node **target) {
if (*root == nullptr) {
*target = nullptr;
}
*target = *root;
while (*target != nullptr && (*target)->value != value) {
if ((*target)->value > value) {
*target = (*target)->left;
}
else {
*target = (*target)->right;
}
}
}
void find_parent(node **root, node *node_1, node **parent) {
if (*root == nullptr) {
*parent = nullptr;
}
node *target = *root;
while (target != nullptr && target->left != node_1
&& target->right != node_1) {
if (target->value > node_1->value) {
target = target->left;
}
else {
target = target->right;
}
}
*parent = target;
}
void swap_nodes(node **node_1, node **node_2) {
swap((*node_1)->left, (*node_2)->left);
swap((*node_1)->right, (*node_2)->right);
swap((*node_1)->value, (*node_2)->value);
}
void swap_root_node(node **root, node **node_1) {
//std::cout << "Pointer address node_1 = " << static_cast<void*>(*node_1) << std::endl;
node *parent_node_1 = nullptr;
find_parent(&(*root), *node_1, &parent_node_1);
if (parent_node_1->left == *node_1) {
swap_nodes(root, node_1);
parent_node_1->left = *root;
}
else {
swap_nodes(root, node_1);
parent_node_1->right = *root;
}
*root = *node_1;
}
void swap_root_root_child(node **root, node **root_child) {
if ((*root)->left == *root_child) {
swap_nodes(root, root_child);
(*root_child)->left = *root;
}
else {
swap_nodes(root, root_child);
(*root_child)->right = *root;
}
*root = *root_child;
}
void swap(node **root, node **n1, node **n2) {
if(*root == *n1 || *root== *n2) {
// root -> root_child.
if(*n1 == *root && (*n2 == (*n1)->left
|| *n2 == (*n1)->right)){
swap_root_root_child(root, n2);
} else if(*n2 == *root && (*n1 == (*n2)->left
|| *n1 == (*n2)->right)) {
swap_root_root_child(root, n1);
} else {
// root -> node.
if(*n1 == *root) {
swap_root_node(root, n2);
} else {
swap_root_node(root, n1);
}
}
} else {
// node -> node.
swap_nodes(n1, n2);
}
}
int main(int argc, char **argv) {
node* root = nullptr;
tree_insert(&root, 5);
tree_insert(&root, 10);
tree_insert(&root, 3);
tree_insert(&root, 1);
tree_insert(&root, 4);
tree_insert(&root, 9);
tree_insert(&root, 15);
tree_print(root); cout << endl;
node *node_1 = nullptr;
node *node_2 = nullptr;
find_node(&root, 3, &node_1);
find_node(&root, 10, &node_2);
swap(&root, &node_1, &node_2);
tree_print(root); cout << endl;
tree_free(&root);
return 0;
}
Java Solution:
public void bTreeSwapTwoNodes(){
Node root = getNode();
System.out.println( " \n\nBinary Tree swap two node" );
HashMap<Integer, Node> map = new HashMap<Integer, Node>();
int val1 = 1;
int val2 = 6;
// if(val1 == val2) {}
if(root.data == val1) {
map.put(val1, root);
} else if(root.data == val2) {
map.put(val2, root);
}
printBFS(root);
findToSwap(root, val1, val2, map);
Node parent1 = map.get(val1);
Node node1 = parent1;
if(parent1 != root) {
if( parent1.left.data == val1 ) {
node1 = parent1.left;
} else if( parent1.right.data == val1 ) {
node1 = parent1.right;
}
}
Node parent2 = map.get(val2);
Node node2 = map.get(val2);
if(parent2 == root) {
node2 = parent2;
} else if( parent2.left.data == val2 ) {
node2 = parent2.left;
} else if( parent2.right.data == val2 ) {
node2 = parent2.right;
}
if(parent1 != root) {
if( parent1.left.data == val1 ) {
parent1.left = node2;
} else if( parent1.right.data == val1 ) {
parent1.right = node2;
}
}
if(parent2 != root) {
if( parent2.left.data == val2 ) {
parent2.left = node1;
} else if( parent2.right.data == val2 ) {
parent2.right = node1;
}
}
Node templeft = node1.left;
Node tempright = node1.right;
node1.left = node2.left;
node1.right = node2.right;
node2.left = templeft;
node2.right = tempright;
printBFS(root);
}
private void findToSwap(Node node, int val1, int val2, Map<Integer, Node> map){
ArrayDeque<Node> que = new ArrayDeque<Node>();
que.offerLast( node );
while( !que.isEmpty() && map.size() < 2) {
Node n = que.pollFirst();
if (n.left != null) {
que.offerLast(n.left);
if (n.left.data == val1) {
map.put(val1, n);
} else if (n.left.data == val2) {
map.put(val2, n);
}
}
if (n.right != null) {
que.offerLast(n.right);
if (n.right.data == val1) {
map.put(val1, n);
} else if (n.right.data == val2) {
map.put(val2, n);
}
}
}
}
private void printBFS(Node root){
ArrayDeque<Node> que = new ArrayDeque<Node>();
que.offerLast( root );
System.out.print("\n\n Printing BFS: ");
while( !que.isEmpty() ) {
Node node = que.pollFirst();
System.out.print("\t->\t" + node.data);
if (node.left != null) {
que.offerLast(node.left);
}
if (node.right != null) {
que.offerLast(node.right);
}
}
}
Above code can be easily modified to swap multiple values by extracting some of the swap code..
public static class Node {
public Integer data = 0;
public Node left;
public Node right;
public Node() {}
public Node(Integer data) {
this.data = data;
}
}
public Node getNode() {
Node root = new Node( 5 );
root.left = new Node( 3 );
root.left.left = new Node( 1 );
root.left.right = new Node( 4 );
root.right = new Node( 9 );
root.right.left = new Node( 6 );
return root;
}
I see many complex solutions / can this not just be done with a standard
tree walk...
note that if you plan to swap a leaf with another it will close up the tree on that leaf
but the questions is vague about how much we swap
The example questions is satisfied
public void swapNodes(TreeNode first, TreeNode second) {
// swap children
TreeNode tempLeft = first.getLeft();
TreeNode tempRight = first.getRight();
first.setLeft(second.getLeft());
first.setRight(second.getLeft());
second.setLeft(tempLeft);
second.setRight(tempRight);
swapNodesR(this.root, first, second);
}
public void swapNodesR(TreeNode subtree, TreeNode first, TreeNode second) {
// walk the tree
if(subtree == null)
return;
TreeNode left = subtree.getLeft();
TreeNode right = subtree.getRight();
if(left == first) {
subtree.setLeft(second);
} else if(left == second) {
subtree.setLeft(second);
} else {
swapNodesR(left, first, second);
}
if(right == second) {
subtree.setRight(first);
} else if(right == second) {
subtree.setRight(first);
} else {
swapNodesR(right, first, second);
}
} // we have to do a tree walk and could walk all of it so O(N) N amount of nodes
public void swapNodes(TreeNode first, TreeNode second) throws TreeSwapException {
if(first == root || second == root)
throw new TreeSwapException(“Not allowed to swap root”);
if(!first.hasAllChildren() || !second.hasAllChildren())
throw new TreeSwapException(“Subtrees will full children only to swap”);
.
.
.
Should just be swapping data, not code needed here.
void swap (Node* a, Node* b)
{
if ( !a || !b ) return;
T data = a->data; // assume copy semantics of T
a.data = b.data;
b.data = data;
}
. 5
. / \
. 3 7
./\ / \
2 4 6 8
swap 7 and 3
. 5
. / \
. 3 7
./\ / \
2 4 6 8
swap 3 & 7;
. 3
. / \
. 5 4
./\
2 7
./ \
6 8
swap 5 & 7;
. 7
. / \
. 6 5
. / \
. 3 8
./ \
2 4
public static class Sol_1 {
//n1 && n2 should not be null
public static Node swap(Node r, Node n1, Node n2) {
if (r == null)
return null;
if (r == n1) {
r = n2;
if (childSwap(n1, n2))
return r;
} else if (r == n2) {
r = n1;
if (childSwap(n2, n1))
return r;
}
r.left = swap(r.left, n1, n2);
r.right = swap(r.right, n1, n2);
return r;
}
//return true if swapped with child
private static boolean childSwap(Node r, Node c) {
if (r.left == c) {
Node cl = c.left;
c.left = r;
r.left = cl;
return true;
} else if (r.right == c) {
Node cr = c.right;
c.right = r;
r.right = cr;
return true;
}
return false;
}
}
#include <iostream>
typedef struct TreeNode{
TreeNode *right;
TreeNode *left;
int value;
}TreeNode;
bool swapTrees(TreeNode *root, TreeNode *node1, TreeNode *node2){
if (node1 == root || node2 == root){
return false;
}
std::pair<TreeNode*, int> p1 = findParent(root, node1);
std::pair<TreeNode*, int> p2 = findParent(root, node2);
if (p1.second == 0){
p1.first->left = node2;
} else if (p1.second == 1){
p1.first->right = node2;
}
if (p2.second == 0){
p2.first->left = node1;
} else if (p2.second == 1){
p2.first->right = node2;
}
}
std::pair<TreeNode*, int> findParent (TreeNode *root, TreeNode *node){
TreeNode* curr == root;
TreeNode* parent;
int side;
while (curr){
if (curr->value == node->value){
if (curr == node){
std::pair<TreeNode*, int> p;
return p;
}
}
if (curr->value < node->value){
child = 0;
parent = curr;
curr = node->left;
} else if (curr->value > node->value){
child = 1;
parent = curr;
curr = node->right;
}
}
return nullptr;
}
include <iostream>
typedef struct TreeNode{
TreeNode *right;
TreeNode *left;
int value;
}TreeNode;
bool swapTrees(TreeNode *root, TreeNode *node1, TreeNode *node2){
if (node1 == root || node2 == root){
return false;
}
std::pair<TreeNode*, int> p1 = findParent(root, node1);
std::pair<TreeNode*, int> p2 = findParent(root, node2);
if (p1.second == 0){
p1.first->left = node2;
} else if (p1.second == 1){
p1.first->right = node2;
}
if (p2.second == 0){
p2.first->left = node1;
} else if (p2.second == 1){
p2.first->right = node2;
}
}
std::pair<TreeNode*, int> findParent (TreeNode *root, TreeNode *node){
TreeNode* curr == root;
TreeNode* parent;
int side;
while (curr){
if (curr->value == node->value){
if (curr == node){
std::pair<TreeNode*, int> p;
return p;
}
}
if (curr->value < node->value){
child = 0;
parent = curr;
curr = node->left;
} else if (curr->value > node->value){
child = 1;
parent = curr;
curr = node->right;
}
}
return nullptr;
}
Here is how I did this in Java. I have the full code committed on my github SerialCoderer under JCollections repo
public void swapNodes(T firstValue, T secondValue) {
JTreeNode<T> firstValueParentNode = findParentNode(this.rootNode, new JTreeNode<T>(null), firstValue);
JTreeNode<T> secondValueParentNode = findParentNode(this.rootNode, new JTreeNode<T>(null), secondValue);
if (( (firstValueParentNode.getLeftNode() != null &&
secondValueParentNode.getLeftNode() != null)
&& firstValueParentNode.getLeftNode().isEqual(firstValue)
&& secondValueParentNode.getLeftNode().isEqual(secondValue))){
JTreeNode<T> tempNode = firstValueParentNode.getLeftNode();
firstValueParentNode.setLeftNode(secondValueParentNode.getLeftNode());
secondValueParentNode.setLeftNode(tempNode);
}else if (((firstValueParentNode.getRightNode() != null &&
secondValueParentNode.getRightNode() != null)
&& firstValueParentNode.getRightNode().isEqual(firstValue)
&& secondValueParentNode.getRightNode().isEqual(secondValue))) {
JTreeNode<T> tempNode = firstValueParentNode.getRightNode();
firstValueParentNode.setRightNode(secondValueParentNode.getRightNode());
secondValueParentNode.setRightNode(tempNode);
} else if (((firstValueParentNode.getLeftNode() != null &&
secondValueParentNode.getRightNode() != null)
&& firstValueParentNode.getLeftNode().isEqual(firstValue)
&& secondValueParentNode.getRightNode().isEqual(secondValue))) {
JTreeNode<T> tempNode = firstValueParentNode.getLeftNode();
firstValueParentNode.setLeftNode(secondValueParentNode.getRightNode());
secondValueParentNode.setRightNode(tempNode);
} else {
JTreeNode<T> tempNode = firstValueParentNode.getRightNode();
firstValueParentNode.setRightNode(secondValueParentNode.getLeftNode());
secondValueParentNode.setLeftNode(tempNode);
}
}
public <T extends Comparable<T>> JTreeNode<T> findParentNode(
JTreeNode<T> node, JTreeNode<T> parentNode, T value) {
JTreeNode<T> tempNode = null;
if (node == null)
return null;
if (node.isEqual(value)) {
tempNode = parentNode;
} else {
if (tempNode == null)
tempNode = findParentNode(node.getLeftNode(), node, value);
if (tempNode == null)
tempNode = findParentNode(node.getRightNode(), node, value);
}
return tempNode;
}
BinaryTreeNode MirrorOfBinaryTree(BinaryTreeNode root)
{
BinaryTreeNode temp;
if(root)
{
MirrorofBinaryTree(root.getLeft());
MirrorofBinaryTree(root.getRight());
// Swap the pointers in this node
temp = root.getLeft();
root.setLeft(root.GetRight()));
root.setRight(temp);
}
}
the signature was something like this
class TreeNode {
int v;
TreeNode left,right;
TreeNode(int v)
{
this.v=v;
left=null;
right=null;
}
}
void swap(TreeNode root, int x,int y) // you can change return type if needed.
{
}
/*after swapping the tree needs to be like that mentioned in the question. The entire tree need not be mirrored*/
package dmitry.com.tree;
import java.util.LinkedList;
import org.junit.Test;
public class TreeSwope {
private LinkedList<Node> tree = new LinkedList<Node>();
Node n5;
Node n3;
Node n4;
Node n7;
Node n2;
Node n6;
public TreeSwope() {
n5 = new Node(5);
n3 = new Node(3);
n7 = new Node(7);
n2 = new Node(2);
n4 = new Node(4);
n6 = new Node(6);
n5.setRight(n7);
n5.setLeft(n3);
n3.setLeft(n2);
n3.setRight(n4);
n7.setLeft(n6);
}
@Test
public void test() {
System.out.println(n3.getLeft().getVal());
TreeSwope tree = new TreeSwope();
tree.swap(n3, n7);
System.out.println(n3.getLeft().getVal());
}
public void printTree() {
}
public void swap(Node n1, Node n2) {
Node temp = n1;
n1.setVal(n2.getVal());
n1.setLeft(n2.getLeft());
n1.setRight(n2.getRight());
n2.setVal(temp.getVal());
n2.setLeft(temp.getLeft());
n2.setRight(temp.getRight());
}
public class Node {
Node(int val) {
this.val = val;
}
private int val;
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = val;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
private Node right;
private Node left;
}
}
The idea is
1. Perform level order traversal and put into queue for entire tree
2. when the first element is found start putting element from thereon to stack till second element is found inclusive.
3. when second element is found, pop all elements from stack and append to the (Q)
#include<stdio.h>
#include<iostream>
#include<stack>
using namespace std;
#define MAX 500
#define MAXQ 500
#define SMX 500
int aux[SMX];
int aux_f,aux_r;
struct node{
int data;
node *left,*right;
};
typedef struct node *NODE;
//build tree
NODE build(int arr[],int len,int index){
NODE tmp = NULL;
if(index <= (len-1)){
tmp = (NODE)malloc(sizeof(struct node));
tmp->left = build(arr,len,2*index+1);
tmp->data = arr[index];
tmp->right = build(arr,len,2*index+2);
}
return tmp;
}
void enqueue(NODE *q,NODE element,int *f,int *r){ q[(*r)++] = element; }
NODE dequeue(NODE *q,int *f){
(*f)++;
return q[*f - 1];
}
NODE *CreateQ(int *f,int *r){
NODE *tmp =(NODE *)malloc(sizeof(NODE *)*MAX);
*f = *r = 0;
return tmp;
}
void add_2_queue(int xq[],int val,int *f,int *r){
xq[(*r)++] = val;
}
void DisplayLevelOrder(NODE root){
int front;
int rear;
int f,r;
f=r= 0;
int xq[MAXQ];
memset(xq,0,MAXQ);
NODE tmp=root;
NODE *queue = CreateQ(&front,&rear);
while(tmp){
//printf("%d ", tmp->data);
cout << " Data=" << tmp->data;
add_2_queue(xq,tmp->data,&f,&r);
if(tmp->left)
enqueue(queue,tmp->left,&front,&rear);
if(tmp->right)
enqueue(queue,tmp->right,&front,&rear);
tmp = dequeue(queue,&front);
}
int n1,n2;
//n1 to come before n2
cout << " Enter n1 and n2:" << endl;
cin >> n1 >> n2;
int put2stack = 0;
stack<int> ss;
aux_f = aux_r = 0;
int i=0;
while(i <= r){
if(xq[i] == n1){
cout << " put2stack state 1" << endl;
put2stack = 1;
}
if(put2stack == 1){
cout << " put2stack state 1..checking for n2" << endl;
//wait for the puttostack become 2
while((i <= r) && put2stack != 2){
cout << " put2stack state pushing to stack" << endl;
ss.push(xq[i]);
if(xq[i] == n2)
put2stack = 2;
else
i++;
}
}
//lets pop all from stack and put into queue
if(put2stack == 2){
cout << " put2stack was 2 ..so poping" << endl;
while(!ss.empty()){
aux[aux_r++] = ss.top();
ss.pop();
}
put2stack = 0;
}else{ //put into queue
cout << " put2stack state was 0 so..putting to queue" << endl;
aux[aux_r++] = xq[i];
}
i++;
}
}
int main(){
int arr[]={5,3,7,2,4,6};
NODE root = NULL;
int len = sizeof(arr)/sizeof(arr[0]);
root = build(arr,len,0);
DisplayLevelOrder(root);
cout << " New tree:" << endl;
NODE rt = NULL;
rt = build(aux,aux_r-1,0);
DisplayLevelOrder(rt);
}
As someone pointed out, if you are swapping subtrees, then it is not possible to handle if one of the input nodes is root. Next, how are the nodes presented to us? Pointers to the treeNodes itself? Do treeNodes also have parent pointers set?
Assuming that we don't have parent pointers and references to treeNodes are inputs, we can do a preorder traversal (equivalent to BFS) and determine the parent nodes and then swap the children.
- cool.fire.ra June 25, 2014public class MyTree{ TreeNode root; public boolean swapSubTrees(TreeNode n1, TreeNode n2){ if(n1 == root || n2==root) return false; /*search for parents*/ LinkedList<TreeNode> Q = new LinkedList<TreeNode>(); TreeNode p1=null, p2=null, curr=root; if(curr!=null) Q.add(curr); else return false; while(! Q.isEmpty()){ cur = Q.remove(); if(cur.left == n1 || cur.right == n1) p1=cur; if(cur.left == n2 || cur.right == n2) p2=cur; if(p1 == null || p2 == null){ if(cur.left!=null) Q.add(cur.left); if(cur.right!=null) Q.add(cur.right); } else break; } if(p1==null || p2==null) return false; else{ if(p1.left == n1) p1.left = n2; else p1.right = n2; if(p2.left == n2) p2.left = n1; else p2.right = n1; } } public class TreeNode<K,V>{ K key; V val; TreeNode left; TreeNode right; /* Assume appropriate constructors and insert fns exist*/ } }