DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks

Binary Tree: Preorder Traversal without Recursion

Puneet Monga user avatar by
Puneet Monga
·
May. 20, 14 · Interview
Like (1)
Save
Tweet
Share
18.13K Views

Join the DZone community and get the full member experience.

Join For Free
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();
        }
    }
}
Tree (data structure)

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • Utilize OpenAI API to Extract Information From PDF Files
  • Taming Cloud Costs With Infracost
  • Building a Scalable Search Architecture
  • How and Why You Should Start Automating DevOps

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends: