Now let’s extend the concept of trees and go into detail about Binary Trees.
So in the case of a Binary Tree, each node has either zero, one or two children nodes. An empty tree is also a valid example of a binary tree.
Types of Binary Tree
1. Strict Binary Tree: Each node of the tree has exactly two children or no children.
2. Full Binary Tree: All Leaf Nodes are at the same level and each node has exactly two children
3. Complete Binary Tree: If height of the tree is h, then all the leaf nodes are at h or h-1. Also if the root node is 1 then when traversing the tree we must get a conpleted and ordered sequence of numbers from one to the number of nodes.
Properties of Binary Tree
If the height of tree is h,
- The number of nodes n in a FULL binary tree is 2ʰ⁺¹ – 1.
(from the above example: h=2; number of nodes = 2²⁺¹ -1= 7) - The number of nodes n in a COMPLETE binary tree is between 2ʰ (min) and 2ʰ⁺¹ – 1 (max).
- The number of leaf nodes in a FULL binary tree is 2ʰ.
- The number of null links in a COMPLETE binary tree of n nodes is n+1.
Note: The following coding exercises have been uploaded in JAVA.
Coding Exercise 1: Representation of Binary Tree
package tree.binarytree;
//representation of binary tree
public class Program001Binary_tree_representation {
class Tree{
Node root;
}
class Node {
int data;
Node left_child, right_child;
public Node (int d){
data=d;
left_child=right_child= null;
}
}
}
Coding Exercise 2: Creating a simple Binary Tree
package tree.binarytree;
// create simple binary tree
public class Program002Create_simple_binary_tree {
static class Node{
int data;
Node left_child, right_child;
public Node (int d){
data=d;
left_child= right_child= null;
}
}
static class Binary_tree {
Node root;
public Binary_tree(){
root=null;
}
public void add_left_node (Node parent_node, Node node){
parent_node.left_child= node;
}
public void add_right_node (Node parent_node, Node node){
parent_node.right_child= node;
}
}
public static void main (String [] args){
Binary_tree t= new Binary_tree();
Node root= new Node (1);
t.root=root;
Node node11= new Node(11);
t.add_left_node (root, node11);
Node node12= new Node(12);
t.add_right_node(root, node12);
Node node111= new Node(111);
t.add_left_node(node11, node111);
}
}
Coding Exercise 3: Inorder Traversal (Recursive method)
package tree.binarytree;
//traversal binary tree: INORDER (recursive)
public class Program003Inorder_traversal_recursive {
static class Node{
int data;
Node left_child, right_child;
public Node(int d){
data=d;
left_child= right_child= null;
}
}
static class Binary_tree{
Node root;
public Binary_tree (){
root=null;
}
public void add_left_node (Node parent_node, Node node){
parent_node.left_child= node;
}
public void add_right_node (Node parent_node, Node node){
parent_node.right_child= node;
}
public void inorder_traversal(Node node){
if(node==null){
return;
}
inorder_traversal(node.left_child);
System.out.print (node.data + " ");
inorder_traversal(node.right_child);
}
}
public static void main (String [] args){
Binary_tree t= new Binary_tree();
t.root= new Node (10);
Node node11= new Node(20);
t.add_left_node(t.root, node11);
Node node12= new Node(30);
t.add_right_node(t.root,node12);
Node node111= new Node(40);
t.add_left_node(node11, node111);
Node node112= new Node(50);
t.add_right_node(node11, node112);
t.inorder_traversal(t.root);
}
}
Coding Exercise 4: Preorder Traversal (Recursive method)
package tree.binarytree;
//Pre-order traversal (recursive)
public class Program004Preorder_traversal_recursive {
static class Node{
int data;
Node left_child, right_child;
public Node(int d){
data= d;
left_child= right_child=null;
}
}
static class Binary_tree{
Node root;
public Binary_tree (){
root= null;
}
public void add_left_node (Node parent_node, Node node){
parent_node.left_child= node;
}
public void add_right_node (Node parent_node, Node node){
parent_node.right_child=node;
}
public void preorder_traversal (Node node){
if(node==null)
return;
System.out.print(node.data+ " ");
preorder_traversal(node.left_child);
preorder_traversal(node.right_child);
}
}
public static void main (String [] args){
Binary_tree t= new Binary_tree();
t.root= new Node(10);
Node node11= new Node(20);
t.add_left_node(t.root, node11);
Node node12= new Node(30);
t.add_right_node(t.root, node12);
Node node111= new Node(40);
t.add_left_node(node11, node111);
Node node112= new Node(50);
t.add_right_node(node11, node112);
t.preorder_traversal(t.root);
}
}
Coding Exercise 5: Postorder Traversal (Recursive method)
package tree.binarytree;
//Post-order traversal (recursive)
public class Program005Postorder_traversal_recursive {
static class Node{
int data;
Node left_child, right_child;
public Node (int d){
data=d;
left_child= right_child=null;
}
}
static class Binary_tree{
Node root;
public void add_left_node (Node parent_node, Node node){
parent_node.left_child=node;
}
public void add_right_node (Node parent_node, Node node){
parent_node.right_child= node;
}
public void postorder_traversal (Node node){
if(node==null)
return;
postorder_traversal(node.left_child);
postorder_traversal(node.right_child);
System.out.print(node.data+ " ");
}
}
public static void main (String [] args){
Binary_tree t= new Binary_tree();
t.root= new Node(10);
Node node11= new Node(20);
t.add_left_node(t.root, node11);
Node node12= new Node(30);
t.add_right_node(t.root, node12);
Node node111= new Node(40);
t.add_left_node(node11, node111);
Node node112= new Node(50);
t.add_right_node(node11, node112);
t.postorder_traversal(t.root);
}
}