Basics of Algorithms

by Gaurav Menghani

1. Introduction

This time we study a data structure called a Binary Tree. I assume you are familiar with basic graph theory. If not, please refer [1]. A Binary Tree is a linked data structure. Each node in a Binary Tree has a father node, (except one node, which is called the root) and thus a directed edge from a father node to the child node exists. Each node may have two children, a left and a right child. A node may have two or less children, but no more.

The left child along with its children forms the left subtree, and the right child along with its children forms the right subtree of the father node.

2. Binary Tree Terminology

There are a few commonly used terms associated with Binary Trees. You already know about father, child, left subtree and right subtree. Let us define some other terms.

Root: It is a node with no father. This implies, there is no directed edge towards the root node from some other node.

Leaf Node: It is just the opposite of a root node. A leaf node does not have any children. While there can only be one root node in a Binary Tree, there can be multiple leaf nodes. It is possible that the root node can itself be a leaf when the tree consists of just one node.

Sibling / Brother: A node's sibling or brother node is a node which has the same parent.

Ancestor and Descendant: A node N is said to be the ancestor another node n, which is said to be N's descendant, when starting from N, there is a path to reach n, following the edges. For example, if A has two children B and C. B also has two children D and E, then A is the ancestor of D and E.

Depth of a Node: Is the length of the path from the root node to that particular node.

Level: Is a set of nodes at the same depth in the tree.

Height of the Tree: Is the length of the path from the root node to the deepest node. Hence, in case of a singular node in a tree, the height would be 0.


A Binary Tree

3. Binary Tree Traversal

A binary tree can be traversed in Preorder, Inorder, Postorder or Levelorder.

In preorder, the following operations are performed, starting with the root node:

  1. Visit the node.
  2. Traverse the left subtree.
  3. Traverse the right subtree.

In inorder, the following operations are performed, starting with the root node:

  1. Traverse the left subtree.
  2. Visit the node.
  3. Traverse the right subtree.

In postorder, the following operations are performed, starting with the root node:

  1. Traverse the left subtree.
  2. Traverse the right subtree.
  3. Visit the node.

In levelorder, we travel each node on the level before going to the next level.

Preorder Traversal: F, B, A, D, C, E, G, I, H (node, left, right)

Inorder Traversal: A, B, C, D, E, F, G, H, I (left, node, right)

Postorder Traversal: A, C, E, D, B, H, I, G, F (left, right, node)

Levelorder Traversal: F, B, G, A, D, I, C, E, H

4. Implementation of Binary Trees

One obvious way to implement Binary Trees is to have a linked-node structure in the following way.

struct Node {
int info;
Node * left, * right;
//Optional father pointer
Node * father; };

It can also be represented using an array. This can be done by keeping an array of size 2d+1 - 1 if d is the maximum depth that you want for the tree. Now, the root can be assigned the location 1. Every node which is assigned the location i, has its left and right children at the locations 2i and 2i + 1 respectively.

If one or both of the children don't exist, then the locations are left empty, or are marked as empty.

Traversal of Binary Trees can be implemented as follows.

void preorder(Node *n)
{
if(n == NULL) return;
cout << (n->info) << " ";
preorder(n->left);
preorder(n->right);
}
void inorder(Node *n)
{
if(n == NULL) return;
inorder(n->left);
cout << (n->info);
inorder(n->right);
}
void postorder(Node *n)
{
if(n == NULL) return;
postorder(n->left);
postorder(n->left);
cout << (n->info);
}

I will leave the implementation of of Level-Order Traversal as an exercise.

5. Tasks for You
  • a) Implement Level-Order Traversal
  • b) Study the basics of Graph Theory from [1]
6. References
  • [1] Introduction to Algorithms (CLRS), 2nd Edition – Page 1080
  • [2] Binary Tree - http://en.wikipedia.org/wiki/Binary_tree
  • [3] Tree Traversal - http://en.wikipedia.org/wiki/Tree_traversal
Share/Save
Your rating: None Average: 5 (1 vote)