Binary Tree

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.

Strict Binary Tree

2. Full Binary Tree: All Leaf Nodes are at the same level and each node has exactly two children

Full Binary Tree


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.

Complete Binary Tree

Properties of Binary Tree

If the height of tree is h,

  1. 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)
  2. The number of nodes n in a COMPLETE binary tree is between 2ʰ (min) and 2ʰ⁺¹ – 1 (max).
  3. The number of leaf nodes in a FULL binary tree is 2ʰ.
  4. 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);
	}

}

Leave a Reply

PHP JS HTML CSS BASH PYTHON CODE

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this:
search previous next tag category expand menu location phone mail time cart zoom edit close