6

Part of it is that I have to implement a non-recursive method of a inorder traversal of a binary tree. I am kind of stuck. Here is what I have so far:

public void inorder(BinaryTree v) {
    Stack<BinaryTree> stack = new Stack<BinaryTree>();
    stack.push(v);
    System.out.println(v.getValue());

    while(!stack.isEmpty()) {
        while(v.getLeft() != null) {
            v = v.getLeft();
            stack.push(v);
            System.out.println(v.getValue());
        }

        while(v.getRight() != null) {
            v = v.getRight();
            stack.push(v);
            System.out.println(v.getValue());
        }
                stack.pop();
    }
}

I noticed that it only prints out the left side of my tree, e.g.

          A
        /   \
       B     C
     /   \  /  \
    D     E F   G
   /  \
  H     I
 / \
J   K

Gives A B D H J

3 Answers 3

19

You can greatly simplify the above with a single while loop:

Stack<Node> stack = new Stack<>();
Node current = root;
while(current != null || !stack.isEmpty()){
  if(current != null){
    stack.push(current);
    current = current.left;
  } else if(!stack.isEmpty()) {
    current = stack.pop();
    process(current);
    current = current.right;
  }
}

Basically the code above pushes left branches on the stack until it reaches the leftmost node in the branch. Then it pops it and processes it (you can print it or do something else with it) and then it pushes the right branch on the stack to process since the left branch and the node itself are done.

7

Following your code, the while loop for the getLeft() part goes all the way down the left of the tree, then exits. v is now node J, which has no right child so the next while loop doesn't run.

Try this code example: http://www.ashishsharma.me/2011/09/inorder-traversal-without-recursion.html

StackOverflow answer: https://stackoverflow.com/a/12718147/1178781

// Inorder traversal:
// Keep the nodes in the path that are waiting to be visited
Stack s = new Stack(); 
// The first node to be visited is the leftmost
Node node = root;
while (node != null) {
    s.push(node);
    node = node.left;
}
// Traverse the tree
while (s.size() > 0) {
    // Visit the top node
    node = (Node)s.pop();
    System.out.println((String)node.data);
    // Find the next node
    if (node.right != null) {
        node = node.right;
        // The next node to be visited is the leftmost
        while (node != null) {
            s.push(node);
            node = node.left;
        }
    }
}
1
  • Thank you so much, the comments helped me to to understand how this works even more :)
    – tenkii
    Mar 15, 2013 at 21:41
0

Another simpler binary traversal implementation :

import java.util.Stack;

public class BinaryTree {

    public static void main(String args[])
    {
        Node root = Node.createDummyTree();
        Node tnode; //= root;

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

        if (root != null)
        {
            stack.push(root);
        }

        while (!stack.isEmpty())
        {
            tnode = stack.pop();

            if (tnode != null)
            {
                System.out.println(tnode.value);

                if(tnode.rightNode != null)
                {
                    stack.push(tnode.rightNode);
                }

                if (tnode.leftNode != null)
                {
                    stack.push(tnode.leftNode);
                }
            }
        }
    }

}

class Node {
    public Node leftNode;
    public Node rightNode;
    public String value;

    Node(String value)
    {
        this.value = value;
    }

    /**
     *  Construct a dummy binary Tree
     *               A
     *          /         \
     *         B           C
     *       /   \       /   \
     *      D     E     F     G
     *     / \   / \   / \   / \
     *    H   I J   K  L  M  N  O

     * @return
     */

    public static Node createDummyTree(){

        Node root = new Node("A");
        root.leftNode = new Node("B");
        root.rightNode = new Node("C");

        Node tnode = root.leftNode;
        tnode.leftNode = new Node("D");
        tnode.rightNode = new Node("E");

        Node tempNode = tnode.rightNode;  //remember "E"  

        tnode = tnode.leftNode;
        tnode.leftNode = new Node ("H");
        tnode.rightNode = new Node ("I");

        tnode = tempNode;

        tnode.leftNode = new Node ("J");
        tnode.rightNode = new Node ("K");

        tnode = root.rightNode;
        tnode.leftNode = new Node("F");
        tnode.rightNode = new Node("G");

        tempNode = tnode.rightNode;  // rememebr "G"

        tnode = tnode.leftNode;
        tnode.leftNode = new Node("L");
        tnode.rightNode = new Node("M");

        tnode = tempNode;

        tnode.leftNode = new Node("N");
        tnode.rightNode = new Node("O");

        return root;
    }
}
1
  • This is a pre-order traversal but OP is referring to an in-order traversal. Jan 23, 2021 at 7:52

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.