Application of a Binary Tree

The binary tree are applicable in the below mentioned fields:
- Used in the compilers of high-level programming languages for intermediate representation
- Used as a searching technique
- Used in databases for storing data
- To solve arithmetic expressions

Exercise-Binary Tree Construction

Given data items: 17, 6, 3, 9 ,12, 15, 1, 18, 22
The resulting binary tree is:

What is a Binary Tree?

A binary tree embodies a finite set of data items that is either empty or partitioned into three disjoint subsets. The first part contains a single data item referred to as the root of the binary tree, other two data items are left and right subtrees. These data items is referred to as nodes of the binary tree.

From this figure we can portray the following:
A - Root node of the binary tree
A - Parent node of the nodes B & C
B & C - Children nodes of A and these nodes are in a level one more than the root node A
C - Right child node of A
B - Left child node of A
D & E - These node are without a child, so they are referred to as leafs or external nodes
B & C - These nodes have a child each, so they are referred to as internal nodes

Depth of this binary tree - The longest path from the root node A to any leaf node, for example D node. Therefore, the depth of this binary tree is two.
Indegree of a node - The number of edges merging into a node. For example, indegree of the node B is one i.e. one edge merges.
Outdegree of a node - The number of edges coming out from a node. For example, outdegree of the node A is two i.e. two edges comes out of this root node.

Concerning the binary trees, do refer to the following blog entries:
- Exercise-Binary Tree Construction
- Application of a Binary Tree

What is a Complete Binary Tree?

A strictly binary tree of depth 'd' in which all the leaves are at level 'd' i.e. there is non empty left or right subtrees and leaves are populated at the same level.
In a complete binary tree all the internal nodes have equal degree, which means that one node at the root level, two nodes at level 2, four nodes at level 3, eight nodes at level 4, etc, which the below figure represents:

What is Heap Sort?

Heap Sort is a sorting algorithm that sorts data items into ascending or descending order, which comes under the category of comparison-based sorting and a family member of the selection sort. As the name suggests, this sorting algorithm use the concept of a heap structure that is based on the binary tree, which works as follows:
1. Using an array and the given data items, build a heap i.e. either a min heap or max heap as per requested sorting order
2. From the heap, remove the root node's data items and insert it to an separate array
3. Wait until the heap orders is restored, which will produces a new root node. Now, recursively repeat the above procedure '2' until there is no data items left in the heap.

Click the link -> Heap Sort for the pseudocode

What is a Search Tree?

Search Tree is based on the Binary Search Tree (BST) in which each node has a left and right child. All the childern to the left of the node with key values have smaller than the root node, all the childern to the right of the node have values greater than the root node.

For example, a sequence of numbers like 34, 54, 66, 12, 43, 28, 83 in a Search Tree is represented as follows:
Now, in order to search a given value i.e. 43 in this constructed tree. Start at the root node to search 43, this is done by making comparsion with the node value. When the value compared with the search value results to be greater, then move to the right node or vice versa. In this case, we move right because 43 is greater than 34.

From, now on just repeat the comparison procedure until you find a matching value or end the comparing procedure at a leaf node.

Continuing our search, we now compare 54 with 43, we notice 43 is less than 54, hence we move left and compare the leaf nodes value i.e. 43 with the search value i.e. 43, therefore 43 equals to 43... match found!

Advantages of such a search tree: Insertion, Removal, Search are performed efficiently. In particularly, when considering the searching iteration we reduce the number of elements to search by one-half.

Binary tree traversal: Preorder, Inorder, and Postorder

In order to illustrate few of the binary tree traversals, let us consider the below binary tree:












Preorder traversal: To traverse a binary tree in Preorder, following operations are carried-out (i) Visit the root, (ii) Traverse the left subtree, and (iii) Traverse the right subtree.
Therefore, the Preorder traversal of the above tree will outputs:
7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10

Inorder traversal: To traverse a binary tree in Inorder, following operations are carried-out (i) Traverse the left most subtree starting at the left external node, (ii) Visit the root, and (iii) Traverse the right subtree starting at the left external node.
Therefore, the Inorder traversal of the above tree will outputs:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Postorder traversal: To traverse a binary tree in Postorder, following operations are carried-out (i) Traverse all the left external nodes starting with the left most subtree which is then followed by bubble-up all the internal nodes, (ii) Traverse the right subtree starting at the left external node which is then followed by bubble-up all the internal nodes, and (iii) Visit the root.
Therefore, the Postorder traversal of the above tree will outputs:
0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7