[Q] Traverse a Binary Tree

[UchihaKite]

Hello C++ Community!

I'm new to to this community, looking forward to expanding my knowledge with you all, as well as helping out where/when I can.

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. Any and all help would be great!

[helios]

https://en.wikipedia.org/wiki/Tree_traversal#Types

[UchihaKite]

So, to do this, I just create a structure for the binary tree with a variable for data, two children for it........then a function for the traversal, and then in main just create the binary tree and call the functions? Is that basically it? The wiki does a good job explaining what traversal is, but not exactly how to code it o.O

[helios]

For example,

void inorder(TreeNode *n){
    if (!n)
        return;

    inorder(n->left);
    do_something(n);
    inorder(n->right);
}

[UchihaKite]

I feel as though this is one of those moments in learning how to program, that I am over-complicating something, and once I understand it I am going to face palm that I didn't understand it sooner lol

So, this I get, as for creating the Binary Tree, how do I differentiate between the Root Node and the Children? Or would the structure I create in main be the root, and the "children" would be the two structures in the structure? I feel like I am missing something @_@

[doug4]

The root node is the node that is pointed to by the rest of the program. Nothing in the tree itself identifies the ultimate root.

Internally every node thinks it is the root and has pointers to 0, 1 or 2 children. So from the node's point of view, it's only a 2-level tree.

To process the nodes of the tree in order, have the program call the function @helios gave you on the root node. The root node will call this function on its children in lines 5 and 7. The recursive nature of the tree will guarantee that all of the node are processed (with the do_something() function).

[Xerxes004]

@UchihaKite,

... how do I differentiate between the Root Node and the Children?

Each node has a pointer to each of its (potential) children, and a pointer to its parent. If a node has no parent, it's the root of the tree.

//...
if (current_node->parent == nullptr) {
     // I am the root, do something
} else {
    // I am not the root, do something else
}

Edit for clarification on another point:

Every node in the tree is the same class and looks something like this (except probably with more encapsulation).

class Node {
public:
    Node() : parent(nullptr), left_child(nullptr), right_child(nullptr), data(0)
    {}

    Node *parent;
    Node *left_child;
    Node *right_child;
    int data;
};

There's a mountain of code on the internet for how to insert into a Binary Tree, so I'd check that out also.

[cire]

Each node has a pointer to each of its (potential) children, and a pointer to its parent. If a node has no parent, it's the root of the tree.

A pointer to a parent node is extra baggage it isn't worth carrying around when you're talking about trees.

[Xerxes004]

@cire,

I'll give an example with no parent pointer, also.

#include <iostream>

class Node {
public:
    Node(int data = 0) : left_child(nullptr), right_child(nullptr), data(data)
    {}

    Node *left_child;
    Node *right_child;
    int data;
};

void btree_insert(Node *root, int val)
{
    if (root == nullptr) {
         root = new Node(val);
         return;
    }

    if (root->data > val) {
        if (root->left_child == nullptr) {
            root->left_child = new Node(val);
        } else {
            btree_insert(root->left_child, val);
        }
    } else {
        if (root->right_child == nullptr) {
            root->right_child = new Node(val);
        } else {
            btree_insert(root->right_child, val);
        }
    }
    return;
}

void preorder_walk_btree(Node *root) {
    if (root == nullptr) return;

    preorder_walk_btree(root->left_child);
    std::cout << root.data << ' ';
    preorder_walk_btree(root->right_child);
}

int main()
{
    Node *root = new Node(3);
    btree_insert(root, 1);
    btree_insert(root, 2);
    btree_insert(root, 4);
    btree_insert(root, 5);

    preorder_walk_btree(root);

    return 0;
}

The output should be 1 2 3 4 5 .

Let me know if I made any mistakes, I slapped this together pretty quickly.

[UchihaKite]

Oh Wow! Thanks for taking the time to help me out guys! I can't even begin to express how much this means to me! I was a little busy visiting my Step Mother in the Hospital, but I am going to dive back into this tomorrow and let you guys know how it goes. Seriously, thank you all!

[Little Captain]

I actually did a series of videos on Binary Search Trees:
https://www.youtube.com/channel/UCSgtee844KS4SnnL6HLexOQ

I hope you find them useful; just keep in mind I'm still updating them, so apologies in advance for some of the glitches here and there :p

I also have code and handouts, so let me know if you need those.

Joe
Concord Spark Tutoring
[e-mail]

[UchihaKite]

Oh wow! Thank you so much for that link man, I will be sure to check those out when I get a chance :D

I am curious though, is their a huge difference between a Binary Tree and a Binary Search Tree? When my teacher gave me stuff to study over my Summer Break, he told me to look into Binary Trees, but didn't say anything about Binary Search Trees

[helios]

A binary tree is a directed acyclic graph where every node points to at most two other nodes and is pointer to by at most one node.
A BST is a special case of such a tree, where every node has some data associated with it and it's positioned within the tree to allow for efficient lookup. BSTs are generally more complex than binary trees, because operations with them must maintain some invariants to ensure that lookup continues to be efficient.

[cire]

Xerxes004 wrote:

Let me know if I made any mistakes, I slapped this together pretty quickly.

Memory leak if you feed btree_insert a null pointer.

[UchihaKite]

Xerxes004 wrote:

std::cout << root.data << ' ';

The only thing I had to change to make it run is "root.data" to "root->data". I need notice the Memory Leak that Cire mentioned. Though, because I am still extremely new to Classes and Binary Trees, not entire sure why it happens or how to fix it. I am still a little noob coder lol

Still checking out your code, is actually giving me a better understanding of Classes and Binary Trees overall! Though if I am going to be honest, it is the insert function that is confusing me the most. It seems to me, that you first look at the data variable in the node, and it its larger than the data you're trying to put into it, then it looks at the left child of the node and if its null, you make a new node, and put the data into it. Else, you're putting it in the root nodes left child? But if the root data is less than the value, then you run the same process but to the right child instead?

Oh, and Helios, so, for now should I just stick to trying to figure out regular binary trees before I tackle that?

[helios]

I should say so, yes.