Binary Search Tree Traversals in C++

By K4Paul 0 Development , , , , , , , , , ,

So this will pretty much wrap up our short expedition into binary trees. Remember that these functions rely on my earlier posts dealing with the class and nodes.

The three types of traversals we will look at are:

  • Preorder (root, left, right)
  • Inorder (left, root, right)
  • Postorder (left, right, root)

Preorder Traversal

This type of traversal can be used to create duplicates of a tree and can be used to implement prefixes. Whatever order of values you put into a tree will be the order that preorder traversal gives you. So If I enter, 5 7 4 2 1 9 8 3 6 into a binary tree, when I use preorder traversal, I will expect to see 5 7 4 2 1 9 8 3 6.

void preorderTraversal (Node* n) {
    if (n != nullptr) { //make sure we have a value
        cout << n->data << endl; //Print out the current Node value
        preorderTraversal(n->left); //traverse down the left side
        preorderTraversal(n->right); //Once we return from the left, go down the right
    }
}

Inorder Traversal

This type of traversal will return data sorted in order. So if I entered, 5 7 4 2 1 9 8 3 6, I would expect to see 1 2 3 4 5 6 7 8 9.

  void inorderTraversal (Node* n) {
    if (n != nullptr) { //make sure we have a value
        inorderTraversal(n->left); //traverse down the left side
        cout << n->data << endl; //Print out the current Node value
        inorderTraversal(n->right); //Once we return from the print, go down the right
    }
}

Postorder Traversal

This type of traversal can be used to implement postfixes and can cleanly be used to destroy a tree with out leaving Nodes floating around corrupting memory. So if I entered, 5 7 4 2 1 9 8 3 6, I would expect to see 1 3 2 4 6 8 9 7 5

 void postorderTraversal (Node* n) {
    if (n != nullptr) { //make sure we have a value
        postorderTraversal(n->left); //traverse down the left side
        postorderTraversal(n->right); //Once we return from the left, go down the right
        cout << n->data << endl; //Print out the current Node value
    }
}

For more information on binary trees, I would checkout this article. It goes into detail on how traversals on called on the tree and gives some great visuals. I also liked this interactive visual for binary search trees in general.

Good luck!

The typical Node structure in C++

By K4Paul 0 Development , , , , , ,

The next couple of posts are going to require the use of a node object. I’ve seen people make the node way more complicating then it should be as a class. The point of a node is to hold data and be aware of it’s neighbors. All you really need is a simple struct.

In the instance of a stack or list, a node just really needs to know who’s next after them. Note in the code below, to create a node, I need some data passed in, that’s it. It’s up to the coder to set the next pointer in their code that is utilizing the node.

struct Node
{
    int data;
    Node* next;

    Node(int d){
        data = d;
        next = nullptr;
    }
};

When we start looking at linked lists and binary search trees, we might consider a struct that is aware of the nodes on both sides of it. Again, it is up to the code using the node structure to set the left and right pointers to the right node neighbors.

struct Node
{
    int data;
    Node* left;
    Node* right;

    Node(int d){
        data = d;
        left = nullptr;
        right = nullptr;
    }
};

Pretty dang simple!