Binary Tree Inorder Traversal

Question

Given a binary tree, return the inorder traversal of its nodes' values iteratively without using recursion.

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

return [1,3,2].

Answer 1

Note:
Before you attempt this problem, you might want to try coding a pre-order traversal iterative solution first, because it is easier. On the other hand, coding a post-order iterative version is a challenge. See my post: Binary Tree Post-Order Traversal Iterative Solution for more details and an in-depth analysis of the problem.

We know the elements can be printed in-order easily using recursion, as follow:

void in_order_traversal(BinaryTree *p) {
    if (!p) return;
    in_order_traversal(p->left);
    cout << p->data;
    in_order_traversal(p->right);
}

Excessive recursive function calls may cause memory to run out of stack space and extra overhead. Since the depth of a balanced binary search tree is about lg(n), you might not worry about running out of stack space, even when you have a million of elements. But what if the tree is not balanced? Then you are asking for trouble, because in the worst case the height of the tree may go up to n. If that is the case, stack space will eventually run out and your program will crash.

To solve this issue, we need to develop an iterative solution. The idea is easy, we need a stack to store previous nodes, and a visited flag for each node is needed to record if the node has been visited before. When a node is traversed for the second time, its value will be printed. After its value is printed, we push its right child and continue from there.

void in_order_traversal_iterative(BinaryTree *root) {
    stack<BinaryTree*> s;
    s.push(root);
    while (!s.empty()) {
        BinaryTree *top = s.top();
        if (top != NULL) {
            if (!top->visited) {
                s.push(top->left);
            } else {
                cout << top->data << " ";
                s.pop();
                s.push(top->right);
            }
        } else {
            s.pop();
            if (!s.empty())
                s.top()->visited = true;
        }
    }
}

Alternative Solution:
The above solution requires modification to the original BST data structure (ie, adding a visited flag). The other solution which doesn't modify the original structure is with the help of a current pointer in addition of a stack.

First, the current pointer is initialized to the root. Keep traversing to its left child while pushing visited nodes onto the stack. When you reach a NULL node (ie, you've reached a leaf node), you would pop off an element from the stack and set it to current. Now is the time to print current's value. Then, current is set to its right child and repeat the process again. When the stack is empty, this means you're done printing.

void in_order_traversal_iterative(BinaryTree *root) {
    stack<BinaryTree*> s;
    BinaryTree *current = root;
    bool done = false;
    while (!done) {
        if (current) {
            s.push(current);
            current = current->left;
        } else {
            if (s.empty()) {
                done = true;
            } else {
                current = s.top();
                s.pop();
                cout << current->data << " ";
                current = current->right;
            }
        }
    }
}

We can even do better by refactoring the above code. The refactoring relies on one important observation:

The last traversed node must not have a right child.

Why this is true? To prove this, we assume the opposite, that is: the last traversed node has a right child. This is certainly incorrect, as in-order traversal would have to traverse its right child next before the traversal is done. Since this is incorrect, the last traversed node must not have a right child by contradiction.

Below is the refactored code:

void in_order_traversal_iterative(BinaryTree *root) {
    stack<BinaryTree*> s;
    BinaryTree *current = root;
    while (!s.empty() || current) {
        if (current) {
            s.push(current);
            current = current->left;
        } else {
            current = s.top();
            s.pop();
            cout << current->data << " ";
            current = current->right;
        }
    }
}

A threaded tree, with the special threading links shown by dashed arrows. A threaded binary tree makes it possible to traverse the values in the binary tree via a linear traversal that is more rapid than a recursive in-order traversal.

Further Thoughts:
The above solutions require the help of a stack to do in-order traversal. Is it possible to do in-order traversal without a stack?

The answer is yes, it's possible. There's 2 possible ways that I know of:

By adding a parent pointer to the data structure, this allows us to return to a node's parent (Credits to my friend who provided this solution to me). To determine when to print a node's value, we would have to determine when it's returned from. If it's returned from its left child, then you would print its value then traverse to its right child, on the other hand if it's returned from its right child, you would traverse up one level to its parent.
By using a Threaded Binary Tree. Read the article: Threaded Binary Tree on Wikipedia for more information.

Answer 2

class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> result;
        if(root == NULL) return result;

        stack<TreeNode *> stk;
        stk.push(root);
        TreeNode *p = root->left;
        while(!stk.empty()) {
            while(p != NULL) {
                stk.push(p);
                p = p->left;
            }
            p = stk.top();
            stk.pop();
            result.push_back(p->val);

            p = p->right;
            if(p != NULL) {
                stk.push(p);
                p = p->left;
            }
        }
    }
};

Answer 3

/*
 using iterative way for in-order traversal
 the key is to use stack to store all nodes with a left tree

 */

class Solution {
public:
  vector<int> inorderTraversal(TreeNode *root) {
    vector<int> ret;

    stack<TreeNode*> stk;
    TreeNode *cur=root;
    bool curVisited=false;

    while(!stk.empty() || cur) {

      if(cur) // non empty
    if(cur->left && !curVisited) { //has left child and cur is first visit
      stk.push(cur); // store it
      cur = cur->left; // descend left
      curVisited = false;
    } else { // no left child, or cur is popped from stack
      ret.push_back(cur->val); // print cur
      cur = cur->right; // descend right     
      curVisited = false;
    }
      else { // empty, so pop the top out
    cur = stk.top();
    stk.pop();
    curVisited = true;
      }

    }

    return ret;
  }
};

Answer 4

classic iterative solution.

vector<int> inorderTraversal(TreeNode *root) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    vector<int> result;
    vector<TreeNode*> stack;

    if (!root)
        return result;

    while (!stack.empty() || root) {
        if (root) {
            stack.push_back(root);
            root = root->left;
        } else {
            root = stack.back();
            stack.pop_back();
            result.push_back(root->val);
            root = root->right;
        }
    }

    return result;
}

Answer 5

public ArrayList<integer> inorderTraversal(TreeNode root) { // Start typing your Java solution below // DO NOT write main() function if(root == null){ return new ArrayList<integer>();
} Stack<treenode> stack = new Stack<treenode>(); stack.push(root); ArrayList<integer> al = new ArrayList<integer>();

    while(!stack.empty()){
    root=stack.peek();

    if(root.left != null){
        stack.push(root.left);  //if left subtree is present push it
    }

    else if(root.right !=null){
        TreeNode top = stack.pop(); //if left subtree is empty, pop root and push right
        al.add(top.val);
        stack.push(top.right);
    }
    else if(root.left == null && root.right == null){ //if we are at leaf node pop it
        TreeNode top = stack.pop();
        al.add(top.val);

        if(!stack.empty()){
            top = stack.pop(); //pop the parent of leaf as well
            al.add(top.val);
        }

        while(top.right==null && !stack.empty()){ //keep popping till we come across a non empty right tree
            top=stack.pop();   
            al.add(top.val);
        }

        if(top.right!=null){
            stack.push(top.right); //push right
        }

        }
    }
    return al;    
    }

Answer 6

public ArrayList<Integer> inorderTraversal(TreeNode root) {
    ArrayList<Integer> rl = new ArrayList<Integer>();
    if(root == null) return rl;
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.add(root);
    while(!stack.isEmpty()){
        TreeNode tmp = stack.peek();
        if(tmp.left != null) {
            stack.push(tmp.left);
            tmp.left = null;
        }
        else{
            stack.pop();
            rl.add(tmp.val);
            if(tmp.right != null) stack.push(tmp.right);
        }
    }
    return rl;
}

Answer 7

Morris algorithm.

void inOrderMorris(TreeNode* root, vector<int> &arr) {
    TreeNode *p, *tmproot = root;

    while (tmproot) {
        if (!tmproot->left) {
            arr.push_back(tmproot->val);
            tmproot = tmproot->right;
        }
        else {
            p = tmproot->left;
            // find the right most leaf node on the left side
            while (p->right && p->right != tmproot) {
                p = p->right;
            }
            // if this node has not been handled,
            // let this node's right pointer point to tmproot
            if (!p->right) {
                p->right = tmproot;
                tmproot = tmproot->left;
            }
            // if this node has been handled,
            // restore this node's right point to NULL
            else {
                arr.push_back(tmproot->val);
                p->right = NULL;
                tmproot = tmproot->right;
            }
        }
    }
}
vector<int> inorderTraversal(TreeNode *root) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    vector<int> arr;
    inOrderMorris(root, arr);
    return arr;
}

Answer 8

vector<int> inorderTraversal(TreeNode *root) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    stack<TreeNode*> ss;
    ss.push(root);
    vector<int> ret;

    while(!ss.empty()){
        TreeNode *node = ss.top();

        if(node){
            ss.push(node->left);
        }
        else{
            ss.pop();
            if(!ss.empty()){
                TreeNode *tmp = ss.top();
                ret.push_back(tmp->val);
                ss.pop();
                ss.push(tmp->right);
            }
        }
    }

    return ret;
}

Answer 9

class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> retval;
        stack<TreeNode*> s;
        TreeNode *current = root, *tmp;
        while(current || !s.empty()){
            if (current){
                s.push(current);
                current = current->left;
            }else{
                tmp = s.top();
                s.pop();
                retval.push_back(tmp->val);
                current=tmp->right;
            }
        }
        return retval;
    }
};

// this is 1337c0d3r's solution.

Binary Tree Inorder Traversal

Follow this question

Welcome to LeetCode

Related questions