Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Binary Tree: Preorder Traversal without Recursion

DZone's Guide to

Binary Tree: Preorder Traversal without Recursion

· Java Zone
Free Resource

Microservices! They are everywhere, or at least, the term is. When should you use a microservice architecture? What factors should be considered when making that decision? Do the benefits outweigh the costs? Why is everyone so excited about them, anyway?  Brought to you in partnership with IBM.

I thought that it would be an interesting exercise to try implementing Binary Tree traversal techniques without recursion. Below is the implementation of Preorder Traversal without recursion.

I have used a queue in order to implement the pre-order traversal without recursion. Since it's a pre-order traversal, we need to visit root, then left and then right subtree.

Steps / Pseudo Code:

  1. Push all the nodes that are towards the left of tree into a queue; starting from root node all the way down to the the leaf node.
  2. Perform the following steps in a loop until queue is empty
    • Pop the node from the queue. Lets call it node P
    • Visit node P
    • Push all the nodes that are towards left of P.right subtree into the queue.
  3. That's it.

Points to note:

  • Since it's a pre-order traversal, we need to visit the root node first. That justifies the purpose of using a queue. Being a FIFO based data structure, it lets me push the root node first and retrieve it back in the same order (i.e. order of insertion).
  • The idea is to push all the nodes that are towards the left in the binary tree to the queue. Whenever a node is visited or popped out from the queue, we need to make sure that right subtree of that node is not left out. That's the point when we push all the nodes, that are towards the left in the right subtree of recently popped out node, into a queue
Below is the implementation in Java. Other supporting classes such as the implementation of binary tree are attached to this post. 
package info.codeaddict.blog.tree.binary;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author codeaddict.info
 */
public class PreOrderWithoutRecursion implements Traversal {

    @Override
    public void traverse(BinaryTree.Node root) {
        Queue<BinaryTree.Node> queue = new LinkedList<>();
        pushAllLeft(queue, root);
        while (!queue.isEmpty()) {
            BinaryTree.Node node = queue.poll();
            System.out.println(node.value());
            pushAllLeft(queue, node.right());
        }
    }

    private void pushAllLeft(Queue<BinaryTree.Node> queue, BinaryTree.Node node) {
        while (node != null) {
            queue.add(node);
            node = node.left();
        }
    }
}

Discover how the Watson team is further developing SDKs in Java, Node.js, Python, iOS, and Android to access these services and make programming easy. Brought to you in partnership with IBM.

Topics:

Opinions expressed by DZone contributors are their own.

The best of DZone straight to your inbox.

SEE AN EXAMPLE
Please provide a valid email address.

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.
Subscribe

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}