Nodes in a Linked List and Binary Trees

A node… a singular entity found drifting in space. So you throw out the tractor beam and bring it aboard. Safe right? After all, what can a simple node do? Little did you realize that the node, when combined with others, could form an organized group with a singular purpose… TO ASSIMILATE YOU!

Ok, perhaps I am going a bit overboard with the whole Borg analogy. But when you think about it, the Borg is like a collection of nodes who work together in unison to create a collective structure that is heavily organized and very powerful. Billions of nodes and I could easily find Seven of Nine (from Voyager) by going to Unimatrix One where she is number seven of a branch containing nine nodes. How did we find her so fast? We cover the ideas of nodes, their place in a linked list and how they form a binary tree on this entry of the Programmer’s Underground!

A node is a simple structure. But it is a bit limiting to say that it is only a structure. Classes are also a structure as well and you could easily build a class to be a node too. Nodes don’t have to be simple, but they do usually have a pointer to another one of its kind to form a link, forming a chain. You usually see nodes implemented as a simple structure consisting of a couple parts..

1) The Node’s Value – This is also called the payload in some documents you might see. It is what the node represents. In many examples you see it represent something as simple as an integer or a string. But it could be a whole object with methods, private member variables, and wrap up access to subsystems or files. In our example below, like many other examples, we will see this as the variable “value” and it will contain an integer. Just keep in mind though that it could represent much more.

2) A pointer variable to another structure of the same type. In our example, our node will point to two objects, both of type node (we will see this in a second). It is a node which points to another node. Hopefully this concept doesn’t confuse you. Think of it like people. You know of a particular friend. You are both of type “person” and when asked, you could point to your friend who is also a person. If you were to go to your friend and ask them, they could point to a friend of theirs who is also a person. See the chain effect here?

Martyr2 points at Skyhawk133 who points at Axel who points at Sloth etc etc etc.

This chaining of nodes is a linked list. Another way to think of this is if we all stood in a single file line. The person in front of me would be Skyhawk and the one in front of him would be Axel and in front of him sloth. This would be a single linked list. Now if I knew who was behind me as well as who was in front of me, that would be a double linked list. I would have a pointer to who is next in line and who was previous to me in line.

Now we have the definition of a node and how it plays out in a linked list. So what the hell is thing about binary trees and nodes taking over humanity? Glad you asked.

Imagine we have a node which points to two others. It would have a structure similar to this…

// Build a classic node structure
// It contains its value and pointers to left and right nodes
struct node {
	int value;
	node *left;
	node *right;
};

Our node points at two other nodes which it knows as left and right. The left pointer would be for nodes which have a value less than the current node. The right would be for nodes which are greater than the current node. If each node has these two pointers, you can see it would create something that may represent a pyramid. Each node would point to two others which would point to two more and exponentially grow. Each time we go through one of the left or right pointers we move down a “level”. The best way to see this is with a graphic.

The value 4 is our lonely node which was floating in space. He points to two other nodes, one for his left and one for his right. On his left is the value 2, which is less than 4. On his right is the value 8 which is greater than 4. The node number 4 is on level 0 and numbers 2 and 8 are one down from 4, so they are on level 1.

If we go to node 8, it too has two pointers, on its left 6 and on rights right 9. Nodes 6 and 9 are on level 2. If we go to node 6 we see it has nothing on its left and a node on its right.. node 7. Node 7 is on level 3. So we can say that this tree of nodes has a depth of 3 and since there are 7 nodes in the entire tree, we can say it has a size of 7. Each node which has no child nodes (nodes below it like node 1) are said to be leaf nodes. Node 4 is a root node, node 2, 8, 6 are branches and nodes 1, 7, and 9 are leaf nodes. See the analogy to a tree? Now if we started mid way through the tree on node 8, we could say node 8 is our root. But don’t let that part confuse you. Root is only relative to where you start.

As you look at the tree you will see that each value on the left of a node is less than its parent node and each one on the right is greater than its parent. For instance 7 is greater than 6 so it is on the right of its parent node 6. Not all branches have to be filled. Some can have both pointers empty and some can have one empty. Node 1 has both empty while node 2 has its right node empty.

So how does this tree help us? Well, it helps us make quick decisions on finding a node out of a huge number of values. Lets say we wanted to find the value 1. We would start at the top of the tree and do simple decision making. Is 1 equal to, greater than, or less than 4? It is less than, so we go down into the left branch, eliminating everything on the right branches of 4. Thus eliminating nodes 8, 6, 9 and 7. Now we are on node 2. Is 1 equal to, greater than ,or less than 2? It is less than, so we go down into the left node. Eliminating everything that would have been on right node of 2 (which again could have been tons of values). Now we are on node 1. Is 1 equal to, greater than or less than 1? It is equal to, we have found our node. So we found our node in essentially three tests.

This process of moving down through the nodes is known as “traversing” the tree. If the nodes knew about its parent as well (like we knew the person previous to us in the single file line) we could traverse up the tree as well. Go from node 1 up to its parent (node 2) and up to its parent (node 4).

Now imagine this tree had hundreds of thousands or even millions of nodes. Each decision we would make could cut off hundreds of thousands of values each time. If we were looking for 6, we would start at 4, cut off values 2 and 1 with our first choice, cut off 9 with our second choice and found node 6. Easy right?

Ok, so lets dive into some C++!

#include <iostream>
using namespace std;

// Build a classic node structure
// It contains its value and pointers to left and right nodes
struct node {
	int value;
	node *left;
	node *right;
};

// Declarations for inserting nodes and traversing nodes
void InsertNode(node *&, node *);
void TraverseNodes(node *&);

int main()
{
	// Create an array of numbers to build into a tree
	int a[7] = {4,2,8,9,1,6,7};

	// Our root node start
	node *b = NULL;

	// Loop through the array, create a new node, set its value from
	// the array and pass it to InsertNode to put in our tree.
	for (int i = 0; i < 7; i++) {
		node *newnode = new node();
		newnode->value = a[i];
		InsertNode(b,newnode);
	}

	// Now lets traverse the tree and when we hit the bottom
	// go back up the tree deleting our nodes.
	TraverseNodes(b);

	return(0);
}

// Inserts a node into the tree in the proper spot based on current location
void InsertNode(node *&currentNode, node *newNode) {
	// If our root node is empty, place our new node there.
	if (currentNode == NULL) {
	   currentNode = newNode;
	}

	// Else if the new node is less than our root, nagivate to left branch
	// by recursively calling the function and using the left branch as our root.
	else if (newNode->value < currentNode->value) {
	   InsertNode(currentNode->left, newNode);
	}

	// If the value is equal to or greater than the root, navigate to right
	// branch again by recursively calling the function and giving it the right
	// branch as our root node.
	else {
	   InsertNode(currentNode->right, newNode);
	}
}

// This moves down through the tree branches until it hits bottom. It then
// goes back up the tree deleting nodes as it goes.

void TraverseNodes(node *&currentNode) {
	// If we have a left node, navigate down it by resursive call.
	cout << "Current node is: " << currentNode->value << endl;
	if (currentNode->left != NULL) {
		TraverseNodes(currentNode->left);
	}
	
	// After we come back from left branch, check to see if we have right branch.
	// Navigate down the right half of the node.
	if (currentNode->right != NULL) {
		TraverseNodes(currentNode->right);
	}
	
	// After we have navigated through both left and right sub branches,
	// delete the current root node.
	delete(currentNode);
}

This program contains three main parts. The first part is the definition of a structure called “node”. Again this could also have been a class pointing to other classes of the same type. The node has its left and right pointers defined as well as the nodes actual value. This value again could be a simple integer or could be a very complex value.

The second part is a function used for inserting nodes. It traverses down the tree checking node values and determining if it should go down the left or right branch and whether or not it should place the newNode on the left or right of the current node.

So if we wanted to place the node 3, it would start at 4, say 3 is less than 4, go down the left node to node 2, check if 3 is greater than or less than 2 and since it is greater than 2, it would place the node on the right of node 2.

The third part is the TraverseNodes() function which simply go down through the nodes and when it reaches the bottom nodes, where it can’t go further, it deletes the node. It then moves up to parent and down into the other branch. Once it has deleted all child nodes, it moves up to the parent and deletes the parent (which is a child of another node). So we start deleting nodes from the bottom up until we reach, and delete, the last node… node 4.

Notice that both functions are calling themselves recursively, passing the right or left node to itself which then uses that to move down into the next set of branches. When they reach the bottom or placed the node, it returns back to itself and either goes down into the other half of the branches or back up to its parent.

Binary trees are great for quick searching since it can quickly eliminate values during the search. This idea is behind the many binary search functions you see in programming. They both work on the same principle. It is also the reason why binary searches require the values to be sorted so that when you make a choice, it eliminates all the values higher or lower than the value you are searching for.

In conclusion you see how to make a node, how the nodes can point at one another to form chains which is at the heart of a linked list and how those chains can be put together into a tree structure known as a binary tree (binary meaning two as in two branches). You also learned the parts of a binary tree including root nodes, branches and leaf nodes.

I hope you enjoyed this entry and yes, I will lay off the star trek for awhile. Thanks! 🙂