[Last Call] Learn how to a build a cloud-first strategyRegister Now


Traverse a binary tree iteratively

Posted on 2006-06-01
Medium Priority
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

ID: 16812164
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

hoomanv earned 600 total points
ID: 16813756

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
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 opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.
Suggested Courses

829 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