Traverse a binary tree iteratively

Posted on 2006-06-01
Last Modified: 2008-03-04
Hi folks,

How can I traverse a binary tree iteratively instead of recursively? (pre-order, in-order, and post order)

The binary tree is just a regular binar tree (not a binary search tree). Each tree is a node, with three elements, node value, pointer to left child, and pointer to right child.

Question by:tiger0516
    LVL 16

    Expert Comment

    Hi tiger0516,

    This is always an interesting homework question. The joy of it is, however you try to do it, you almost always end up trying to emulate a stack. It's intended to show you that 'sometimes' the recursive solution is the most optimal.

    However, it is not always the best! For example, if you want to postpone the search while it os running and go off and do something else for a while, a recursive solution is not easy to manage.

    The answer is to hold a stach of levels, ideally growable but I doubt that would impress anyone. Allow yourself, say 100 levels. The stack needs only to contain node pointers.

    Whenever you step deeper into the tree, 'push' a pointer to the node you are leaving onto the stack. To step out of the tree by one node, just pop the top pointer off the stack.

    Post some code and we'll help you get it right. :-)

    LVL 14

    Accepted Solution


    Featured Post

    How to run any project with ease

    Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
    - Combine task lists, docs, spreadsheets, and chat in one
    - View and edit from mobile/offline
    - Cut down on emails

    Join & Write a Comment

    This tutorial is posted by Aaron Wojnowski, administrator at  To view more iPhone tutorials, visit This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
    Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
    The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
    The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.

    754 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    21 Experts available now in Live!

    Get 1:1 Help Now