## Ebay Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
0
of 0 vote

Ingredients: Depth First traversal, a sentinel node.

``````void leaf_linking_traversal(Node* node, Node** prev_node)
{
assert(*prev_node);
if (node)
{
if (node->left == 0 && node->right == 0)
{
(*prev_node)->right = node;
node->left = *prev_node;
*prev_node = node;
}
else
{
}
}
}

{
if (tree_root)
{
Node* list_back = &sentinel;
if (list_back!=&sentinel)
{
list_back->right = &sentinel;
sentinel.left    = list_back;
}
else
{
sentinel.right = &sentinel;
sentinel.left  = &sentinel;
}
}
}``````

Comment hidden because of low score. Click to expand.
0

You have given the ingredients, but recipe is not in english. Care to explain?

Comment hidden because of low score. Click to expand.
0

well, an element of a double linked list has two pointers: forward and backward. Think of a tree node's right pointer as forward and its left pointer as backward.

the algorithm consists in traversing the tree and appending leaves to the list as we encounter them from left to right.

you have a routine called leaf_linking traversal(...) which is in charge of this. It needs a pointer to a node to explore from, and a pointer to the back of the double-linked list to be construct.

in the first call to this routine, you pass the root as the current node and a pointer to the list's sentinel.

the depth first search performed by the routine knows it has found a leaf when the left and right pointers are both 0 (unassigned).

in that case, it performs the double-linking, and the current node (leaf) becomes the last element of the list. This change is reflected through re-assignment of the pointer *prev_node. It means that the next leaf in the tree is going to see the current leaf as the one it should double-link to.

when the traversal is over, you still have to double-connect the last element in the list to the sentinel, or double-connect the sentinel tp itself in case the tree was empty (routine link_leaves(...) does this).

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think you can just do it by traversing the tree once. When you reach a leaf simply pass it to the routine which makes the list ( something like addToList(node)). This routine will return a head which will be the first node it receives.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Does anyone know what "re-using the left and right pointers" mean?

Comment hidden because of low score. Click to expand.
0

May be it means that if you have a sub tree like [Left] <== [Root] ==> [Right], then your algorithm should reuse these links for constructing the corresponding Doubly Linked List: [Left] <==> [Root] <==> [Right]

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public void convert() {
TreeNode prev = null;
}

private void convertT(TreeNode node, TreeNode head, TreeNode prev) {
if (node == null) {
return;
}

node.left = prev;
if (prev != null) {
prev.right = node;
} else {
}
TreeNode right = node.right;

prev = node;
}``````

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.

### 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.