WikiGalaxy
WikiGalaxy💙Blue💛🌹
Personalize
Full Binary Tree
Definition:
A full binary tree is a type of binary tree in which every node other than the leaves has two children. This structure is also known as a proper binary tree or a 2-tree.
Properties of Full Binary Tree
Nodes Count:
In a full binary tree, the number of nodes is equal to 2^h - 1, where h is the height of the tree.
Leaf Nodes:
The number of leaf nodes in a full binary tree is (n + 1) / 2, where n is the total number of nodes.
Example 1: Simple Full Binary Tree
class Node {
int data;
Node left, right;
Node(int item) {
data = item;
left = right = null;
}
}
public class FullBinaryTree {
Node root;
boolean isFullBinaryTree(Node node) {
if (node == null) return true;
if (node.left == null && node.right == null) return true;
if ((node.left != null) && (node.right != null))
return isFullBinaryTree(node.left) && isFullBinaryTree(node.right);
return false;
}
public static void main(String[] args) {
FullBinaryTree tree = new FullBinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
if (tree.isFullBinaryTree(tree.root))
System.out.println("The tree is a full binary tree");
else
System.out.println("The tree is not a full binary tree");
}
}
Console Output:
The tree is a full binary tree
Example 2: Constructing a Full Binary Tree
class Node {
int data;
Node left, right;
Node(int item) {
data = item;
left = right = null;
}
}
public class FullBinaryTree {
Node root;
Node constructFullBinaryTree(int[] arr, Node node, int i) {
if (i < arr.length) {
node = new Node(arr[i]);
node.left = constructFullBinaryTree(arr, node.left, 2 * i + 1);
node.right = constructFullBinaryTree(arr, node.right, 2 * i + 2);
}
return node;
}
void inorderTraversal(Node node) {
if (node == null) return;
inorderTraversal(node.left);
System.out.print(node.data + " ");
inorderTraversal(node.right);
}
public static void main(String[] args) {
FullBinaryTree tree = new FullBinaryTree();
int[] arr = {1, 2, 3, 4, 5, 6, 7};
tree.root = tree.constructFullBinaryTree(arr, tree.root, 0);
tree.inorderTraversal(tree.root);
}
}
Console Output:
4 2 5 1 6 3 7
Example 3: Checking Fullness of a Binary Tree
class Node {
int data;
Node left, right;
Node(int item) {
data = item;
left = right = null;
}
}
public class FullBinaryTree {
Node root;
boolean isFullBinaryTree(Node node) {
if (node == null) return true;
if (node.left == null && node.right == null) return true;
if ((node.left != null) && (node.right != null))
return isFullBinaryTree(node.left) && isFullBinaryTree(node.right);
return false;
}
public static void main(String[] args) {
FullBinaryTree tree = new FullBinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
if (tree.isFullBinaryTree(tree.root))
System.out.println("The tree is a full binary tree");
else
System.out.println("The tree is not a full binary tree");
}
}
Console Output:
The tree is not a full binary tree
Example 4: Calculating Height of Full Binary Tree
class Node {
int data;
Node left, right;
Node(int item) {
data = item;
left = right = null;
}
}
public class FullBinaryTree {
Node root;
int height(Node node) {
if (node == null) return 0;
return 1 + Math.max(height(node.left), height(node.right));
}
public static void main(String[] args) {
FullBinaryTree tree = new FullBinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.println("Height of the tree is: " + tree.height(tree.root));
}
}
Console Output:
Height of the tree is: 3
Example 5: Counting Leaf Nodes in Full Binary Tree
class Node {
int data;
Node left, right;
Node(int item) {
data = item;
left = right = null;
}
}
public class FullBinaryTree {
Node root;
int countLeafNodes(Node node) {
if (node == null) return 0;
if (node.left == null && node.right == null) return 1;
return countLeafNodes(node.left) + countLeafNodes(node.right);
}
public static void main(String[] args) {
FullBinaryTree tree = new FullBinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
System.out.println("Number of leaf nodes: " + tree.countLeafNodes(tree.root));
}
}
Console Output:
Number of leaf nodes: 4
