Linkedin Interview Question


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 9 vote

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;
}

- PrateekS. July 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very clean. This is good ..

- Anonymous July 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think // Working base condition
if( root.Left == NULL && root.Right == NULL)
{
return root.Left;
}

should return root not root.left

- Ravi July 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Ravi

You're right - That was a copy/paste error.
It should be root.

- PrateekS. July 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

root.Left.Left = root.Right;
root.Left.Right = root;
root.Left = NULL;
root.Right = NULL;

the logic seems not correct. your tree is broken apart and never be able to connect back.

- Anonymous September 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

can someone reply to this question in C#

- Anonymous July 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The code that PrateekS. wrote would work for any structure like

public class Tree
{
	Tree left;
	Tree right;
	int data;
}

It wouldnt matter what language. It would work just as well in C# or Java..

- Anonymous July 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public Node treeRev(Node n, int count)
	{
		if(n.left == null && n.left == null)
		{			
			return n;
		}
	
		Node newHead = treeRev(n.left, count+1);
		n.left.left = n.right;
		n.left.right = n;
		if(count == 0)
		{
			n.left = null;
			n.right = null;
		}
		return newHead;
	}

- sp!de? July 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Charanjit Ghai July 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- joe kidd July 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Name August 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Name August 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static TreeNode FlipTree (TreeNode n, TreeNode l, TreeNode r){
		TreeNode left = n.left;
		TreeNode right = n.right;
		n.left = l;
		n.right = r;
		if(left == null)
			return n;
		else
			return FlipTree (left,right, n);

	}

- alex.fantasy August 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- wjian@yahoo-inc.com September 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Post order for the left tree is same as the preOrder for the right tree. So why cant we use postOrder traversal and construct a new tree?

- Anonymous September 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Shobhank September 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static TreeNode updown(TreeNode root) {
if(root.left == null) return root;
TreeNode n = updown(root.left);
TreeNode curr = n;
while(n.right != null) n = n.right;
n.left = new TreeNode(root.right.data);
n.right = new TreeNode(root.data);
return curr;
}

- Xinlu September 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

- xjma1123 September 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- apurusha October 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- apurusha October 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Asif Garhi October 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solution
1)Treat the left subtree of the tree as singly linklist and reverse it.
2) then take the mirror of the tree.

- Anonymous October 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Cloud_cal October 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How can this be O(1) space?
flipTreeHelper re-curses along left links from root to leftmost leaf. This is O(h) where h is depth of tree (in this problem it is O(n) as n/2 <= h <= n)

- Anonymous January 23, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
       }

- muki-buki November 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static Node Flip(Node root) {

	if (root == null) {
		return null;
	}
	
	if (root.left == null) {
		return root;
	}
	
	Node flippedRoot = Flip(root.left);
	root.left.left = root;
	root.left.right = root.right;
	return flippedRoot;

}

- pavel.kogan January 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
        }

- Anonymous January 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	    }
	}

- Anonymous April 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class tree* prev = NULL;
class tree* newRoot = NULL;
void convertTree(class tree* root)
{
    if(root)
    {
        prev = root;
        newRoot = prev;
        convertTree(root->left);
    }
    if(prev && root && prev != root)
    {
        prev->left = root->right;
        prev->right = root;
        root->left = NULL;
        prev = root;
    }
}

- skum June 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- bulzak September 28, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More