Everything you need to know about binary trees and circular linked lists for C++ job interview questions

In order to properly build a binary tree, you need to do the following steps:

1) Inorder traversal of a Binary search Tree prints the data in the increasing order.

2) While doing in order traversal, at each step, build the linked list adding the each element at the end of linked list.

3) At each step, also make the end of the linked list to point to the first element of the linked list. This will make the linked list circular.

Here is a code sample of a binary sorted tree that can be converted to a linked list (this also ensures the list is circular):

#include

using namespace std;

#include

#include

#include

#include

#include

#include

#include

#define MAX 1000

#define max(a,b) (a)>=(b)?(a):(b)

#define REP(i,n) for(i=0;i

/*** structure of the tree node ****/

struct node

{

int data;

node *small;

node *large;

};

/* fun to insert element in the binary search tree */

void insert(node **root,int val)

{

node *tmp;

if(*root==NULL)

{

tmp=(node*)malloc(sizeof(node));

tmp->data=val;

tmp->small=NULL;

tmp->large=NULL;

*root=tmp;

}

else

{

if(val<(*root)->data)

insert(&((*root)->small),val);

else

insert(&((*root)->large),val);

}

}

/* this function joins two given nodes */

void join(node **a,node **b)

{

(*a)->large=(*b);

(*b)->small=(*a);

}

/* this function appends second list behind first list */

node *append(node *head1,node *head2)

{

if(head1==NULL)

return head2;

if(head2==NULL)

return head1;

node *alast,*blast;

alast=head1->small;

blast=head2->small;

join(&alast,&head2);

join(&blast,&head1);

return head1;

}

/**** most important function ,uses recursion to convert bst to circular ll ***/

node* treetolist(node *root)

{

if(root==NULL)

return NULL;

node *alist,*blist;

alist=treetolist(root->small);

blist=treetolist(root->large);

root->small=root;

root->large=root;

alist=append(alist,root);

alist=append(alist,blist);

return alist;

}

/* funtion to display bst */

void display(node *root)

{

if(root!=NULL)

{

display(root->small);

cout<

}

}

/* function to display ll */

void displayl(node *head)

{

for(int i=1;i<=5;i++)
{
cout<

}

}

int main()

{

node *root=NULL;

node *head;

/* test values */

insert(&root,10);insert(&root,4);insert(&root,8);insert(&root,15);insert(&root,9);

display(root);

cout<**NOTE** I now post my** TRADING ALERTS** into my personal FACEBOOK ACCOUNT and TWITTER. Don't worry as I don't post stupid cat videos or what I eat!