Google Interview Question Software Engineer / Developers
S is right. inorder or preorder doesn't differ (just the outputting order changes). the point is the same null pointers in the leaf nodes are manipulated as a stack to remember right childs that should be visited.
I hadn't heard about the Morris traversal before. Just googled about it. Interesting to know. However, I still am not sure how the solution for preorder would work. Any code pointers?
public ArrayList<Integer> preorder(TreeNode root){
ArrayList<Integer> res=new ArrayList<Integer>();
TreeNode stack=null;
TreeNode cur=root;
while(true){
TreeNode p=cur;
if(p!=null){
while(p.right!=null){
p=p.right;
}
p.right=stack;
stack=cur;
}
if(stack==null){
break;
}else{
res.add(stack.val);
cur=stack.left;
stack=stack.right;
}
}
return res;
}
keep a parent pointer in each node, then I guess preorder traversal is nothing but a special case of euler walk in a binary tree
while(cur_node!=root)
set subtree_visited=false
if(!subtree_visited&&cur_node.child)
{
while(cur_node.child)
cur_node=cur_node.child
}
else
{
print cur_node.val
if(cur_node.next_sibling)
{
subtree_visited=false
cur_node=cur_node.next_sibling;
}
else
{
subtree_visited=true
cur_node=cur_node.parent
}
}
above solution uses sibling pointer and parent pointer
As I said, the interviewer did not allow me to use a visited field in the node. In the end, I added a parent pointer to the node structure.
In the loop, I maintained a current and old pointer. Based on the old pointer, you know if you are coming from parent/left child/right child and handle the cases accordingly. If you reach a leaf or you reach a node from the right child, backtrack by old=curr; curr=curr->parent
Once we reach a leaf node, we can go to its parent and make its parent NULL. This way any node will know whether to branch left or right or to go to its parent.
void pre()
{
node *ptr,*current;
ptr = root;
while(ptr)
{
if(ptr->left && ptr->left->parent)
{
ptr=ptr->left;
}
else if(ptr->right && ptr->right->parent)
{
ptr=ptr->right;
}
else
{
current=ptr;
ptr=ptr->parent;
current->parent=NULL;
}
}
}
yes. threaded binary tree should work. however, i suspect there is still other smarter way
geeksforgeeks.org/?p=6358
This has nice code for Morris in-order traversal. It can be trivially modified to do pre-order traversal.
Solution for stackless inorder,preorder,postorder in slide 14,15,16 : http : / / gabrielistrate.weebly.com/uploads/2/5/2/6/2526487/curs8.pdf
<pre lang="c++" line="1" title="CodeMonkey31120" class="run-this">void stacklessPreorder(Node* root)
{
Node* p, *pre;
if(root == NULL) return;
p = root;
while(p != NULL)
{
if(p->left == NULL)
{ printf(" %d",p->value); p=p->right; continue;}
for(pre=p->left;pre->right != NULL && pre->right != p;pre= pre->right)
{ }
if(pre->right == NULL)
{ pre->right = p; printf(" %d",p->value);p = p->left; continue;}
else
{ pre->right = NULL; p = p->right;continue;}
}
}</pre><pre title="CodeMonkey31120" input="yes">
</pre>
static void preorder(Node root)
{
Node curr=root;
Node prv=null;
int f=1;
while(curr!=null)
{
f=0;
if(prv==null || prv.par!=curr)
{
f=1;
prv=curr;
System.out.println(curr.value);
if(curr.left!=null)
curr=curr.left;
else if (curr.right!=null)
curr=curr.right;
else curr=curr.par;
}
else if(prv==curr.right)
{
prv=curr;
curr=curr.par;
f=1;
}
else
{
f=1;
prv=curr;
if(curr.right!=null)
curr=curr.right;
else
curr=curr.par;
}
}
}
}
check this
preordermorrisiterative(Tnode *root) {
Tnode *current = root, *pred = NULL, *succesor = NULL;
while (current != NULL) {
if (current->left == NULL) {
printf(" %d ", current->data);
current = current->right;
} else {
pred = current->left;
while (pred->right != NULL && pred->right != current) {
pred = pred->right;
}
if (pred->right == NULL) {
pred->right = current;
//preorder
printf(" %d ", current->data);
current = current->left;
} else {
pred->right = NULL;
//inorder
//printf(" %d ", current->data);
current = current->right;
}
}
}
}
can we use extra space of O(1) ??
if yes, then this could be one of the solutions..
for preorder:
void iterativePreorder(mynode *root) { mynode *save[100]; int top = 0; if (root == NULL) { return; } save[top++] = root; while (top != 0) { root = save[--top]; printf("[%d] ", root->value); if (root->right != NULL) save[top++] = root->right; if (root->left != NULL) save[top++] = root->left; } }
similarly write for postorder and inorder
can we use extra space of O(1) ??
if yes, then this could be one of the solutions..
for preorder:
void iterativePreorder(mynode *root) {
mynode *save[100];
int top = 0;
if (root == NULL) { return; }
save[top++] = root;
while (top != 0) {
root = save[--top];
printf("[%d] ", root->value);
if (root->right != NULL)
save[top++] = root->right;
if (root->left != NULL)
save[top++] = root->left; } }
similarly write for postorder and inorder
Here is another solution (P = parent, R = right, L = left):
1.) you traverse the tree and when you see a node P with left Node just put that node on the right side - there you link P.R to the most right node from the L (L.R.R)
2.) continue this untill there are no left nodes. Here is a picture of the trees:
//
4
/ \
2 5
/ \ \
1 3 6
//
4
2
1 3
5
6
//
4
2
1
3
5
6
Here is a Java implementation:
public TreeNode preOrderSpecial(TreeNode root) {
TreeNode currNode = root;
while (currNode != null) {
if (currNode.left != null) {
TreeNode mostRight = getMostRightNode(currNode);
mostRight.right = currNode.right;
currNode.right = mostRight;
currNode.left = null;
}
currNode = currNode.right;
}
return root;
}
protected TreeNode getMostRightNode(TreeNode t) {
TreeNode result = t;
while (result.right != null)
result = result.right;
return result;
}
void preOrderNonRecursive( BSTNode* root )
{
if(!root)
return;
BSTNode* cur = root;
while(cur)
{
bool b = false;
BSTNode* pre = NULL;
if (cur->left)
{
pre = cur->left;
while(pre->right && pre->right != cur)
pre = pre->right;
if(!pre->right)
{
pre->right = cur;
b = true;
}
else
pre->right = NULL;
}
else
printf("%d\n",cur->val);
if(b)
{
printf("%d\n",cur->val);
cur = cur->left;
}
else
cur = cur->right;
}
}
why not use threading?? I believe preorder traversal can be achived using an even an right inorder threaded tree.
- Anonymous August 04, 2010