Copyright

Binary Trees: Applications & Implementation

Instructor: Joelle Mumley
Binary trees are types of data structures that have many uses. They can be applied in search, 3D video games, high-bandwidth network routers, some peer-to-peer programs and cryptography. In this lesson, we'll explore the basics and application of binary trees. We will also implement a binary tree example.

What Is a Binary Tree?

A normal tree has no restrictions on the number of children each node can have. Binary trees, on the other hand, can have at most two children for each parent. Every node contains a 'left' reference, a 'right' reference, and a data element. The topmost node in the tree is called the root node. Nodes with children are parent nodes, and the child nodes contain references to their parents. A node with no children is called a leaf node. Thus, each node in a binary tree can have either 0, 1 or 2 children as shown in Figure 1.


Figure 1: Binary Tree Example
Binary Tree Example


Types & Implementation

There are three different types of binary trees that will be discussed in this lesson:

  • Full binary tree: Every node other than leaf nodes has 2 child nodes.
  • Complete binary tree: All levels are filled except possibly the last one, and all nodes are filled in as far left as possible.
  • Perfect binary tree: All nodes have two children and all leaves are at the same level.


Figure 2: Types of Binary Trees
Types of Binary Trees


Binary trees can be implemented using pointers. A tree is represented by a pointer to the top-most node in the tree. If the tree is empty, then the value of the root is NULL.

A binary tree has the following parts:

  1. Data
  2. Pointer to the left child
  3. Pointer to the right child

We can represent a tree node structure in the C programming language. Consider an example that consists of a node with integer data. We can then add to this to create a simple binary tree with four nodes:

struct node
{
 int data;
  struct node *left;
  struct node *right;
};
/* newNode() allocates a new node with the given data and NULL left and
right pointers. */
 struct node* newNode(int data)
{
// Allocate memory for new node
 struct node* node = (struct node*)malloc(sizeof(struct node));
// Assign data to this node
  node->data = data;
// Initialize left and right children as NULL
  node->left = NULL;
  node->right = NULL;
 return(node);
}
int main()
{
/*create root*/
 struct node *root = newNode(1);
  root->left = newNode(2);
  root->right = newNode(3);
  root->left->left = newNode(4);
 getchar();
return 0;
}

The result of the code is:


Figure 3: Simple Binary Tree with Four Nodes
null


Traversing Binary Trees

Any node in a binary tree data structure can be reached by starting at the root node and repeatedly following references to either the left or the right child. The degree, or number of children a node has, is a maximum of two.

The process for visiting all the nodes is called a traversal, and consists of three types: 1) preorder, 2) postorder and 3) inorder.


Figure 4: Tree for Transversal Examples
Traversal Example


In a preorder transversal, we visit any given node before we visit its children. Here, we begin at the root (node 7) and end at the right-most node (node 10). The traversal sequence, in this case, would be:

  • 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10

In a postorder traversal, we visit each node only after we visit its children (and their subtrees). We begin with the left-most node (node 0) and end with the root (node 7). The traversal sequence, in this case, would be:

  • 0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7

In an inorder traversal, we first visit the left child (including its entire subtree), then visit the parent node and finally visit the right child (including its entire subtree). Here, we begin at the left-most node (node 0) and end at the right-most node (node 10). The traversal sequence, in this case, would be:

  • 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Note that the binary search tree makes use of the inorder traversal method to print all nodes in ascending order of value.

Binary Search Tree

A binary search tree is essentially a binary tree with respect to child node counts, but has one crucial difference: There is a relative ordering with how the nodes are organized. In a binary search tree, all the nodes to the left of a given node have values less the value of that node, and all the nodes to the right of a given node have values greater than the value of that node.


Figure 5: Binary Search Tree
null


Binary search trees are useful in situations where data is continuously changing and fast searching is needed.

To unlock this lesson you must be a Study.com Member.
Create your account

Register to view this lesson

Are you a student or a teacher?

Unlock Your Education

See for yourself why 30 million people use Study.com

Become a Study.com member and start learning now.
Become a Member  Back
What teachers are saying about Study.com
Try it risk-free for 30 days

Earning College Credit

Did you know… We have over 200 college courses that prepare you to earn credit by exam that is accepted by over 1,500 colleges and universities. You can test out of the first two years of college and save thousands off your degree. Anyone can earn credit-by-exam regardless of age or education level.

To learn more, visit our Earning Credit Page

Transferring credit to the school of your choice

Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.

Create an account to start this course today
Try it risk-free for 30 days!
Create an account
Support