Solution: Most problems involving binary trees can be solved by using recursion. Recursion is inherent to trees. But, keep in mind that recursion has a memory overhead because of the additional stack space required for the recursive method calls. Sometime interviewers will ask to solve problems related to trees without using recursion. This can sometimes make the problem challenging. In this problem, even though we will not use recursion explicitly, we will use the Stack data structure that emulates what recursion does.

Code:

typedef struct _node { int data; struct _node * left; struct _node * right; } Node; void Pre-Order-Traversal-Non-Recursive(Node * root) { Stack nodeStack; nodeStack.Push(root); // while stack is not empty while(nodeStack.Count > 0) { Node * currentNode = nodeStack.Pop(); printf("%d\n", currentNode->data); nodeStack.Push(currentNode->right); nodeStack.Push(currentNode->left); } }

Note: This implementation, even though avoids recursion, does not take any less memory compared to the recursive method since we are using an external stack to emulate recursion.

For the pre-order, you will have to process the nodes as follows: Root(Node)->Left->Right, while you have it as Root(Node)->Right->Left.

ReplyDeletehe is using stack, so the right node should be pushed before left node

Deleteisnt't null check required ?? when pusing elements in stack

ReplyDeleteya its required

ReplyDelete@all...Please understand the logic...he is using stack so root->right->left means

ReplyDeletehe will print root first then left will be printed as left is at the top of the stack.

it is showing some errors

ReplyDeleteNode * currentNode = nodeStack.Pop();

ReplyDeleteif(currentNode != null) {

printf("%d\n", currentNode->data);

nodeStack.Push(currentNode->right);

nodeStack.Push(currentNode->left);

}

would check the null otherwise it throws error.

Check the null in main with throwing an Exception :)

ReplyDelete