Engineering Full Stack Apps with Java and JavaScript
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.
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 will be O(n)
Extra spac will be taken for the Stack.