Binary Search Tree In-Order Traversal Iterative Solution

Given a binary search tree, print the elements in-order iteratively without using recursion.


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:

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.

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.

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:


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:

  1. 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.
  2. By using a Threaded Binary Tree. Read the article: Threaded Binary Tree on Wikipedia for more information.
VN:F [1.9.22_1171]
Rating: 4.7/5 (71 votes cast)
Binary Search Tree In-Order Traversal Iterative Solution, 4.7 out of 5 based on 71 ratings

51 thoughts on “Binary Search Tree In-Order Traversal Iterative Solution

  1. Prateek

    Hi,

    Inorder can be done without visited flag as well.

    void iterative_inorder(Node * node) {

    Stack s; // Initially empty

    while(1) {
    while(node) {
    s.push(node);
    node = node->left;
    }

    if(s.isempty()) break;
    else {
    Node * temp = s.pop();
    printf("%d ", temp->value);
    node = temp->right;
    }
    }
    }

    VA:F [1.9.22_1171]
    +2
    1. itnovice

      I think the outmost while-loop (ie, while(1) is not necessary. Instead, it might cause looping problem when the inner loop is terminated by the break statement. My understand is break statement can only exit the immediate loop in case of nested loops. Once the inner while loop is terminated, there’s no way to terminate the outer loop. I didn’t try this on computer though so I might be wrong.

      Correct me if I am wrong. Thanks.

      VA:F [1.9.22_1171]
      0
      1. itnovice

        Sorry, I was wrong. I don’t think we cannot simply get rid of the outer loop otherwise only a part of the tree is traversed. I change the code as below:

        Let me know if you see any problems.

        VA:F [1.9.22_1171]
        -6
        1. itnovice

          oops, it looks like the “submit comment” function eats up all””s (less than T greater than) in my post.

          VA:F [1.9.22_1171]
          -2
  2. 1337c0d3r

    Hi Prateek,

    Yes, I did realize that there is a solution without using a flag, but it's different than yours.

    I believe your solution is to traverse the tree via left child down until it reaches the left leave, while pushing the nodes to the stack. Once it reaches the leave, pop off the stack and print its value. Then, point the current node to its right child and repeat again. (That is, treat its right child as another subtree and continue from there).

    Thanks for sharing your solution with us, it's appreciated 🙂

    VA:F [1.9.22_1171]
    +1
  3. Prateek

    Hi,

    Yes my solution is this only. Do you have a better solution without using flags? If yes, then please post that. I could think of just this approach only.

    VA:F [1.9.22_1171]
    0
  4. 1337c0d3r

    Prateek,

    I've updated this post with my solution. I don't think my solution is better, I think in general the idea is the same as yours. Congrats on solving this problem without using flags.

    VA:F [1.9.22_1171]
    0
  5. Prateek

    Hi 1337c0d3r,

    Thanks for your site. I got into Amazon 🙂
    And your site was of a great help in achieving that.

    Prateek

    VA:F [1.9.22_1171]
    0
  6. 1337c0d3r

    Hi Prateek,

    That's definitely a great news! I'm very glad that my site had help you. Congratulations to you!

    VA:F [1.9.22_1171]
    0
  7. Anonymous

    This works fine for in-order traversal (except that you are pushing a node to the stack unnecessarily – even though that makes your code simpler).

    However, I find it quite challenging to apply this construct to a post-order traversal. Have you thought of a common approach that can be applied to all three depth-first traversals in iterative way? I was a very interesting exercise for me.

    About traversing the tree in-order without using a stack, it is possible, with partially threaded tree – i.e., only using the right child node pointers to thread the tree. You can even restore the tree to the original shape.

    VA:F [1.9.22_1171]
    0
  8. Pingback: Binary Search Tree In-Order Traversal Iterative Solution « Algorithms in Pseudo Code

  9. daxingqiao

    This is the solution w/o recursion and iteration:

    void InorderTraverseNoRecursiveIteration(BinaryTree * root)
    {
    if (!root)
    {
    return;
    }
    BinaryTree * prev = NULL;
    BinaryTree * cur = root;
    while (cur)
    {
    if (!prev || prev->left == cur || prev->right == cur)
    {
    if (cur->left)
    {
    cur = cur->left;
    }
    else if(cur->right)
    {
    cout <data <right;
    }
    else
    {
    cur = prev;
    }
    }
    else if (cur->left == prev)
    {
    cout <data <right)
    {
    cur = cur->right;
    }
    else
    {
    cur = cur->parent;
    }
    }
    else if (cur->right == prev)
    {
    cur = cur->parent;
    }
    prev = cur;
    }
    }

    VA:F [1.9.22_1171]
    -1
    1. daxingqiao

      void InorderTraverseNoRecursiveIteration(BinaryTree * root)
      {
      if (!root)
      {
      return;
      }
      BinaryTree * prev = NULL;
      BinaryTree * cur = root;
      while (cur)
      {
      if (!prev || prev->left == cur || prev->right == cur)
      {
      if (cur->left)
      {
      cur = cur->left;
      }
      else if(cur->right)
      {
      cout <data <right;
      }
      else
      {
      cur = prev;
      }
      }
      else if (cur->left == prev)
      {
      cout <data <right)
      {
      cur = cur->right;
      }
      else
      {
      cur = cur->parent;
      }
      }
      else if (cur->right == prev)
      {
      cur = cur->parent;
      }
      prev = cur;
      }
      }

      VA:F [1.9.22_1171]
      0
  10. Nitish

    1337c0d3,
    Why have you not mentioned Morris Traversal for inorder traversal within constant space. Is it not a iterative inorder traversal?

    VA:F [1.9.22_1171]
    0
  11. Pingback: Binary Search Tree In-Order Traversal Iterative Solution | 口├人人│의 Blog

  12. Sivananda Reddy

    Iterative Inorder with out recursion, the following code works based on the stack size(when it decreases)
    public static void inorderIterativeStackSize(TreeNode t) {
    if(t != null) {
    boolean stackSizeDec;

    Stack s = new Stack();
    s.push(t);
    stackSizeDec = false;

    while(s.size() > 0) {
    if(stackSizeDec){
    if(s.peek().getRight() != null) {
    System.out.print(s.peek().getKey()+”, “);
    s.push(s.pop().getRight());
    stackSizeDec = false;
    }
    else {
    System.out.print(s.pop().getKey()+”, “);
    }
    }
    else {
    if(s.peek().getLeft() != null) {
    s.push(s.peek().getLeft());
    }
    else if(s.peek().getRight() != null) {
    System.out.print(s.peek().getKey()+”, “);
    s.push(s.pop().getRight());
    }
    else {
    stackSizeDec = true;
    System.out.print(s.pop().getKey()+”, “);
    }
    }
    }
    }

    }

    VN:F [1.9.22_1171]
    0
  13. reader

    Both of the alternative solutions are erroneous.
    In the else part the

    can only be NULL and you crash.
    It should be:

    instead.
    One last note:I don’t get what you mean by the statement

    . You don’t seem to use this in the refactoring of the code.

    VA:F [1.9.22_1171]
    -1
  14. Venki

    Dear 1337c0d3r,
    Here is the code without flag. Comments please…

    1. Go to left extreme, push nodes on the way
    2. Start pop-off and process each node till stack exhausts
    3. If pop-ed off node has a right child, go to step 1

    VN:F [1.9.22_1171]
    +5
  15. opoopo

    My code without flag. Comments please…

    VA:F [1.9.22_1171]
    -1
  16. Pingback: Anonymous

  17. chasemydreaming

    public void iterativeInorder() {
    BSTNode p = root;
    Stack<BSTNode> travStack = new Stack<BSTNode>();
    while (p != null) {
    while(p != null) { // stack the right child (if any)
    if (p.right != null) // and the node itself when going
    travStack.push(p.right); // to the left;
    travStack.push(p);
    p = p.left;
    }
    p = travStack.pop(); // pop a node with no left child
    while (!travStack.isEmpty() && p.right == null) { // visit it and all
    visit(p); // nodes with no right child;
    p = travStack.pop();
    }
    visit(p); // visit also the first node with
    if (!travStack.isEmpty()) // a right child (if any);
    p = travStack.pop();
    else p = null;
    }
    }

    VA:F [1.9.22_1171]
    -1
  18. Pingback: leetcode: Binary Tree Inorder Traversal solution | 烟客旅人 sigmainfy

  19. butlerain

    I think the action to be done in the loop can be divided into 2 parts.
    The 1st part is to push left child to the stack; second is to pop the top element and push its right child into the stack. So it should be something like this.

    The most difficult part is to figure out the if condition.

    VN:F [1.9.22_1171]
    +1
  20. Pingback: In-order traversal of a Binary Search Tree without recursion « ..MindWrite..

  21. Xueyuan Xing

    VN:F [1.9.22_1171]
    0
  22. Xueyuan Xing

    VN:F [1.9.22_1171]
    0
    1. lcn

      I believe your code would go in to infinite loop. Consider a simple case:
      2
      / \
      1 3
      \
      4
      2 gets pushed; top now is 2, it has a left child, then 1 pushed; top is now 1, it has no left child, stack removes 1, 1 gets printed; top now is 2 and it has a left child again!

      Please make sure you do run your code before posting it on the Internet.

      VA:F [1.9.22_1171]
      0
  23. lcn

    A stack solution like in the post order case: enumerate conditions when a node should be printed, and when necessary push a node into the stack for a second time.

    VA:F [1.9.22_1171]
    0
  24. Pingback: Binary Tree Traversal | Yeming Hu's Homepage

  25. Georg Hopp

    Solution with a parent attribute and no stack. This is a plain C solution.

    VA:F [1.9.22_1171]
    +1
  26. heng zhang

    here is another in order iterative version in python

    VA:F [1.9.22_1171]
    0
  27. Jasvinder

    Your solutions are for a general binary tree. Using the BST property should make the code simpler. Pseudocode below:-

    VA:F [1.9.22_1171]
    0
  28. Vikas Bansal

    In the solution where structure of tree is changes,
    <else {
    cout <data <right);
    }>
    It prints the top element, then pops and then pushes top element’s right child. But as soon as you pop an element, the top is changed. And you will actually skip a node.

    VA:F [1.9.22_1171]
    0
  29. Pingback: Binary Tree Preorder and Postorder Traversal: Iterative way | Kaituo

  30. Pingback: Tree Based Problems and Links | mybookmarks

  31. Pingback: LeetCode | Technical interview solutions

  32. Luciano

    I wrote a code to read a directory hierarchy. It is not a binary tree cause it can have several nodes under any node.

    It uses only a list and a stack to solve the problem. It is wrote in C# and I hope it can help you in some way:

    Regards

    VA:F [1.9.22_1171]
    0
  33. Pingback: 二叉树后序遍历的非递归实现 | 书影博客

  34. Eric Lemoine

    This is my implementation in Python

    VN:F [1.9.22_1171]
    0
  35. Pingback: Threaded binary tree in hindi | hindistudy

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*