An efficient tree-traversal strategy is proposed in this letter to reduce the computational complexity of soft-output multiple-input multiple-output (MIMO) symbol detection. To minimize unnecessary computations, the proposed algorithm visits a node at most once. Meanwhile, it repetitively reorganizes the set of nodes which are likely to be the maximum-likelihood solution or counter-hypotheses that need to be identified in the detection. As the reorganization directs the algorithm to search only meaningful nodes for the required symbols, the complexity can be effectively mitigated while preserving the max-log optimality. Experimental results claim that the proposed algorithm reduces the number of visited nodes by 36% over the single tree search for a MIMO system equipped with 4 x 4 64-QAM.