Coding Interview Club

Prepare for coding interviews in simple and structured steps

Preorder Traversal Without Using Recursion

Category: 
Problem: 

Preorder Traversal Without Using Recursion

Approach: 
  • In inorder, we print data and then go to left and right subtree.
  • We can use a stack here.
  • Every time we print a node, we will add its right and left children to the stack in order.
  • Since stack is a LIFO data structure, the left will be poped and printed first.
Solution: 

void preorder(TreeNode n)

{

  TreeNode current = n;

  Stack s = new Stack();

  s.push(current);

  while(!s.isEmpty())

  {

    current = s.pop();

    print(current);

    s.push(current.right);

    s.push(current.left);

  }

}

 

Complexity

Complexity will be O(n)

Extra spac will be taken for the Stack.

Back to Top