Iterative Binary Tree Traversal in Java

/** Iteratively traverses the binary tree in pre-order */
public void preorder( ) {
    if( root == null ) return;

    Stack<Node> stack = new Stack<Node>( );
    stack.push( root );

    while( ! stack.isEmpty( ) ) {
        Node current = stack.pop( );
        if( current.right != null ) stack.push( current.right );
        if( current.left != null ) stack.push( current.left );
        System.out.print( current.data + " " );
    }
}

/** Iteratively traverses the binary tree in in-order */
public void inorder( ) {
    Node node = root;
    Stack<Node> stack = new Stack<Node>( );
    while( ! stack.isEmpty( ) || node != null ) {
        if( node != null ) {
            stack.push( node );
            node = node.left;
        } else {
            node = stack.pop( );
            System.out.print( node.data + " " );
            node = node.right;
        }
    }
}

/** Iteratively traverses the binary tree in post-order */
public void postorder( ) {
    if( root == null ) return;

    Stack<Node> stack = new Stack<Node>( );
    Node current = root;

    while( true ) {

        if( current != null ) {
            if( current.right != null ) stack.push( current.right );
            stack.push( current );
            current = current.left;
            continue;
        }

        if( stack.isEmpty( ) ) return;
        current = stack.pop( );

        if( current.right != null && ! stack.isEmpty( ) && current.right == stack.peek( ) ) {
            stack.pop( );
            stack.push( current );
            current = current.right;
        } else {
            System.out.print( current.data + " " );
            current = null;
        }
    }
}

Inorder Tree Traversal without Recursion(use stack)

Using Stack is the obvious way to traverse tree without recursion. Below is an algorithm for traversing binary tree using stack. See this for step wise step execution of the algorithm.

1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then 
     a) Pop the top item from stack.
     b) Print the popped item, set current = current->right 
     c) Go to step 3.
5) If current is NULL and stack is empty then we are done.

Let us consider the below tree for example

            1
          /   \
        2      3
      /  \
    4     5

Step 1 Creates an empty stack: S = NULL

Step 2 sets current as address of root: current -> 1

Step 3 Pushes the current node and set current = current->left until current is NULL
     current -> 1
     push 1: Stack S -> 1
     current -> 2
     push 2: Stack S -> 2, 1
     current -> 4
     push 4: Stack S -> 4, 2, 1
     current = NULL

Step 4 pops from S
     a) Pop 4: Stack S -> 2, 1
     b) print "4"
     c) current = NULL /*right of 4 */ and go to step 3
Since current is NULL step 3 doesn't do anything. 

Step 4 pops again.
     a) Pop 2: Stack S -> 1
     b) print "2"
     c) current -> 5/*right of 2 */ and go to step 3

Step 3 pushes 5 to stack and makes current NULL
     Stack S -> 5, 1
     current = NULL

Step 4 pops from S
     a) Pop 5: Stack S -> 1
     b) print "5"
     c) current = NULL /*right of 5 */ and go to step 3
Since current is NULL step 3 doesn't do anything

Step 4 pops again.
     a) Pop 1: Stack S -> NULL
     b) print "1"
     c) current -> 3 /*right of 5 */  

Step 3 pushes 3 to stack and makes current NULL
     Stack S -> 3
     current = NULL

Step 4 pops from S
     a) Pop 3: Stack S -> NULL
     b) print "3"
     c) current = NULL /*right of 3 */  

Traversal is done now as stack S is empty and current is NULL. 

Iterative Tree Traversals (转载)

Tree traversals, are very important for any interview. Almost any interview question that you get, can be solved by finding out the correct traversal to use. You can read and compare various tree traversals from here .

Although the recursive tree traversals, can be coded very neatly but recursion is generally not preferred. Excessive recursive function calls may cause memory to run out of stack space.

Since the depth of a balanced binary search tree is about lg(n), we need not worry about running out of stack space, even if there are a million elements in the tree. But alas perfectly balanced trees, come at their own cost. Rather efficient height balanced trees is still an active area of interest. So it is quite possible in practical scenarios that the tree may not be balanced. If that is the scenario then we are asking for trouble using recursion, because in the worst case the height of the tree may go up to n and in this case, the stack space will eventually run out and the program will crash.
Iterative tree traversals can be coded easily, using a _ visited _ flag. This has been sufficiently explained at this wiki page . But this requires us to change the structure of the tree, and we would not want that. here we will attempt to develop iterative traversals, without modifying the structure.
Understanding the below given iterative traversals can be a little tricky so the best way to understand them is to work them out on a piece of paper. Use this sample binary tree and follow the steps of the below given codes.

In Order Traversal:
The in order traversal requires that we print the leftmost node first and the right most node at the end. So basically for each node we need to go as far as down and left as possible and then we need to come back and go right. Steps of algorithm are:

1. Start with the node equals root
   
2. Store the node in the stack and visit it's left child.
   
3. Repeat step 2 while node is not NULL, if it's NULL then pop it's parent (i.e. the last node in stack) and print it.
   
4. Now move to node's right child and repeat step 1
   
5. Repeat whole procedure while node is not NULL and stack is not empty
   

Inorder(Tree *p)
{
    stack < Tree* > S;
    do
    { 
        while (p!=NULL)                      
        { 
            // store a node in the stack and visit it's left child
            S.push(p);
            p=p->left; 
        }

        // If there are nodes in the stack to which we can move up
        // then pop it
        if (!S.empty())
        { 
            p=S.top();
            S.pop();

            // print the nodes value
            cout << p->ele << "-";

            // vistit the right child now
            p=p->right; 
        }

    // while the stack is not empty or there is a valid node
    }while(!S.empty()||p!=NULL);
}

Food for Thought: The above given iterative solution makes use of explicit stack. We have only managed to eliminate the recursion, but not the extra space requirement. Can there be another way in which we can give an in-order traversal without using a stack?
Yes! you can do that and there are two methods. But both of them require to change the tree structure as we generally us it.

• One is pretty intuitive, and that is to have a parent pointer, in addition to the child pointer. This eliminates the need for extra space, because the whole purpose of using a stack was to save the parent nodes.
  
• The second is not so intuitive, but a very popular data structure and that is Threaded Binary Tree . This along with the normal structure, also stores a pointer to the next in-order successor of a node. In case there is a right child then the in-order successor is the child otherwise it is one of the successors.
  

Pre Order Traversal:
Pre order is very similar to in order traversal. The way of accessing all the nodes remains the same except the position where we print the node. Now the node is printed/visited before visiting the children of the nodes. Steps are very similar to in-order

1. Start with node equal to root node
   
2. Store the node in the stack, print it and visit it's left child.
   
3. Repeat step 2 while node is not NULL, if it's NULL then pop it's parent (i.e. the last node in stack).
   
4. Now move to node's right child and repeat step 2
   
5. Repeat whole procedure while node is not NULL and stack is not empty
   

  Preorder(Tree *p)    
{ 
    stack < Tree* > S;
    do
    {     
        while (p!=NULL)
        { 
            // storea node in stack and print it's value
            S.push(p);
            cout << p->ele << "-";
            // visit the left child
            p = p->left; 
        }

        // visit the right child
        if (!S.empty())
        {
            p=S.top();
            S.pop();
            p = p->right; 
        }

    } while(!S.empty()||p!=NULL);
}

Post Order Traversal:
Post order traversal is the trickiest one out of them all and hence it is not very frequently asked as an interview question. But Amazon has asked the iterative implementation once. It is useful in some cases

• Tree deletion: In order to free up allocated memory of all nodes in a tree, the nodes must be deleted in the order where the current node is deleted when both of its left and right sub-trees are deleted. This can be done using post-order traversal only.
  
• It is also used in evaluating Post-fix or Reverse Polish Notation.
  

The problem with post-order traversal is that in the previous two cases when a node was popped of from the stack, then it was finally removed and was not accessed again. However in case of post-order the node needs to be accessed from the stack twice, and is deleted only in the second access.
First time we find a node, we push it on to the stack, the second time we examine it from the stack to go to it's right child and then finally after visiting both the right sub-tree and the left-subtree we remove the node from the stack. So a node stays in the stack as long as it's sub-trees have not been visited.

Since, a node has to be visited(printed in the trivial case) only after it's left and right child have been visited, we print a node's value after we have visited the left child followed by the right child. The property that is exploited in this implementation is that the the parent node will always be visited just after visiting it's right child.

After visiting the left child, when we come to the parent node in the stack if the right child is NULL, then we can straight away print the node, but if it's not NULL then we have to check whether the previous node which was printed is it's right child. If it's the right child then we can visit the current node, otherwise the right child has not been visited and we must proceed with the right child.
Hence in this traversal, we have to use a previous pointer, only then will we able to correctly traverse the node. Otherwise we do not know when the right child has been visited or not.

1. Start with the root node.
   
2. Store the node in the stack, and visit it's left child.
   
3. Repeat step 1 while node is not NULL, if it's NULL:
   
   • Pick the top most node from the stack.
     
   • If it's right child is NULL, then print the node and set prev pointer to this node
     
   • If it's not NULL, check whether the right child is equal to prev pointer, if it is then print the node, else repeat step 1 with the right child
     
   • In this step, if you print the node then current is made equal to NULL and this sub-loop is repeated untill stack is not empty and current is NULL
     
4. Since the root node remains in the stack till the end, the terminating condition is untill stack is empty
   

  Postorder(Tree *p)  
{
    stack < Tree* > S;
    Tree *prev;
    do
    { 
        while (p!=NULL)
        { 
            S.push(p);
            p=p->left;
        }
        if(!S.empty())
        {
            while(p==NULL && !S.empty())
            {
                p=S.top();
                if(p->right!=NULL)
                {
                    if(p->right == prev)
                    {
                        cout << p->ele  <<  "-";
                        S.pop();
                        prev = p;
                        p = NULL;
                    }
                    else
                        p = p->right;
                }
                else
                {
                    cout << p->ele  <<  "-";
                    S.pop();
                    prev = p;
                    p = NULL;
                }
            }
        }    
    }while(!S.empty());
}

说一下学术派的代码（java）

前面看到有人说写出来的代码让人一眼就看出是没有工作经验的 这个的确是有可能的，从我自身经验判断 一般来说，具备以下一个或几个特点的代码 会被认为是写java代码写不够多的人写出来的 

 1) 变量名和方法名首字母大写 这个是大忌，一般遇到了，不让过是很正常的 从某种意义上说，这个不是风格的问题 跟goto一样，其实是个错误 

2) 命名中使用下划线 尤其是自定义的系统变量，喜欢用下划线开始 这说明程序猿喜欢介入系统内部实现 which正好是java不提倡的做法 java提倡非侵入式编程 也就是对于已经做好的东西，比如jvm 采用输入参数形式来tune 其次，对于具体对象的管理，采用反射等高级手段来做 直接介入系统内部实现，比如介入jvm内部实现 的方式，其实是不提倡，甚至可以说是禁止的 对于下划线的命名，能不用就不用 所以当你遇到了_myInstance的时候，嗯 

3) static关键字的使用 能写出static方法是好事 说明你懂static是干什么的 但是多数时候，static其实并不是那么频繁滴被使用到 static的代码实现多数时候交给了框架去做 一般如果你要用static 建议单独搞一个类，然后在这个类的命名最后加上Util 比如MyApplicationUtil，这样就显得professional一点 static变量应该尽量避免 关于2和3，有一个特例，就是全局常量（不变的变量）的定义 比如public static final String BIG_COW = "goodbug"; 这个时候你需要static变量和下划线，其它时候，最好不要了 

4) 封装的意识         对于一个类，实现之后，看是否意识到实现了private和set/get方法 还是直接访问内部变量 这个是oop，set/get方法可以有很多理由 比如说，只实现get而不实现set，那么这就是read only 还有并发的时候，可以通过syncrhonized set/get方法来控制并发 等等 

5）最后一个就是看对于各种类的使用 比如Hashtable，这个已经too old了 还有Vector这几个类，都已经old太久了 有新类能够替换这些类，所以如果你打算用java写代码 请躲开这几个“老”类 

这几个细节，虽然说都是rule of thumb，都不难，稍微留意一下，都很容易避开 但是很有趣的是，往往是一些有其它语言经验的程序猿 比如写c++写得比较多的，转过来，会犯这些错误 所以有时候雇主更喜欢新人，白纸一张，可塑性很强 换编程语言的程序猿，会带来不少坏习惯 当然最理想的还是有相关经验的程序猿 只要能针对上诉五点，稍加练习，你的代码显得比较professional问题不大