Microsoft Interview Question Software Engineer in Tests
I think we should give types for different nodes, 0 for root, 1 for leftmost nodes, 2 for ritemost nodes. Then print with recursion using DFS. void print(tree* parent, int type, stack<string>& data); Print type 1 nodes, leaf nodes directly (they are in order with DFS) but add type 2 nodes in a stack. In the end, pop the stack and print.
Check the code. But I couldn't have time to test it.
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);
}
Use Euler Walk to traverse the Tree.If Tree Node structure is node not provided augment the conventional Node structure by adding a bool field visit.
struct TreeNode
{
TreeNode *left;
TreeNode *right;
void * data;
bool visit;
};
Now start the Euler walk
1. All the nodes are visted from 3 sides left,center and right.
2. if visit value is false, print the node value
3. else move to next node.
Repeat step 2 and 3 until all the nodes are traversed.
what more can be done using stacks which are required three in number.
read a node push it in stack say s1 and at the same time push its children into another stack say s2. now read read by popping frm s2 and printing left child of popped node value until s2 gets empty simultaneously push this node to s1 and its children to stack s3.now do the same for s3 using s2 untile one reaches the end of the tree. this way as we move down the tree we keep on printing the left of every node. and after we have traversed the full tree we have all the node ordered in s1. just pop from s1 and print their rhith children and at last print the root which is lowest in the stack s1...
hope this logic makes sense to u guys..
if ne of u finds ne loop hole in dis plz do comment ..
<pre lang="c++" line="1" title="CodeMonkey83653" class="run-this">struct node {
int val;
node *left;
node *right;
};
void print_leaves (node *n) {
if (!n->left && !n->right)
cout << n->val << " ";
else {
if (n->left)
print_leaves (n->left);
if (n->right)
print_leaves (n->right);
}
}
void print_left_edge (node *n) {
cout << n->val << " ";
if (n->left)
print_left_edge (n->left);
if (n->right)
print_leaves (n->right);
}
void print_right_edge (node *n) {
if (n->left)
print_leaves (n->left);
if (n->right)
print_right_edge (n->right);
cout << n->val << " ";
}
void print_border (node *root) {
if (root->left)
print_left_edge(root->left);
if (root->right)
print_right_edge(root->right);
cout << root->val << endl;
}
</pre><pre title="CodeMonkey83653" input="yes">
</pre>
void print_cyclic(node *root)
{
int type = 0;
if(!root)
return;
stack<node*> stk;
stack<node*> rght;
rght.push(root);
node* st = root;
node* right_most = root;
while(1)
{
if(st->right)
stk.push(st->right);
if(st->left)
stk.push(st->left);
if(stk.empty())
break;
st = stk.top();
stk.pop();
bool new_right = false;
if(st->left || st->right)
{
if(right_most->right)
{
if(right_most->right == st)
new_right = true;
}
else if(right_most->left == st)
{
new_right = true;
}
if(new_right)
{
rght.push(st);
right_most = st;
}
}
if(type == 0)
{
printf("%d ", st->val);
if(!st->left && !st->right)
type = 1;
}
else if(type == 1)
{
if(!st->left && !st->right)
printf("%d ", st->val);
}
}
while(!rght.empty())
{
printf("%d ", rght.top()->val);
rght.pop();
}
}
Solution in python:
def travel(root):
if not root.left and not root.right: # Prints leaves
if not root.visit:
root.visit = True
print root.val
return
if root.left: # Lefts are traversed first and printed
if not root.left.visit:
root.left.visit = True
print root.left.val
travel(root.left)
travel(root.right)
if root.right: # This is visited after it hits a leaf and prints it
if not root.right.visit:
root.right.visit = True
print root.right.val
if not root.visit: # Prints the root finally
root.visit = True
print root.val
void print_boundary(node *T,int right,node *root)
{
static int flag=0;
if(T==NULL)
return;
if(flag==1){
printf("%d ",T->n);
}
else if(flag==0){
if(T->left==0 && T->right==0)
printf("%d ",T->n);
}
if(T->left!=NULL && T->right!=NULL && T==root)
flag=1;
else if(T->left==NULL && T->right==NULL)
flag=0;
print_boundary(T->left,0,root);
print_boundary(T->right,(right&&1),root);
if(flag==1){
printf("%d ",T->n);
}
if(right==1 && T->left==NULL && T->right==NULL){
flag=1;
}
}
the idea is:
initially flag is zero
if T!=root and flag=0 keep printing node till left most node is reached
when we reach left most node set flag=1
if flag= 1 print only leaf nodes
when we reach rightmost node again set flag=0
variable right is to keep track if the node is rightmost node
private static void printBorderOfTree() {
Node root = null;
if(root==null)
{
root = new Node(4);
}
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(1);
Node n5 = new Node(5);
Node n6 = new Node(6);
Node n7 = new Node(7);
Node n8 = new Node(8);
Node n9 = new Node(9);
Node n10 = new Node(10);
Node n34 = new Node(34);
root.left = n2;
root.right = n7;
n2.left = n4;
//n3.right =n4;
n2.right = n3;
n5.right = n6;
n7.left = n5;
n7.right=n8;
n8.right = n10;
n8.left = n9;
n3.right = n34;
//n5.left = new Node(35);
//n4.left = new Node(32);
//n4.right = new Node(33);
System.out.println("Border of the tree:");
System.out.print(" "+root.data);
preOrder1(root.left,1);
postOrder1(root.right,1);
}
private static void preOrder1(Node n, int flag)
{
if(n==null)
return;
if(flag==1)
{
System.out.print(" "+n.data);
if(n.left!=null)
preOrder1(n.left,1);
if(n.right!=null)
preOrder1(n.right,0);
} else if(flag==0){
if(n.left == null && n.right == null)
{
System.out.print(" "+n.data);
return;
}
if(n.left!=null)
preOrder1(n.left,0);
if(n.right!=null)
preOrder1(n.right,0);
}
}
private static void postOrder1(Node n, int flag)
{
if(n==null)
return;
if(flag==1)
{
if(n.left!=null)
postOrder1(n.left,0);
if(n.right!=null)
postOrder1(n.right,1);
System.out.print(" "+n.data);
} else if(flag==0){
if(n.left == null && n.right == null)
{
System.out.print(" "+n.data);
return;
}
if(n.left!=null)
postOrder1(n.left,0);
if(n.right!=null)
postOrder1(n.right,0);
}
}
#define ROOT 0
#define LEFT -1
#define RIGHT 1
void traverse(struct node *n, int child, int parent){
if(n!=NULL){
if(n->right == NULL && n->left == NULL){
printf(" %d ",n->val);
}
else if((parent==ROOT|| parent == LEFT) && child == LEFT){
printf(" %d ",n->val) ;
traverse(n->left,LEFT,LEFT);
if(parent == ROOT){
traverse(n->right,RIGHT,ROOT);
}
else traverse(n->right,RIGHT,LEFT);
}
else if((parent == RIGHT)){
traverse(n->left,RIGHT,RIGHT);
traverse(n->right,LEFT,RIGHT);
}
else if(parent == ROOT &&child == RIGHT){
traverse(n->left,LEFT,RIGHT);
traverse(n->right,RIGHT,ROOT);
printf(" %d ",n->val);
}
}
}
make a call to this function like
traverse(root,LEFT,ROOT);
in this case, there is no internal nodes. what if there has internal nodes, do we need ignore those?
- Anonymous September 20, 2010