Microsoft Interview Question
Software Engineer in TestsDo InorderTraversal.
During traversal once you get a leaf node, add in the Linked list( it's single linked list, that's what I ahve udnerstood from the question, doesn't have a previous pointer).
Time complexity = O(N).
For n element tree, there can be at maximum ceil(n/2) leaf nodes. From the problem, I see that the nodes are appended at the tail end of the list. So, during the traversal, if we want to add a node to the linked list, we have to traverse all the way to the end of the linked list and then insert it. This will be O(n^2) ( n for inorder traversal and n for linkedlist traversal )
If allowed, one way would be to keep track of tail node of the linked list after each insertion. Then it will be O(n). Any other method to do this problem?
Do a dfs traversal using stack and whenever a child does not have children, append to list.
1. push root node on stack. pop stack and push right child node on stack and then left child node on stack.
2. pop stack. It will give a child. If new node does not have child, then append to linked list else push right child and then left child on stack.
typedef struct tree{
int data;
struct tree *left;
struct tree *right;
}*node;
typedef strict linklist{
int data;
struct linklist *next;
}*list;
list * InorderTraversal( node *root )
{
static list *head=NULL; // static head pointer
if( root == NULL )
{
return;
}
else if( root->left == NULL && root->right == NULL )
{
if( head == NULL )
{
head = (list *) malloc(sizeof(list));
head->next = NULL;
head->data = root->data;
}
else
{
list *p = NULL;
p = head;
while( p->next != NULL )
{
p = p ->next;
}
p->next = (list *) malloc(sizeof(list));
p = p->next;
p->next = NULL;
p->data = root->data;
}
}
else
{
InorderTraversal( root->left );
InorderTraversal( root->right );
}
return head;
}
public class node {
public node next;
public tnode data;
}
public class tnode {
public tnode left;
public tnode right;
public int data;
}
public class printLeaf {
public static void printLeaf(tnode treenode,node head){
if(treenode.left !=null){
printLeaf(treenode.left,head);
}
if(isLeaf(treenode)){
appendtoTail(head,treenode);
}
if(treenode.right !=null){
printLeaf(treenode.right,head);
}
}
private static boolean isLeaf(tnode treenode) {
if(treenode.left==null && treenode.right==null)return true;
return false;
}
private static void appendtoTail(node head, tnode treenode) {
if(head.data==null){
head.data=treenode;
return;
}
node cur=head;
while(cur.next!=null){
cur=cur.next;
}
node newnode=new node();
newnode.data=treenode;
cur.next=newnode;
}
}
Modified Inorder traversal.
However, it changes the structure of the tree.
void LL(struct node* root,struct node** start)
{
static struct node* tail;
if(root)
{
LL(root->left,start);
if(isLeaf(root))
{
if(!*start)
{
*start=root;
tail=root;
}
else
{ tail->right=root;
tail=tail->right;
}
}
LL(root->right,start);
}
}
start points to the head of the linked list.
Complete code: ideone.com/6WhB3
struct tree
{
int data;
struct tree *left;
struct tree *right;
}*root;
struct list
{
int data;
struct list *link;
}*node;
void create_List(struct tree *root)
{
if(!root->left && !root->right)
{
struct tree *temp=(list*)malloc(sizeof(struct list));
temp->data=root->data;
temp->link=root->left;
node=temp;
return;
}
create_List(root->right);
create_List(root->left);
}
void main()
{
root=NULL;
node=NULL;
create_List(root);
while(!node)
{
printf("%d->",node->data);
node=node->link;
}
}
I believe, It is a BFS. You do a BFS using a queue. Every time, You take out a element from queue to examine...
- Ravi December 08, 2010If( leafNode )
Add it to Linklist
else
Add its children to Queue.
This way, you get the required ordering in the link list as well.