An Euler tour traversal of a binary tree visits each internal node three times. Now you need four visits.