Pop all items one by one . Do following for every popped item a ) push its right child and set its parent pointer b ) push its left child and set its parent pointer Note that right child is pushed first so that left is processed first
while ( ! nodeStack . empty ( ) ) {