In Order traversal of a modified Binary Tree

Question

This was asked to me in an interview which I screwed up. We are given a binary tree , however , it is modified such that it's children are never null , if a non leaf node doesn't have a child then its right/left child points to the node itself. And for the leaf nodes , they point to the next left node and right node. For leftmost and rightmost node it will be pointing to itself and the previous/next element.

Example :

        1
     /     \
    2       3
  /  \     / \
(4 =  5 = 6 = 7)

Here 4.left = 4 , 4.right = 5 , 5.left = 4 and 5.right = 6 and so on.

We need to do an inorder traversal of this tree.

I came up with the conditions which will determine if a node is leaf node (exit condition):

 if(root.right==root || root.left == root || root.left.right == root || root.right.left == root)

But couldn't combine these properly. Also we need to take care of skewed trees for which even the root satifies the condition root.left = root || root.right = right , so we will straight away get out of recursion without even traversing the whole tree.

Please help me with it. I couldn't come up with proper condition check for recursion.

We just need to do an in order traversal of this tree. Output : 4 2 5 1 6 3 7

Answer 1

The following algorithm should do:

visit(vertex v) {
    if (v.left != v && v.left.right != v) visit(v.left)
    print v
    if (v.right != v && v.right.left != v) visit(v.right)
}

I think your problem was that you tried to do too many things at a time. Instead of detecting whether the vertex is a leaf or not, it would have sufficed to detect first whether it has a left child and then whether it has a right child.

Answer 2

If you hit a non-leaf that points to itself on the right side, but has a child on the left side, a condition like 'root.right==root' would falsely call that node a leaf. You need to use an and statement. I think this might work:

if((root.right==root && root.left.right == root) || (root.left == root && root.right.left == root) || (root.left.right == root && root.left == root))

But this will not work if you have a tree with a missing leaf in the middle. Of course if the nodes were numbered, then it would be much easier since you could just use log2 to check what level it was on compared to where it linked to.

Answer 3

For clarity, I put all the bizarre logic into a function (which could be inlined)

#include <stdio.h>

struct list {
        struct list *prev;
        struct list *next;
        int val;
        };

struct list arr[] =
{ {arr+1, arr+2, 1}
, {arr+3, arr+4, 2}
, {arr+5, arr+6, 3}
, {arr+3, arr+4, 4}
, {arr+3, arr+5, 5}
, {arr+4, arr+6, 6}
, {arr+5, arr+6, 7}
        };

int is_leaf(struct list *p)
{
if (p->prev == p) return 1;     // 4
if (p->next == p) return 1;     // 7
if (p->next->prev == p) return 1; // 5,6
return 0;                       // non-leaves : 1,2,3
}

unsigned recurse (struct list *p)
{
int chk;
unsigned ret=1;
chk = is_leaf(p) ;

if (!chk) ret+=recurse(p->prev);
printf("%d %s\n", p->val, chk ? "leaf" : "nonLeaf" );
if (!chk) ret+=recurse(p->next);
return ret;
}
int main (void) {

    unsigned cnt;
    cnt = recurse (arr);
    printf( "Result=%u\n", cnt );

   return 0;
}

Output:

4 leaf
2 nonLeaf
5 leaf
1 nonLeaf
6 leaf
3 nonLeaf
7 leaf
Result=7