C++ interview questions on binary trees with in order traversal, linked list, recursive traverse

Binary tree:

Convert a binary search tree to a circular sorted linked list. The highest valued node should point to the lowest valued node at each step.

I think it should be implemted by using Breadth-first traversal.

We can Insert elements in link list by traversing tree in INORDER. At last we can point last elemtents node to the head.

You are right.

Inorder traversal would give a sorted list which can be pused inside a circular link list.

Guys,

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

2) While doing inorder 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.

Basically, we need to maintain always two pointers, one to head and another to the last element of the linked list

its the great tree list recursion problem… find it on

http://www.google.com/search?hl=en&q=stanford+cs+lib&btnG=Search

Question doesn’t restrict space usage and thus this is not that ‘great’ problem. Moreover, this is a question asked for Program Manager.

void main_class::iterate(Node *new_node)

{

char flag;

Node *temp_parent = NULL;

if (root == NULL)

{

//This is the root node

root = new_node;

cout<<"Root value: "<

{

temp_parent = current;

current = current->child_right;

flag = ‘r’;

}

else

{

temp_parent = current;

current = current->child_left;

flag = ‘l’;

}

}

new_node->parent = temp_parent;

if(flag == ‘l’)

{

temp_parent->child_left = new_node;

}

else

{

temp_parent->child_right = new_node;

}

cout<<"Value: "<

{

current = current->child_left;

//cout<<"Going left to: "<

recursive_traverse(current);

current = current->parent;

}

cout<

//previous_node->child_left = NULL;

}

else

{

//previous_node->child_right = current; // Logical error here. The tree structure is being changed

//before the tree can be traversed!

current->child_left = previous_node;

previous_node = current;

}

/* Section for making of the Linked List ends here */

if(current->child_right !=NULL)

{

current = current->child_right;

//cout<<"Going right to: "<

recursive_traverse(current);

}

return;

}

Oops… u guys will need one more function…lol… on May 09, 2009 |Edit | Edit

{

new Node(7); new Node(4); new Node(3); new Node(5);

new Node(15); new Node(12); new Node(10);

recursive_traverse(root);

Node *an_iterator = previous_node;

/*The following part connects the root node

to the last node making the queue circular

*/

root->child_left = previous_node;

previous_node->child_right = root;

/* The following prints the Linked list

to check if it is indeed the list that

was intended. It also makes it a double

linked list form a single linked list while doing so.

It was not possible to make a double linked list

to begin with because it was creating a logical

error as indicated a few lines of code below.

Hence, iterating from right to left.

*/

cout<<"\n\nThe Linked list: ";
while (an_iterator != root)
{
cout<

an_iterator = an_iterator->child_left;

}

/*

This extra print statement has to be put

outside to print the root node’s valuel

*/

cout<

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<

struct ListNode

{

T value;

ListNode* next;

explicit ListNode(T v) : value(v), next(NULL) { }

};

template

struct TreeNode

{

T value;

TreeNode* left;

TreeNode* right;

};

template

ListNode

{

ListNode

if (tree)

{

list = to_list(tree->right, tail);

ListNode

if (!list)

{

list = node;

}

if (tail)

{

tail->next = node;

}

tail = node;

node->next = to_list(tree->left, tail);

}

return list;

}

cristi.vlasceanu on July 17, 2009 |Edit | Edit

oh, and to make the list circular we need to call the function like this:

ListNode

ListNode

if (tail)

tail->next = list; // make it circular

what nagendra.kumar suggested is right.

this way list would be sorted in increasing order and each element would be pointing

to the smallest as per the question.And there is no need to traverse right subtree first.

i m using double linked list….

node *p=NULL;

node* Cirq(node *t)//we have call with root node….

{

if(t->left !=NULL)

{

p=tree(t->left);

p->right=t;

t->left=p;

}

else if(t->right !=NULL)

{

p=tree(t->right);

t->right=p;

return p;

}

else

{

return t;

}

}

Inorder traversal would print the numbers in icreasing order for Binary search tree.

inorder(Node *root)

{

if(root)

{

inorder(root->left);

//printf(“%d”, root->value); Instead of print to just assign the next poiter to end //of the list. I guess that shoudn;t be hard to figure how to assign the next link 😉

inorder(root->right);

}

}

one more statement after the end of the traversal to point the last node to the head of the list

Reply to Comment

nirmalr on November 09, 2009 |Edit | Edit

// Routine to convert tree into doubly list

// after conversion “right” points to “next” node and “left” points to “prev” node

node_t * toList(node_t *curr, node_t *next) {

if (curr == 0) return next;

curr->right = toList(curr->right, next);

if (curr->right)

curr->right->left = curr;

return toList(curr->left, curr);

}

invoke like this,

head = toList(root, 0);

this routine returns head of the list. head and tail is not linked that can be done easily.

abhimanipal on May 09, 2010 |Edit | Edit

Very nice and effective solution

typedef node * NodePtr;

node *CreateListFromTree(node *root)

{

NodePtr start = NULL, tail = NULL;

CreateListFromTreeCore(root,&start,&tail);

return start;

}

/* Assume right for tree will act as next for Linked List */

void CreateListFromTreeCore(node *root, NodePtr *start, NodePtr *tail)

{

CreateListFromTreeCore(root->left,start,tail);

node *temp = root->right;

root->left = NULL;

if (*start == NULL)

*start = *tail = root;

else

{

(*tail)->right = root;

*tail = root;

}

*tail->right = *start;

CreateListFromTreeCore(temp,start,tail);

}

Question is convert BST to LL but not create another list and copy values.

here is working solution.

btnode* formListFromBT(btnode* root, btnode* cur, btnode** head) {

if(!root) return cur;

cur = formListFromBT(root->left, cur, head);

if(*head == NULL) {

*head = cur = root;

}

cur->left = root; cur = cur->left;

cur = formListFromBT(root->right, cur, head);

}

// call the above function using…

btnode *listhead = NULL;

tail = formListFromBT(head, NULL, &listhead);

tail->left = listhead;

Reply to Comment

Anonymous on January 14, 2010 |Edit | Edit

//call will be

// Element *start = null;

// Element *tail = BuildCircularLL(root, &start);

// tail->left = start;

Element *BuildCircularLL(Element *head, Element **start)

{

Element *begin = *start;

Element *node = head;

Element *prev = null;

Element *after = null;

if(node == null)

{

return null;

}

prev = BuildCircularLL(&node->left, &begin);

if(prev != null)

{

if(begin == null)

{

begin = prev;

}

prev->left = node;

}

after = BuildCircularLL(&node->right, &begin);

if(after != null)

{

node->left = after;

node->right = null;

return after;

}

else

{

return node;

}

}

binary search to speed up

balancing binary trees, find the depth of a tree.

They asked about balancing binary trees and

Print nodes in a binary tree in level order

Tree traversal

**HOW DO YOU START A PROFITABLE TRADING BUSINESS? Read more NOW >>>**

**NOTE**I now post my

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

*TRADING ALERTS*