Push right & left children of the popped node to stack . Also set their parent pointer in the map
if ( current -> right ) { parent [ current -> right ] = current ; nodeStack . push ( current -> right ) ; } if ( current -> left ) { parent [ current -> left ] = current ; nodeStack . push ( current -> left ) ; } } }