Linkedin Interview Question
Country: United States
Interview Type: Phone Interview
I think // Working base condition
if( root.Left == NULL && root.Right == NULL)
{
return root.Left;
}
should return root not root.left
#include <iostream>
using namespace std;
class node
{
private:
node * left;
node * right;
public:
int val;
node(int nval) : val(nval) , left(NULL) , right(NULL){}
void setRight(node * right){
this->right = right;
}
void setLeft(node * left){
this->left = left;
}
node * getLeft(){
return this->left;
}
node * getRight(){
return this->right;
}
};
class RightLeafBinaryTree
{
private:
node * head;
public:
RightLeafBinaryTree(int val) : head(new node(val)) {}
node * getHead(){
return head;
}
void setHead(node * new_head){
head = new_head;
}
void addNode(int val){
node * iter = head;
while(iter->getLeft() && iter->getRight())
iter = iter->getLeft();
if(! iter->getLeft())
iter->setLeft(new node(val));
else
iter->setRight(new node(val));
}
void flipNodePtrs(node * parent_node){
node * left_child = parent_node->getLeft();
left_child->setLeft(parent_node->getRight());
left_child->setRight(parent_node);
parent_node->setLeft(NULL);
parent_node->setRight(NULL);
}
node * flipTree(node * root){
if(! root || ! root->getLeft())
return root;
if(! root->getLeft()->getLeft()){
node * new_root = root->getLeft();
flipNodePtrs(root);
return new_root;
}
node * new_root = flipTree(root->getLeft());
flipNodePtrs(root);
return new_root;
}
void printTree(node * head)
{
if(head){
cout << head->val << " ";
cout << " L ";
if(head->getLeft())
cout << head->getLeft()->val << " ";
else
cout << "NULL" << endl;
cout << " R ";
if(head->getRight())
cout << head->getRight()->val << endl;
else
cout << "NULL" << endl;
printTree(head->getLeft());
printTree(head->getRight());
}
}
};
int main(){
RightLeafBinaryTree bt(1);
bt.addNode(2);
bt.addNode(3);
/*bt.addNode(4);
bt.addNode(5);
bt.addNode(6);
bt.addNode(7);*/
bt.setHead(bt.flipTree(bt.getHead()));
bt.printTree(bt.getHead());
return 0;
}
What about using a queue to generate a breadth first search through the tree and when it is done then:
1. take three first elements from the queue A, B, C and then: B->right = A, B->left = C,
2. assign curRight = C
3. while(queue is not empty)
- take two elements A B from the queue
- A->right = curRight, A->left = B
- curRight = A
4. set root = curRight
Handle the edge cases.
Thank you for contributing this question, Prateek.
I may have clarified if the tree is to be flipped in place or a new one to be created. In an interview it may be worth mentioning that the order in which we insert nodes in the new tree is a depth-first ordering of the nodes in the original tree, with the left node being traversed before the right. In its most simplest form, the order of the new tree could be derived with this recursion:
static void TransformTree(Node node, ref Node newTree)
{
if (node == null) { return; }
TransformTree(node.Left, ref newTree);
TransformTree(node.Right, ref newTree);
AddNode(node.Value, ref newTree);
}
This probably makes it easiest to not lose oneself in the operations necessary to swap the node references. AddNode could then be implemented like this:
static void AddNode(int value, ref Node node)
{
if (node.Value == -1)
node.Value = value;
else if (node.Left == null)
node.Left = new Node { Value = value };
else
{
node.Right = new Node { Value = value };
node = node.Right;
}
}
In order to not traverse nodes repeatedly during insertion and increase time complexity of the algorithm, I am using a C# reference to the node parameter and update its value to its right child whenever a level is completed. I have chosen to represent empty nodes with a value of "-1", instead of passing a reference to null, because I am not returning the root of the new tree.
I have not made a comparison with your original solution in terms of line count, but you may want to give this solution consideration in terms of its relative comprehensibility, and if a solution is desirable that keeps the original tree intact.
Thank you for contributing this question, Prateek.
I may have clarified if the tree is to be flipped in place or a new one to be created. In an interview it may be worth mentioning that the order in which we insert nodes in the new tree is a depth-first ordering of the nodes in the original tree, with the left node being traversed before the right. In its most simplest form, the order of the new tree could be derived with this recursion:
static void TransformTree(Node node, ref Node newTree)
{
if (node == null) { return; }
TransformTree(node.Left, ref newTree);
TransformTree(node.Right, ref newTree);
AddNode(node.Value, ref newTree);
}
This probably makes it easiest to not lose oneself in the operations necessary to swap the node references. AddNode could then be implemented like this:
static void AddNode(int value, ref Node node)
{
if (node.Value == -1)
node.Value = value;
else if (node.Left == null)
node.Left = new Node { Value = value };
else
{
node.Right = new Node { Value = value };
node = node.Right;
}
}
In order to not traverse nodes repeatedly during insertion and increase time complexity of the algorithm, I am using a C# reference to the node parameter and update its value to its right child whenever a level is completed. I have chosen to represent empty nodes with a value of "-1", instead of passing a reference to null, because I am not returning the root of the new tree.
I have not made a comparison with your original solution in terms of line count, but you may want to give this solution consideration in terms of its relative comprehensibility, and if a solution is desirable that keeps the original tree intact.
struct binary_node* flip(struct binary_node* root)
{
if(root != NULL)
{
struct binary_node* left = root->left;
struct binary_node* right = root->right;
while(left != NULL)
{
struct binary_node* left_left = left->left;
struct binary_node* left_right = left->right;
left->left = right;
left->right = root;
root = left;
left = left_left;
right = left_right;
}
}
return root;
}
A working code:
void flipTree(tnode **tree){
tnode * temp = *tree;
tnode * temp2 = temp->right;
temp->right = NULL;
tnode * temp3;
while(temp->left!=NULL){
temp3 = (temp->left)->right;
temp->left->right = temp2;
temp = temp->left;
temp2 = temp3;
} //make tree such that right of left node of parent points to parent's right eg.
/*
40 40
/ \ => /
30 60 30 -- 60
*/
tnode *stop = temp;
temp = *tree;
temp2 = temp->left;
temp->left=NULL;
temp3 = temp2->left;
while(temp!=stop){ //now reverse the pointer from 30 to 40 and make 30 as root
temp2->left = temp;
temp=temp2;
temp2 = temp3;
if(temp2!=NULL)
temp3 = temp2->left;
}
*tree = temp;
}
Here is my code with O(n) time and O(1) space.
Node * flip(Node *root){
if(root == NULL) return NULL;
Node *parent, *sibling;
Node *cur = root;
parent = cur->left;
sibling = cur->right;
cur->left = NULL;
cur->right = NULL;
while(parent != NULL){
Node* newParent = parent->left;
Node* newSibling = parent->right;
parent->left = sibling;
parent->right = cur;
cur = parent;
parent = newParent;
sibling = newSibling;
}
return cur;
#include<iostream>
using namespace std;
class Node {
public:
Node* left;
Node* right;
int data;
Node(const Node& aNode) {
data = aNode.data;
left = 0;
right = 0;
}
};
Node* flipTree(Node* root, Node* newRoot = 0) {
if(!root) return 0;
if(!root->left && !root->right) {
newRoot = new Node(*root);
return newRoot;
}
Node* n = flipTree(root, newRoot);
n->left = new Node(*root->right);
n->right = new Node(*root);
return n->right;
}
The previous one is gonna blow!
class Node {
public:
Node* left;
Node* right;
int data;
Node(const Node& aNode) {
data = aNode.data;
left = 0;
right = 0;
}
};
Node* flipTree(Node* root, Node* newRoot = 0) {
if(!root) return 0;
if(!root->left && !root->right) {
newRoot = new Node(*root);
return newRoot;
}
Node* n = flipTree(root->left, newRoot);
n->left = new Node(*root->right);
n->right = new Node(*root);
return n->right;
}
TreeNode<String> newCurrRoot = null, newRoot = null, root = null;
public void doTurn(TreeNode<String> root) {
if(root.hasLeft()) {
doTurn(root.getLeft());
} else {
newRoot = breakLinks(root);
}
if(root.hasRight()) {
newCurrRoot.setLeft(root.getRight());
}
if(newCurrRoot != null) {
newCurrRoot.setRight(root);
}
newCurrRoot = breakLinks(root);
}
private TreeNode<String> breakLinks(TreeNode<String> root) {
if(root == null) return root;
root.setLeft(null);
root.setRight(null);
return root;
}
I have either failed to understand the requirement or some solutions posted above but this is my version. Visits only left nodes and reuses the nodes to make the new one. I would be glad to have some feedback. Sorry I haven't checked for edge/null cases.
Here is my code with O(n) time and O(1) space
TreeNode* flipTree(TreeNode* root) {
flipTreeHelper(root);
TreeNode* prev = nullptr;
while (root) {
TreeNode* temp = root->right;
root->right = prev;
prev = root;
root = root->left;
prev->left = temp;
}
return prev;
}
void flipTreeHelper(TreeNode* root) {
if (!root->left && !root->right) { return; }
flipTreeHelper(root->left);
root->left->right = root->right;
root->right = nullptr;
}
time: O(h) and O(1) space -- where h is the height of the tree
public static Node reverse(Node root) {
if (root == null) {
return null;
}
Node curr = root, left = null, parent = null, sibling = null;
while (curr.left != null) {
left = curr.left;
curr.left = sibling;
sibling = curr.right; // next sibling
curr.right = parent;
parent = curr; // next parent
curr = left;
}
curr.left = sibling;
curr.right = parent;
return curr;
}
private static class Node {
protected Node left;
protected Node right;
protected int val;
}
This one works
public static Node inverse(Node n)
{
if(n == null)
{
return null;
}
if(n.left!=null)
{
if(n.left.left==null && n.left.right==null)
{
//bottom case
rootTree = n.left;
rootTree.left = n.right;
rootTree.right = n;
return rootTree.right;
}
}
Node root = inverse(n.left);
root.left = n.right;
root.right = n;
return root.right;
}
public static Node flippityFlip(Node n) {
if(n == null) {
return n;
}
Stack<Node> S = new Stack<Node>();
// push all left nodes into stack.
while(n != null) {
S.push(n);
n = n.left;
}
Node root = S.peek();
while(!S.isEmpty()) {
flip(S.pop(), S.peek());
}
return root;
}
// takes node and its parent, and flips the node.
public static void flip(Node n, Node p) {
if(p==null) {
n.left = null;
n.right = null;
} else {
n.left = p.right;
n.right = p;
}
}
Kinda DFS, without recursion Node (id, left, right)
Node flipTree(Node root){
ArrayDeque stack = new ArrayDeque();
Node currentNode = root;
while (currentNode.left != null){
stack.addLast(currentNode);
currentNode = currentNode.left;
}
root = stack.pollLast();
currentNode = root;
while (!stack.isEmpty()){
Node temp = stack.pollLast();
currentNode.left = temp.right;
currentNode.right = temp;
currentNode = tempt;
}
return root;
}
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
- PrateekS. July 29, 2014