Engineering Full Stack Apps with Java and JavaScript
We can use a stack data structure to do this:
Initialize current node as root
Create a stack.
Do following until current is NULL and stack is empty:
Push the current node to stack and set current = current.left until current is NULL
If current is NULL and stack is not empty then
Pop the top item from stack into current.
Print current,
Set current = current.right
void inorder(TreeNode n)
{
TreeNode current = n;
Stack s = new Stack();
while((current ! = null) || !s.isEmpty())
{
if(current!=null)
{
s.push(current);
current = current.left;
}
else{
current = s.pop();
print(current);
current = current.right;
}
}
}
Time complexity is O(n)
Extra space for stack also will be taken.