Interview Questions

Given a binary tree print the nodes in this order ......

Software QA/Tests Interview Questions from Microsoft

(Continued from previous question...)

Given a binary tree print the nodes in this order ......

Question:
Given a binary tree print the nodes in this order:
all the left most nodes from top to bottom, then all the leaves, then all the right most nodes from bottom to top, then the root. like
10
5 15
3 2 12 17
you would print 5 3 2 12 17 15 10



maybe an answer:


class BSTNode
{
int data;
BSTNode *left;
BSTNode *right;

BSTNode(int d)
{
data = d;
left = 0;
right = 0;
}
};

void PrintLeftMostTopBottomButNotLeaf(BSTNode *node)
{
if(node == null)
{
return;
}
else
{
while(node != null &&&& (node->left != null || node->right != null))
{
cout << node->data << " ";

if (node->left != null)
node = node->left;
else
node = node->right;
}
}

}

void PrintLeafs(BSTNode *node)
{
if (node->left == null && node->right == null)
cout << node->data << " ";
else
{
if (node->left != null)
PrintLeafs(node->left);
if (node->right != null)
PrintLeafs(node->right);
}
}

void PrintRightMostBottomTopButNotleafs(BSTNode * node)
{
if(node != null)
{
if (node->right != null)
PrintRightMostBottomTopButNotleafs(node->right);
else if (node->left != null)
PrintRightMostBottomTopButNotleafs(node->left);
else
// do nothing
}

// If not a leaf node
if (node->left != null || node->right != null)
cout << node->data << " ";
}

void Question(BSTNode *node)
{
if (node != null)
{
// Left Most Print
if(node->left != null)
PrintLeftMostTopBottomButNotLeaf(node->left);
else if(node->right != null)
PrintLeftMostTopBottomButNotLeaf(node->right);
else
return;

// Leaf Print
PrintLeafs(node);

// Right Most Print
PrintRightMostBottomTopButNotleafs(node);

// self Print
cout << node->data << endl;

}
}

void main()
{
BSTNode *node = new BSTNode(17);

// You can fill the BST then call Question

Question(node);
}

(Continued on next question...)

Other Interview Questions