[tree] inorder traversal, concise iterative version

inorder_traversal.cpp

void in_order(TreeNode *root) {
	if(!root) return;
	stack<TreeNode*> s;
	TreeNode *curr = root;
	//s.push(curr);
	while(true) {
		if(curr) {
			s.push(curr);
			curr = curr->left;
		}
		else {
			if(s.empty()) break;
			curr = s.top(); s.pop();
			visit(curr);
			curr = curr->right;
		}
	}
}

// better version
void inorder_traversal(TreeNode *root) {
	if(!root) return;
	stack<TreeNode*> s;
	TreeNode *cur = root;  // gist, use a temp variable cur to traverse. Do not push cur into stack now.
	while(1) {
		while(cur) {
			s.push(cur);  // all elements in stack are non-NULL. 
			cur = cur->left;
		}
		if(s.empty()) break;
		cur = s.top(); 
		s.pop();
		visit(cur);
		cur = cur->right;
	}
}