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

x
Solved

# Traverse a binary tree iteratively

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

Thanks
0
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.

Paul
0

LVL 14

Accepted Solution

hoomanv earned 600 total points
ID: 16813756
0

## Featured Post

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
Course of the Month18 days, 2 hours left to enroll