Tag Archives: in order traversal

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

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: "<value<<"\n\n"; } else { //This is not a root node and hence, now we iterate Node *current = root; while(current != NULL) { if(current->value < new_node->value) // Go right
{
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: "<value<<" Parent value: "<<(new_node->parent)->value<<"\n\n"; } } /* This is a recursive function to traverse the binary tree INORDER */ void main_class::recursive_traverse(Node *current) { if(current->child_left != NULL)
{
current = current->child_left;
//cout<<"Going left to: "<value;
recursive_traverse(current);
current = current->parent;
}

cout<value<<" "; /* This section is for making of the Circular Linked list*/ if(previous_node == NULL) { /* This is the head*/ previous_node = current; root = current; //root->child_left = NULL;
//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: "<value;
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<value<<" "; an_iterator->child_left->child_right = an_iterator;
an_iterator = an_iterator->child_left;
}

/*
This extra print statement has to be put
outside to print the root node’s valuel
*/
cout<value<<" "; cout<<"\n\n"; } Isnt the problem statement to convert the existing bst to a ll and not creating a new one!!! This is the well working code for this problem..:) #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<data<<"\t"; display(root->large);

}
}
/* function to display ll */
void displayl(node *head)
{
for(int i=1;i<=5;i++) { cout<data<<"\t"; head=head->large;
}
}
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* to_list(TreeNode* tree, ListNode*& tail)
{
ListNode* list = NULL;
if (tree)
{
list = to_list(tree->right, tail);
ListNode* node = new ListNode(tree->value);
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* tail = NULL;
ListNode* list = to_list(tree, tail);
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 TRADING ALERTS into my personal FACEBOOK ACCOUNT and TWITTER. Don't worry as I don't post stupid cat videos or what I eat!