CareerCup

Possible ways to find the right node first
1) Check if the parent has right children, if yes get the next left child if not the right.
2) If parents doesn't have right child, go to its parent with level++ and go down on the right of that parent using the same first condition recursively till that level becomes zero.
3) If didn't find, return null.

I may be wrong, please correct me.

@uuuouou you could do better

1) use parent pointer to find the level of the two nodes. --> O(height) = O(lgn) for balanced tree and O(n) for unbalanced tree.

2) Now, keep two pointers: one pointing to the deeper node and second pointing to the shallower node. Also keep two lists: one for putting the nodes in the path from first node to the lowest common ancestor. Another for putting nodes in the path from second node to LCA node in reverse order (i.e. always insert in front of the list).

3) Move deeper pointer up (one parent each time) for delta=level-level2 times. Also add nodes to the proper list accordingly. --> O(lgn) for balanced tree and O(n) for unbalanced tree.

4) Now, two pointers are leveled. Move up both pointer at the same time up one parent until the pointers hit to the common parent (lca). While going up we already populate first list by the nodes in the path from first node to lca in forward order; and populated 2nd list by the nodes in the path from second node to lca in reverse order. --> O(lgn) for balanced tree and O(n) for unbalanced tree

5) concat second list with first list and voila! we have our answer. --> O(1)

overall complexity is O(lgn) for balanced tree and O(n) for unbalanced tree.

Since this is listed as a C interview question (not C++) I did an answer in C99.

Most of the code is test cases and linked-list handling (for the paths). The real solution is the 3 routines at the beginning

The algorithm is simple:
(1) Find a pointer to the right sibling O(n) worst case: chosen node is leftmost child on lowest level of full binary tree that has no other children at our node's depth.
(2) Create a path between the initial node and the right sibling by following their parent pointers up until they reach a common ancestor. O(path length)

Finding the right sibling is also a simple recursive routine:
If this is the left child and the parent has a right child, that is this node's right sibling. Otherwise, keep finding right siblings of the parent and choose the leftmost of their children. If none of the parent's right siblings has children, there is no right sibling for this node.

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef struct node_struct {
  struct node_struct* left;
  struct node_struct* right;
  struct node_struct* parent;
  int data;
} node;

typedef struct path_node_struct {
  struct path_node_struct* next;
  node* path_elt;
} path_node;

void delete_path(path_node* head);
path_node* empty_path();
void push_onto_front_of_path(path_node** head, node* path_elt);
void move_first_onto_front_of_path(path_node** to_move, path_node** dest);

/**
 * Return a path as a linked list to the first node to the right on
 * the same level as this node.  Return empty path if there is no node
 * to the right
 */
path_node* path_to_right(node*cur){
  node* right_neighbor(node* cur);
  path_node* path_between_siblings(node*start, node*end);
  if(cur == NULL){ return NULL; }
  node* neighbor;
  if(cur->parent == NULL){
    return NULL;
  }else{
    neighbor = right_neighbor(cur);
    if(neighbor == NULL){
      return NULL;
    }else{
      return path_between_siblings(cur, neighbor);
    }
  }
}

/**
 * Return a pointer to the first node to the right of cur on the same
 * level or NULL if there is no such node.
 */
node* right_neighbor(node* cur){
  node*parent_of_sibling;
  
  assert(cur != NULL);
  if(cur->parent == NULL){ //At root
    return NULL;
  }else{
    if(cur->parent->left == cur){ //Am left child
      if(cur->parent->right != NULL){ //With a right sibling
	return cur->parent->right;
      }
    } 
    //Am right child or don't have a right sibling from same parent
    //So must look at children of right siblings of parent in order
    parent_of_sibling = right_neighbor(cur->parent);
    while(parent_of_sibling != NULL){
      if(parent_of_sibling->left != NULL){
	return parent_of_sibling->left;
      }else if(parent_of_sibling->right != NULL){
	return parent_of_sibling->right;
      }
      parent_of_sibling = right_neighbor(parent_of_sibling);
    }
    //No siblings of my parent have appropriate children thus I have no
    //right neighbor
    return NULL;
  }
}

/**
 * Given that start and end are on the same level, return the path
 * between them as a linked list.
 */
path_node* path_between_siblings(node*start, node*end){
  path_node* start_to_LCA = empty_path();
  path_node* LCA_to_end = empty_path();
  node* start_ancestor = start;
  node* end_ancestor = end;
  assert(start != NULL);
  assert(end != NULL);
  while(start_ancestor != end_ancestor){
    assert(start_ancestor != NULL); //Verify that really were siblings
    assert(end_ancestor != NULL);
    push_onto_front_of_path(&start_to_LCA, start_ancestor);
    push_onto_front_of_path(&LCA_to_end, end_ancestor);
    start_ancestor = start_ancestor->parent;
    end_ancestor = end_ancestor->parent;
  }
  push_onto_front_of_path(&LCA_to_end, end_ancestor);
  while(start_to_LCA != NULL){
    move_first_onto_front_of_path(&start_to_LCA, &LCA_to_end);
  }

  return LCA_to_end;
}


///////////
// Path and Tree manipulation
///////////

void delete_path(path_node* head){
  while(head != NULL){
    path_node* next = head->next;
    free(head);
    head = next;
  }
}

path_node* empty_path(){
  return NULL;
}

void push_onto_front_of_path(path_node** head, node* path_elt){
  assert(head != NULL);
  path_node* new = (path_node*)malloc(sizeof(path_node));
  new->next = *head;
  new->path_elt = path_elt;
  *head = new;
}

void move_first_onto_front_of_path(path_node** to_move, path_node** dest){
  path_node* temp = *to_move;
  assert(to_move != NULL);
  assert(dest != NULL);

  if(temp != NULL){
    *to_move = temp->next;
    temp->next = *dest;
    *dest = temp;
  }else{
    //Moving the first of an empty list. Maybe this should log a 
    //warning somewhere. Doing nothing right now (though crashing in
    //debug
    assert(temp != NULL);
  }
}


void delete_tree(node* to_delete){
  if(to_delete == NULL) return;
  delete_tree(to_delete->left);
  delete_tree(to_delete->right);
  free(to_delete);
}

void print_tree(node* root, int depth){
  int i;
  if(root != NULL){
    print_tree(root->left, depth+1);
  }
  for(i = 0; i+1 < depth; ++i){
    printf("|");
  }
  if(root != NULL){
    printf("_%d @ (%d)\n",root->data, depth);
  }else{
    printf("_NULL @ (%d)\n", depth);
  }
  if(root != NULL){
    print_tree(root->right, depth+1);
  }
}


node* make_node(int value, node* left, node* right){
  node* to_ret = (node*)malloc(sizeof(node));
  to_ret->left = left;
  if(left != NULL){
    left->parent = to_ret;
  }
  to_ret->right = right;
  if(right != NULL){
    right->parent = to_ret;
  }
  to_ret->parent = NULL;
  to_ret->data = value;
  return to_ret;
}

void print_path(path_node* head){
  while(head != NULL){
    printf("%d->",(int)head->path_elt);
    head = head->next;
  }
  printf("\n");
}

/**
 * Test code (just uses assert, nothing fancy)
 */

int main(){
  ///////////////
  // Test path list
  ///////////////
  path_node* test_list = NULL;
  path_node* test_list2 = NULL;

  // Make list 56,2,1
  push_onto_front_of_path(&test_list, (node*)1);
  assert(test_list->path_elt == (node*)1);
  assert(test_list->next == NULL);

  push_onto_front_of_path(&test_list, (node*)2);
  assert(test_list->path_elt == (node*)2);
  assert(test_list->next != NULL);
  assert(test_list->next->path_elt == (node*)1);
  assert(test_list->next->next == NULL);

  push_onto_front_of_path(&test_list, (node*)56);
  assert(test_list->path_elt == (node*)56);
  assert(test_list->next != NULL);
  assert(test_list->next->path_elt == (node*)2);
  assert(test_list->next->next != NULL);
  assert(test_list->next->next->path_elt == (node*)1);
  assert(test_list->next->next->next == NULL);


  // Make a second list -56,-2,-1
  push_onto_front_of_path(&test_list2, (node*)-1);
  assert(test_list2->path_elt == (node*)-1);
  assert(test_list2->next == NULL);

  push_onto_front_of_path(&test_list2, (node*)-2);
  assert(test_list2->path_elt == (node*)-2);
  assert(test_list2->next != NULL);
  assert(test_list2->next->path_elt == (node*)-1);
  assert(test_list2->next->next == NULL);

  push_onto_front_of_path(&test_list2, (node*)-56);
  assert(test_list2->path_elt == (node*)-56);
  assert(test_list2->next != NULL);
  assert(test_list2->next->path_elt == (node*)-2);
  assert(test_list2->next->next != NULL);
  assert(test_list2->next->next->path_elt == (node*)-1);
  assert(test_list2->next->next->next == NULL);

  // Move second list elements onto the first
  move_first_onto_front_of_path(&test_list2, &test_list);

  assert(test_list2->path_elt == (node*)-2);
  assert(test_list2->next != NULL);
  assert(test_list2->next->path_elt == (node*)-1);
  assert(test_list2->next->next == NULL);

  assert(test_list->path_elt == (node*)-56);
  assert(test_list->next != NULL);
  assert(test_list->next->path_elt == (node*)56);
  assert(test_list->next->next != NULL);
  assert(test_list->next->next->path_elt == (node*)2);
  assert(test_list->next->next->next != NULL);
  assert(test_list->next->next->next->path_elt == (node*)1);
  assert(test_list->next->next->next->next == NULL);

  // Delete the lists
  delete_path(test_list); test_list = NULL;
  delete_path(test_list2); test_list2 = NULL;


  /////////////
  // Test Tree stuff
  /////////////

  node* empty_tree = NULL;
  node* single_node_tree = make_node(100, NULL, NULL);
  node* tree_with_one_right = 
    make_node
    (10,
     NULL,
     make_node(100, NULL, NULL)
     );

  node* tree_with_one_left =
    make_node
    (10,
     make_node(100, NULL, NULL),
     NULL
     );

  node* tree_with_both =
    make_node
    (10,
     make_node(20, NULL, NULL),
     make_node(40, NULL, NULL));
  
  node* complex_tree =
    make_node(1,
	      make_node(10,
			make_node(100,
				  make_node(1000, NULL, NULL),
				  NULL),
			make_node(200,
				  make_node(2000,NULL, NULL),
				  NULL)),
	      make_node(20, 
			NULL,
			make_node(300,
				  make_node(3000,NULL, NULL),
				  make_node(4000,NULL, NULL))));
  
  path_node* ans = NULL;

  ans = path_to_right(empty_tree);
  assert(ans == NULL);
  
  ans = path_to_right(single_node_tree);
  assert(ans == NULL);

  ans = path_to_right(tree_with_one_left);
  assert(ans == NULL);

  ans = path_to_right(tree_with_one_left->left);
  assert(ans == NULL);

  ans = path_to_right(tree_with_one_right->right);
  assert(ans == NULL);

  ans = path_to_right(tree_with_both->right);
  assert(ans == NULL);

  ans = path_to_right(tree_with_both->left);
  assert(ans != NULL);
  assert(ans->path_elt == tree_with_both->left);
  assert(ans->next->path_elt == tree_with_both);
  assert(ans->next->next->path_elt == tree_with_both->right);
  delete_path(ans);

  ans = path_to_right(complex_tree->left->left->left);
  assert(ans != NULL);
  assert(ans->path_elt == complex_tree->left->left->left);
  assert(ans->next->path_elt == complex_tree->left->left);
  assert(ans->next->next->path_elt == complex_tree->left);
  assert(ans->next->next->next->path_elt == complex_tree->left->right);
  assert(ans->next->next->next->next->path_elt == 
	 complex_tree->left->right->left);
  delete_path(ans);

  ans = path_to_right(complex_tree->left->right->left);
  assert(ans != NULL);
  assert(ans->path_elt == complex_tree->left->right->left);
  assert(ans->next->path_elt == complex_tree->left->right);
  assert(ans->next->next->path_elt == complex_tree->left);
  assert(ans->next->next->next->path_elt == complex_tree);
  assert(ans->next->next->next->next->path_elt == 
	 complex_tree->right);
  assert(ans->next->next->next->next->next->path_elt == 
	 complex_tree->right->right);
  assert(ans->next->next->next->next->next->next->path_elt == 
	 complex_tree->right->right->left);
  delete_path(ans);

  ans = path_to_right(complex_tree->right->right->right);
  assert(ans == NULL);

  delete_tree(single_node_tree);
  delete_tree(tree_with_one_right);
  delete_tree(tree_with_one_left);
  delete_tree(tree_with_both);
  delete_tree(complex_tree);
}

[Not a solution]
You shouldn't be disheartened by what happened. Microsoft is known for doing strange things in their interview process. Sometimes they already have a decision made about you, even before you enter the interview room. Interview is just a formality, because Microsoft has committed the interview.

The question wasn't too difficult, practice more next time! Hope you do well.

Has happened to me before. And now, I work at Microsoft.

The problem can be divided into two steps:
(1)find the first common ancestor of the two nodes
(2)find path from left node to ancestor, say it is leftPath,
find path from right node to ancestor, say it is rightPath,
then path = leftPath - ancestor + reverse(rightPath)
In implementation, we can combine those two steps together. Following is code in C++:

struct TreeNode{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode* parent;
	TreeNode(int value) : val(value) left(NULL), right(NULL), parent(NULL) {}
};
bool getPath(vector<TreeNode*>& path, TreeNode* start, TreeNode* dest)
{
	path.clear();
//step 0: handling specail cases
	if(start == NULL || dest == NULL) return false;
	if(start == dest){//start is dest
		path.push_back(start);
		return true;
	}
	if(start->parent == NULL){//start is root
		getPathToRoot(path, dest);
		if(path.back() != start){//start and dest in different trees!
			path.clear();
			return false;
		}
		reversePath(path);
		return true;
	}
	if(dest->parent == NULL){//dest is root
		getPathToRoot(path, start);
		if(path.back() != dest){//start and dest in different trees!
			path.clear();
			return false;
		}
		return true;
	}
//step 1: find out two nodes' paths to root
	vector<TreeNode*> startToRoot, destToRoot;
	getPathToRoot(startToRoot, start);
	getPathToRoot(destToRoot, dest);
//step 2: find out the first common ancestor by finding the first common node of two lists
	size_t i, j, lenOfStart = startToRoot.size(), lenOfDest = destToRoot.size();
	if(lenOfStart < lenOfDest){
		i = 0;
		j = lenOfDest - lenOfStart;
	}
	else{
		i = lenOfStart - lenOfDest;
		j = 0;
	}
	for(; j < lenOfDest; ++i, ++j){
		if(startToRoot[i] == destToRoot[j]) break;//find common ancestor!
	}
	if(j == lenOfDest) return false;//start and dest in different trees!
//step 3: get fully path from start to dest
	path.assign(startToRoot.begin(), startToRoot.begin() + i);
	path.insert(path.end(), destToRoot.rbegin() + lenOfDest - 1 - j, destToRoot.rend());
	return true;
}
void getPathToRoot(vector<TreeNode*>& path, TreeNode* p)
{
	for(; p != NULL; p = p->parent) path.push_back(p);
}
void reversePath(vector<TreeNode*>& path)
{
	if(path.size() < 2) return;
	for(size_t i = 0, j = path.size() - 1; i < j; ++i, --j){
		TreeNode* tmp = path[i];
		path[i] = path[j];
		path[j] = tmp;
	}
}

I think we can do something like this.

int main()
{
bool skip_this=false;
if(p->parent && p->parnet->right ==p)
	skip_this==true;
if(p->parent==null) 
	{ //exit for root 
	return 0;
	}
	int rv= find_path(p->parent, 1, new string("p->val"), skip_this);
return rv;
}
bool find_path(tree *p, int level, string path, bool skip_this)
{
bool rv=false;
	if(level==0)
	{
	PRINT(path);
	rv=true;
	}
	else
	{
	if(p->right != null && skip_this!=true)
		{
		rv= find_path(p->right, level -1, path + p->val, false);
		}
	if(rv!=true)
		{
		if( p->parent != null)
			{
			rv= find_path(p->parent, level+1, string+p->val, false);
			}	
		}
	}
return rv;
}

what team was this for??

My solution

public class Node
    {
        public Node left, right, parent;
        public string Value;

        public Node(string value)
        {
            Value = value;
        }
    }

        static List<Node> PathToRightSibling(Node n)
        {
            Node current = n;
            int level = 0;
            List<Node> upwardPath = new List<Node>();
            upwardPath.Add(n);

            // Traverse up the tree
            while (current.parent != null)
            {
                if (current.parent.left == current)
                {
                    current = current.parent;
                    level++;
                    upwardPath.Add(current);

                    if (current.right != null)
                    {
                        List<Node> path = FindPath(current.right, level - 1);

                        if (path != null)
                        {
                            upwardPath.AddRange(path);
                            return upwardPath;
                        }
                    }
                }
                else
                {
                    current = current.parent;
                    level++;
                    upwardPath.Add(current);
                }
            }

            return null;
        }

static List<Node> FindPath(Node root, int level)
        {
            List<Node> path = new List<Node>();
            path.Add(root);
            if (level == 0)
            {
                return path;
            }
            
            if (root.left != null)
            {
                List<Node> leftPath = FindPath(root.left, level - 1);
                if (leftPath != null)
                {
                    path.AddRange(leftPath);
                    return path;
                }
            }
            
            if (root.right != null)
            {
                List<Node> rightPath = FindPath(root.right, level - 1);
                if (rightPath != null)
                {
                    path.AddRange(rightPath);
                    return path;
                }
            }

            return null;
        }