# BST In Order Traversal

I have written code to input data into a BST.  This data after being placed in the tree is shown below.  I would like to print this data in order.  After making the tree on paper i noticed that the path we need to take is Left pointer, parent, right pointer.  What is the best way to do this?
microsoft        3989898989 02 03
java             1357357357 05 12
zipinfo          0490080000 04 28
pizzahut         3789789789 20 07
cnn              1444444444 21 09
yahoo            2121212121 11 00
ilounge          4040404040 18 00
dictionary       0555555555 31 10
expedia          1234543210 00 17
un               3939393939 13 14
limewire         1010101010 22 00
quicken          4294967295 00 15
verizon          2468246824 00 16
secondlive       1888888888 25 26
wikipedia        4242424242 00 19
howstuffworks    0000000001 00 00
xe               0123123123 00 00
nytimes          1234554321 27 23
barnesandnoble   1111111111 24 00
kalamazoocity    2444666888 00 00
oprah            2999999999 00 00
amazon           2222222222 00 30
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
The easiest way uses a recursive function to walk the nodes.  It would be easier to explain if I saw your data structure, but here's some pseudo-code to get started.  Pass the root node to PrintTree to print the entire tree or any child node to print just that node and all descendants.

Function:  PrintTree(node_pointer)
1. If node_pointer is null, return.
2. Call PrintNode(node_pointer.left_pointer).
3. Print the current node.
3. Call PrintNode(node_pointer.right_pointer).

That should do it.
0
Author Commented:
The data for the BST was attached to this question.  If you look at the BST, Microsoft is the root of the tree and then the left and right child pointers point to other nodes.
0
Commented:
I understand that.  What part of my answer are you having trouble with?  This is a standard BST search algorithm.
0
Author Commented:
I am able to find the last node of the tree by following the left pointer until it equals 00.  Once i get to there i know i need to write the parent node and then the right node.  The trouble i have is, when i get to cnn lets say, i have multiple nodes off of that which i have to write.  Then after that i have to come back to cnn and write the parent node of that.  The code that i am writing for this isn't working out.
0
Commented:
Did you read my post about creating a recursive function to handle this?  The beauty of using a recursive function is that you don't need to follow any path, the function is smart enough to find all nodes and print them in order.  It works every time.  If you post some of your source code, I'll help you create one.  I need to know how you are storing the nodes.
0
Author Commented:
Below is the code that i use to create the BST.  A line is read in from a file and inputed into a string[,] BSTHold.  Once this is done, it ouputs the array i placed in my original question.  Let me know if this helps, thanks a lot!
public static void Create(ref int nextEmpty, ref int rootPtr, ref string url, ref string ipAddress,
ref int Incrementer, ref int Incrementer2, ref string data, ref int N, ref StreamWriter WriteToLog,
ref int leftChPtr, ref int rightChPtr, ref string[,] BSTHold, ref StreamReader ReadInFile, ref int menuchoice, ref int NodeCount)
{

for (int i = 0; i < 16; i++)//Reading the first 16 characters of the data string
{
url += data[i];
}

for (int j = 17; j < 27; j++)//Reading the second 10 characters of the data string
{
}

N++;

while (data != null)
{
InsertInBST(ref rootPtr, ref BSTHold, ref nextEmpty, ref url, ref ipAddress,
ref Incrementer, ref Incrementer2, ref rightChPtr, ref leftChPtr, ref N, ref data, ref ReadInFile, ref menuchoice, ref NodeCount);
}

WriteToLog.WriteLine("*Create BST Done: {0} BST nodes, root is at node 1", N.ToString("d2"));
}

public static void InsertInBST(ref int rootPtr, ref string[,] BSTHold, ref int nextEmpty, ref string url, ref string ipAddress,
ref int Incrementer, ref int Incrementer2, ref int leftChPtr, ref int rightChPtr, ref int N, ref string data, ref StreamReader ReadInFile, ref int menuchoice, ref int NodeCount)
{
if (rootPtr == 0)
{

BSTHold[nextEmpty, 0] = url;
BSTHold[nextEmpty, 2] = leftChPtr.ToString();
BSTHold[nextEmpty, 3] = rightChPtr.ToString();

rootPtr = 1;
nextEmpty++;
}

else
{
BSTHold[nextEmpty, 0] = url;
BSTHold[nextEmpty, 2] = leftChPtr.ToString();
BSTHold[nextEmpty, 3] = rightChPtr.ToString();

int v = 1;
Incrementer2 = 1;
int RowDim = 0;

while (BSTHold[Incrementer + 1, 0] != null)
{
while (BSTHold[Incrementer2 + 1, 0] != null)
{
if (string.Compare(url, BSTHold[v, 0]) < 0)
{
if (BSTHold[v, 2].Equals("0"))
{
BSTHold[v, 2] = nextEmpty.ToString();
v++;

Incrementer2 = (BSTHold.GetLength(RowDim) - 3);
}
else
{
v = Convert.ToInt32(BSTHold[v, 2]);
}

Incrementer2++;
}
else
{
if (BSTHold[v, 3].Equals("0"))
{
BSTHold[v, 3] = nextEmpty.ToString();
v++;

Incrementer2 = (BSTHold.GetLength(RowDim) - 3);
}
else
{
v = Convert.ToInt32(BSTHold[v, 3]);
}

Incrementer2++;
}

NodeCount++;
}
Incrementer++;
v++;
}

nextEmpty++;
}

{

if (data != null)
{
url = "";

for (int i = 0; i < 16; i++)//Reading the first 16 characters of the data string
{
url += data[i];
}

for (int j = 17; j < 27; j++)//Reading the second 10 characters of the data string
{
}

N++;
}
}
}
0
Commented:
It looks like you are storing the BST in a 2-dimensional string array where the first index indicates the node location and the second index indicates the data stored in the node.  This is not the best way to store a tree, but it should work.  I would normally define a custom Node class and store the nodes in a linked list.

Anyway, here's my attempt at writing a PrintTree function for your array.  You will need to add the code that prints the actual values and I'm not sure if I'm passing your tree variable correctly, but it should get you on the right path.  Notice that PrintTree operates on one node at a time and calls itself to traverse the entire tree.

To print the entire tree, just call PrintTree with the root node (ex: PrintTree(BSTHold[0], BSTHold);).

You can also print a partial tree by passing in any node (ex: PrintTree(BSTHold[5], BSTHold);).
public static void PrintTree(ref node, ref string[,] BSTHold){
if (node[2] != "0") PrintTree(BSTHold[node[2]], ref BSTHold);
// Insert code to print the node here.
if (node[3] != "0") PrintTree(BSTHold[node[3]], ref BSTHold);
}
0

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Commented:
Bill-Hanson has given you good advice. However, after looking at your code, there are a few things I would like to add.

1. There are two advantages to using a tree. First, a pre-order traversal will return the nodes in a specific order - in this case alphabetic order. Second, you can search for any node in the tree very quickly - order of LOG-Base2(n) compares. There is also one big disadvantage. In order to preserve the fast search, you have to balance the tree as you add nodes. In your code, the first node entered is always the root. There is no balancing. Consider what your tree would look like if the nodes were added in alphabetic order. In that case, no node would have a left child, and you are left with a linear list of nodes. That's still a valid tree, but it's not balanced, and searches become Order(n).

2. You are converting numeric values to strings, then back to numbers when you want to use them. That's expensive. If you want to keep various data types together in a list or array, it is more efficient to create a very thin class or struct to contain the data.

3. When you read the data in from the file, you are concatenating a fixed number of characters one at a time to a new string. Each iteration through each of those two loops causes a new string to be allocated on the heap, and the previous one is abandoned for garbage collection. Substring would be much more efficient in both time and memory consumption.

4. Balancing a tree is a complex task. Given the way you are using the string array, I believe it would be much more efficient, and easier to write and debug if you just create an ordered list. If you always know in advance how big the list will be, you can use an array, but inserts are easier in a list. It's not hard to write a simple binary search for an ordered list. That gives you Order LOG(n) searches without the need to balance the tree.

Jim
0
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C#

From novice to tech pro — start learning today.