473,322 Members | 1,781 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes and contribute your articles to a community of 473,322 developers and data experts.

Binary tree traversal with stack data structure

This is an eclipse based project. So the attachment may be unzipped and run in eclipse.
eclipse Juno and Java 7 has been used. First the code should be inspected and run. Then the blog may be reffered.
======================================

Stack based implementation of Binary Tree traversal. The ArrayList<Integer> result variable will have the traversal result
In this example I have added the data from a node to the ArrayList.
Entry.java should be run as Java Application. This class basically tests the functionalities.

A close inspection to the code will make it easy to understand that left branch of a root is always explored before the right branch. For example: The order of stack insertion of nodes in a sub tree is the same for all three traversals.
1) Insert Root --> 2) insert until the last left child --> 3)pop until the top node of the stack has a right child--> 4) Insert Right child (This child is the new Root now, call this node as "new Root 1") -->5) Follow all the steps from 2 to 4 recursively till the top node of the stack is again "new Root 1" --> pop "new Root 1" --> pop Root


InOrder
=======
The Node data will be added to the ArrayList only in the following cases

1> When any of the leafe nodes pops, it's data/node will be added
2> Immidiately after a left child is popped, the parent's data/node will be added
3> if the parent does not have a left child, it's data/node will be added immidiately before it's right child is pushed into the stack.

PreOrder
========
After every push() operation to the stack, the data/node of the pushed node will be added.

Post Order
==========

The Node data will be added to the ArrayList only in the following cases

1> If a node does not have a right child, but has a left child, then immidiately after the left child is popped, parent's data/node
will be added (after popping the parent).

2> Immidiately after popping out the right son, the parent's data/node will be added (after popping the parent).

3> A leaf is always popped and it's data/node is added.

There should be one change and the following line in italics will be replaced by the statement in bold.
Attached Files
File Type: zip treetraversal.zip (4.5 KB, 200 views)
Sep 25 '14 #1
2 5549
Hi ZMBD, could you please remove the following line in italics completely?

"A close inspection to the code will make it easy to understand that left branch of a root is always explored before the right branch. For example:"

I am unable to do it.
Thanks in advance!
Sep 30 '14 #2
For theory portion please follow my another article
http://bytes.com/topic/algorithms/in...actually-works

Also please ignore the following portion in this current article

A close inspection to the code will make it easy to understand that left branch of a root is always explored before the right branch. For example: The order of stack insertion of nodes in a sub tree is the same for all three traversals.
1) Insert Root --> 2) insert until the last left child --> 3)pop until the top node of the stack has a right child--> 4) Insert Right child (This child is the new Root now, call this node as "new Root 1") -->5) Follow all the steps from 2 to 4 recursively till the top node of the stack is again "new Root 1" --> pop "new Root 1" --> pop Root
Oct 15 '14 #3

Sign in to post your reply or Sign up for a free account.

Similar topics

4
by: Jerry Khoo | last post by:
Thanks for the answer, and by the way, i would like to know that in C++, how u create a tree using a recursive envronment. It seems that most people used struct to create a node than, using...
7
by: Lynn | last post by:
I am rewriting some memory management code and I need to have a forward declaration of a data structure. I am not converting this data structure into a class (yet). How do I generate a forward...
6
by: Ravi | last post by:
Hi, I need to find the non-recursive algorithm to find the height of a Binary Tree. Regards, SunLight.
4
by: Ken | last post by:
I have a binary tree in VB NET and insertions seem to be slow. The program receives data from one source and inserts it into the tree. The program receives data from another source and...
10
by: Aris | last post by:
Hello! This is my problem. I'm trying to make an inorder traversal algorithm for a binary tree, not a recursive one, but using a stack. Till now I got this: void traverse(tree * p) { l:...
4
by: ch13f | last post by:
Kindly help me with these problems .. *sigh* I'm having a hard time for this .. C Programming please .. Problem 1 : Create a program to test the package for the ADT stack INPUT : Commands...
6
by: APEJMAN | last post by:
would you please help me? I wrote 3 separate line of code for printing my binary tree, and now I am trying to print the level-order traversal of the tree, where the nodes at each level of the tree...
4
by: APEJMAN | last post by:
would you please help me with this question? I know that a binary tree can be recovered from its pre-order traversal. That is, a tree built from the pre-order traversal should always be the same as...
1
by: rashmiharitas | last post by:
why are we storing object references varibles on stack data structure why not any other data structure please let me know about this
2
by: slizorn | last post by:
hi guys, i need to make a tree traversal algorithm that would help me search the tree.. basically i need to read in a text file... shown below H H,E,L E,B,F B,A,C A,null,null c,null,D
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.