LeetCode Binary Tree Inorder Traversal: 4 Methods (Previous and Current Pointers)

Overview

4 different implementations here: 1. recursive method 2. Use HashMap 3. Pre Pointer to check Left Subtree 4. Simulate inorder traversal without any explicit flag.

LeetCode Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

LeetCode Binary Tree Inorder Traversal Solution: 4 Methods

(1) Well, the recursive solution is obviously trivial: that is,

void inorder(TreeNode *root) {
    if(!root) return;
    inorder(root->left);
    cout<val<<endl;
    inorder(root->right);
}

(2) if we want to do this in iterative way, then we need a stack, (it is known that every recursive function could be translated into some sort of iterative method by using stack), following this angle of just treating the iterative method as a translation of the recursive one, we have the following Psudo-code (suppose every node has a flag indicating that the left subTree of the node is already printed, one could simulate such flag by using hash set without modifying the original construct):

void inorder_iterative(TreeNode *root) {
    stack s;
    s.push(root);
    while(!s.empty()) {
         TreeNode *node = s.top();
         if(node) {
             if(the left child of node is printed already) {
                 print node->val;
                 s.pop();
                 s.push(node->right);
             }
             if(the left child of node is NOT printed yet) {
                 //this means that the left child of node is not processed yet
                 s.push(node->left);
                 set the flag of node as true indicating the left child is processed;
                 //we can set the flag as true because when next time we encounter this node
                 //it must be that the left child is already printed by the property of stack
             }
         }
         else
             s.pop(); //pop the NULL outt
    }
}

(3) There is an alternative approach of the iterative method, remember (2) is still simulating the recursive way but we can think about it in another direct iterative angle: just think about how inorder traversal works, it is actually like this, we keep traversing to root’s left child (left left child……) while pushing visited nodes onto the stack. When reach a NULL node, we are ready to print the top node in the stack. Then we can continue to process its right child and repeat the process again. This yields the following code:

void inorder_iterative(TreeNode *root) {
    stack s;
    s.push(root);
    while(!s.empty()) {
         TreeNode *node = s.top();
         if(node) {
             stack.push(node->left);//keep traversing the left child until a NULL
         }
         else {
             s.pop(); //pop out the null
             pop and print s.top();
             s.push(node-rith);//process the right child
         }
    }
}

This code is more concise and simpler one.

Updated: Also, I give an accepted piece of code here which might be a bit longer than the above one but easier to understand and to come up with during say an interview. The basic idea is essentially the same, we need to figure out when we should print out a node value. Recall inorder traversal, it is Left->Root->Right order, by explicitly using a stack, we simulate the recursive method, a node value should be printed out once its left subtree finished processing, we use a previous pointer Pre to indicate the previous visited node, and compare Pre with Curr which is the current node to determine whether we are travelling down along the tree or we are travelling up: We got the current Node A, if we are travelling down, we cannot pop out A and should keep it in the stack for later printing out, we need to push the left child into the stack in order to process the left subtree first. If we are travelling up, then we need to print the current node (Since the order is Left->Root and the left subtree is finished) and push its right child into the stack to start to process the right subtree, so in this code, it is easier to understand by using a Pre pointer explicitly and this is also consistent with the way in my post about how to do postorder tree traversal. Here comes the accepted code:

class Solution {
public:
	void inorderTraversal_iterative(TreeNode *root, vector<int> *pvecResult)
	{
		if (NULL == pvecResult)
			throw runtime_error("NULL pointer to the result!");

		if (NULL == root) return ;

		stack<TreeNode *> stk;
		TreeNode *pre = NULL;
		TreeNode *curr = NULL;
		stk.push(root);
		while (!stk.empty()) {
			curr = stk.top();
			if (NULL == curr->left && NULL == curr->right) {
				pvecResult->push_back(curr->val);
				stk.pop();
			}
			else {
				if (!pre || pre->left == curr || pre->right == curr) {
					if (curr->left) stk.push(curr->left);
				}
				else {
					pvecResult->push_back(curr->val);
					stk.pop();
					if (curr->right) stk.push(curr->right);
				}
			}
			pre = curr;
		}
	}

    vector<int> inorderTraversal(TreeNode *root) {
		vector<int> vecResult;
		inorderTraversal_iterative(root, &vecResult);
		return vecResult;
    }
};

LeetCode Binary Tree Inorder Traversal Tips and Remarks:

The key here is still to understand when to print a node value, for inorder traversal, we print a value of a node A once we finish processing A’s left subtree. And there is a post in the leetcode website “Binary Search Tree In-Order Traversal Iterative Solution” you could check it out for further reference.

Summary

4 different implementations here: 1. recursive method 2. Use HashMap or Pre Pointer to check Left Subtree 4. Simulate inorder traversal without any explicit flag.

 

Written on April 13, 2013