[Q] Traverse a Binary Tree

[UchihaKite]

Hello SFML Community!

First off, I apologize if this is in the incorrect location, secondly, if their is a better forum for C++ questions, feel free to direct me to it. I think I am just used to how awesome this community is, thus, I keep coming back here lol

So, currently I am on my second C++ class in college, and I decided to ask my teacher what I could look into over the break to get ahead a little. He told me that when I come back from Summer Break, he would like an example of Traversing a Binary Tree.

My question is, if anyone has a good resource on learning how to do this? I, of course, searched Google and Youtube. However, I found that most videos were either about Binary Search Trees, or were just very poor videos. My results on Google just left me completely confused. Like, I understand what a Binary Tree is, and how to Traverse a Binary Tree, on paper. Coding it, is something that is going well over my head. Any and all help would be great!

[Laurent]

The SFML forums are definitely not the right place for such questions. Now that you've asked your question, we'll keep the topic open and try to answer it, but keep this in mind next time you have a non-SFML question

[UchihaKite]

Ah, I apologize for that. Is their a different area in the community where this question would be better placed? Sorry about that!

[Evan Bowman]

Binary trees are fairly simple, in this case even simpler since your structure doesn't need to fulfill the search tree property. They're really just a collection of nodes where each node has at most two children.

So for example, a tree node:

Code: [Select]

struct TreeNode {
TreeNode * leftChild, * rightChild;
TreeNode() : leftChild{nullptr}, rightChild{nullptr} {}  // Change to ctor style initialization if you're not using c++11
};

Then to traverse, you could simply start at the root (the initial node), and explore it's non-null children, children of children, etc.

You might want to look into existing graph traversal algorithms, Breadth First and Depth First traversal are fairly simple.

Of course, an easy recursive solution is fine if your tree is reasonably shallow.

Code: [Select]

//...
void traverse(TreeNode * pNode) {
if (pNode->leftChild) {
std::cout << "Found left child" << std::endl;
traverse(pNode->leftChild);
}

if (pNode->rightChild) {
std::cout << "Found right child" << std::endl;
traverse(pNode->rightChild);
}
}

int main(int argc, char ** argv) {
TreeNode node1, node2, node3;
node1.leftChild = &node2;
node1.leftChild->rightChild = &node3;
traverse(&node1);
}

The above is a variant of depth first search (adapted for binary trees).

Arrays can be a more compact way of storing a binary tree, especially if tree nodes contain only numerical values, but methods of traversing them when stored this way are not immediately obvious (require math), so I showed it with structs.

[UchihaKite]

Binary trees are fairly simple, in this case even simpler since your structure doesn't need to fulfill the search tree property. They're really just a collection of nodes where each node has at most two children.

So for example, a tree node:

Code: [Select]

struct TreeNode {
TreeNode * leftChild, * rightChild;
TreeNode() : leftChild{nullptr}, rightChild{nullptr} {}  // Change to ctor style initialization if you're not using c++11
};

Then to traverse, you could simply start at the root (the initial node), and explore it's non-null children, children of children, etc.

You might want to look into existing graph traversal algorithms, Breadth First and Depth First traversal are fairly simple.

Of course, an easy recursive solution is fine if your tree is reasonably shallow.

Code: [Select]

//...
void traverse(TreeNode * pNode) {
if (pNode->leftChild) {
std::cout << "Found left child" << std::endl;
traverse(pNode->leftChild);
}

if (pNode->rightChild) {
std::cout << "Found right child" << std::endl;
traverse(pNode->rightChild);
}
}

int main(int argc, char ** argv) {
TreeNode node1, node2, node3;
node1.leftChild = &node2;
node1.leftChild->rightChild = &node3;
traverse(&node1);
}

The above is a variant of depth first search (adapted for binary trees).

Arrays can be a more compact way of storing a binary tree, especially if tree nodes contain only numerical values, but methods of traversing them when stored this way are not immediately obvious (require math), so I showed it with structs.

Man! This is exactly what I needed! I KNEW I was over complicating this! It makes so much more sense with your example! Every other example I found was using Classes, Stacks or Queues, and I haven't learned those yet. So, having this as a foundation is going to make it a lot easier to build upon it, to more advanced methods of doing this. I'm going to play around with this when I get to work and let you know how it goes, thank you so much for your time and help Evan!

[Evan Bowman]

Every other example I found was using Classes, Stacks or Queues, and I haven't learned those yet. So, having this as a foundation is going to make it a lot easier to build upon it, to more advanced methods of doing this.

It's worth noting that while recursion is visually elegant, it does also use a stack, only it's abstracted behind function calls (each call pushes a new stack frame, which are executed in last in first out order (LIFO)). The function calls result in slightly more memory usage, but if you're not doing too much work inside the function and a reasonable number of iterations you won't see a performance difference.

When you learn more about data structures stacks/queues will make more sense, but starting with a recursive implementation can help to understand what is going on at a high level (which is why the psuedo code for many algorithms is written recursively). Converting a recursive algorithm to a stack based approach is usually fairly straightforward, after you've done it once it all makes sense (non recursive merge sort would be a fun challenge, and a useful thing to know how to do).

thank you so much for your time and help Evan!

No problem

[Evan Bowman]

Also worth considering that DFS can easily be done in parallel (manually unrolled first stage for readability, although it would be more extensible if done programmatically based on detected hardware parallelism, also this example doesn't account for all possible corner cases).

Code: [Select]

void beginParallelTraversal(TreeNode * pNode) {
if (pNode->leftChild) {
std::cout << "Found left child" << std::endl;
std::thread worker(traverse, pNode->leftChild); // Do half the work on a separate thread
if (pNode->rightChild) {
traverse(pNode->rightChild);
}
worker.join(); // Wait for the other thread to finish
} else {
traverse(pNode);
}
}


[UchihaKite]

Also worth considering that DFS can easily be done in parallel (manually unrolled first stage for readability, although it would be more extensible if done programmatically based on detected hardware parallelism, also this example doesn't account for all possible corner cases).

Code: [Select]

void beginParallelTraversal(TreeNode * pNode) {
if (pNode->leftChild) {
std::cout << "Found left child" << std::endl;
std::thread worker(traverse, pNode->leftChild); // Do half the work on a separate thread
if (pNode->rightChild) {
traverse(pNode->rightChild);
}
worker.join(); // Wait for the other thread to finish
} else {
traverse(pNode);
}
}


I've never worked with threads before, so, this would be useful to preserve how much work you put the computer through? Kind of like.......optimization? Thanks again for helping me man! You broke this down for me, and I don't know how to repay you!

[Evan Bowman]

I've never worked with threads before, so, this would be useful to preserve how much work you put the computer through? Kind of like.......optimization? Thanks again for helping me man! You broke this down for me, and I don't know how to repay you!

No problem. The computer actually would be doing the same amount or slightly more work, but it could potentially do the work faster because it has broken the problem down into smaller parts, and can do each of these smaller parts at the same time (any threads you create can be run a different non-busy processor core, if available). Creating and joining threads does incur a small performance overhead though, so this is more likely to be faster the larger the tree is. I just thought it was worth mentioning, because in the past decade processors haven't gotten that much faster, but they are more capable of running things (eg threads) in parallel, as a consequence of having more cores.

Some problems lend themselves to parallelization, while others do not. Parallelization requires steps to be independent because threads can start in any order and run at the same time. For example, traversing binary tree subtrees can be considered independent. If you were to traverse the right subtree before the left one, or do them both at the same time, it wouldn't make a difference, because there are by definition no dependencies between the two subtrees.

Here's a famous article about concurrency and why it is increasingly relevant:
http://www.gotw.ca/publications/concurrency-ddj.htm

[UchihaKite]

I've never worked with threads before, so, this would be useful to preserve how much work you put the computer through? Kind of like.......optimization? Thanks again for helping me man! You broke this down for me, and I don't know how to repay you!

No problem. The computer actually would be doing the same amount or slightly more work, but it could potentially do the work faster because it has broken the problem down into smaller parts, and can do each of these smaller parts at the same time (any threads you create can be run a different non-busy processor core, if available). Creating and joining threads does incur a small performance overhead though, so this is more likely to be faster the larger the tree is. I just thought it was worth mentioning, because in the past decade processors haven't gotten that much faster, but they are more capable of running things (eg threads) in parallel, as a consequence of having more cores.

Some problems lend themselves to parallelization, while others do not. Parallelization requires steps to be independent because threads can start in any order and run at the same time. For example, traversing binary tree subtrees can be considered independent. If you were to traverse the right subtree before the left one, or do them both at the same time, it wouldn't make a difference, because there are by definition no dependencies between the two subtrees.

Here's a famous article about concurrency and why it is increasingly relevant:
http://www.gotw.ca/publications/concurrency-ddj.htm

Oh I am defiantly going to have to look into that. That sounds really important!

Alright, so, I am checking out your code, and have a few questions and then I should be good to go.

The TreeNode struct I understand, but this part "   TreeNode() : leftChild{ nullptr }, rightChild{ nullptr } {}  // Change to ctor style initialization if you're not using c++11"

I'm assuming because my teacher has never mentioned ctor to us, that I don't have to use that style of initialization? Also, is that line of code just putting a null value into the left and right child?

As for the traverse function, that's just identifying if a left and/or right child exists? So if I wanted to do preorder traversal, I believe that prints out all the values in the left side of the tree first, and then the right, right? So, if I had, lets say, five nodes on the right side of the tree, and four on the right, would I just need a variable to keep track of the amount of nodes on each side of the tree, and then just loop the traversal by that value?

As for the main function, I've never actually put anything in the "(" ")" before, could you explain that to me?

Thanks again for your help and support man. Seriously means a lot to me! Sorry again for posting a general C++ question on these forums, I promise I will keep to SFML after this!

[Evan Bowman]

I'm assuming because my teacher has never mentioned ctor to us, that I don't have to use that style of initialization?

I guess there's a lot going on here that I should elaborate on. ctor is a common written abbreviation for 'constructor.' In C++, there are three ways of initializing a variable:

Code: [Select]

int var1 = 0; // Assignment style
int var2(0); // Constructor style
int var3{0}; // Brace style, post C++11 only. Compile your code with the flag -std=c++11 if you are using gcc or clang

If you are using C++11, it is usually recommended to initialize most things with braces, with a few exceptions. This is because among other things, braced initialization does not allow narrowing, which is a term for the loss of data that occurs when you try to initialize a variable with a larger value than will fit.

Also, is that line of code just putting a null value into the left and right child?

That's correct. The list of members following the colon after the constructor name is an initializer list. Initializer lists are the preferred way of initializing a class or struct's members. You can see from the above description of initialization methods that each member is being initialized to nullptr by braced initialization. Constructor style initialization would also work here (but the assignment operator (the equals sign) would not).

As for the traverse function, that's just identifying if a left and/or right child exists? So if I wanted to do preorder traversal, I believe that prints out all the values in the left side of the tree first, and then the right, right? So, if I had, lets say, five nodes on the right side of the tree, and four on the right, would I just need a variable to keep track of the amount of nodes on each side of the tree, and then just loop the traversal by that value?

The traverse function checks if the left or right child exists, and if it does, it calls traverse on that child. If you were to call traverse on the root node (the initial node at the top of the tree with no parents), the function would visit all of the nodes in the tree. No looping or variables needed here, this function already does a preorder traversal. Stepping through the code in a debugger might be helpful in understanding what it's doing.

As for the main function, I've never actually put anything in the "(" ")" before, could you explain that to me?

Do you mean the char ** argv? That is called an argument vector. The argument vector is an array containing strings that are passed to your program as parameters. argc is the length (number of strings) of the argument vector. argv[0] by default is your executable name. The reason these parameters exist is so that you can pass arguments to your program via the command line. Say that you saved the example code I posted as a file called example.cpp and then compiled it to an executable like this:

Code: [Select]

clang++ example.cpp -std=c++11 -o example   // clang is a compiler, you could also use gcc/icc/whatever you have
This would generate an executable in the same directory called example (I believe if you are on windows, the executable would also have an extension, .exe).

Then if you ran the executable with some parameters...

Code: [Select]

./example some parameters here  // I don't know how to run an executable on windows from the command line, but you might not need the ./
The argument vector would contain:
argv[0] = "example"
argv[1] = "some"
argv[2] = "parameters"
argv[3] = "here"
argv[4] = NULL <-- A null terminator, not included in the argument count

If you're interested in this and you're working in a unix based environment, the standard ways of processing command line arguments are either doing it yourself, or using getopt:
https://www.gnu.org/software/libc/manual/html_node/Getopt.html

Thanks again for your help and support man. Seriously means a lot to me!

No problem!

[FRex]

For C++ options parsing boost offers program options lib: http://www.boost.org/doc/libs/1_61_0/doc/html/program_options.html