## Algorithm

A full binary tree is a type of binary tree in which every node other than the leaves has two children, and all leaf nodes are at the same level. In other words, a binary tree is considered "full" if every node has either 0 or 2 children. No node in a full binary tree has only one child.

Here are some characteristics of a full binary tree:

1. Nodes and Levels:

• Every level of the tree is completely filled, except possibly for the last level.
• If the last level is not completely filled, the nodes are filled from left to right.
2. Number of Nodes:

• If the height of the tree is h, the number of nodes in a full binary tree is 2h+1−1.
• Each level of the tree doubles the number of nodes in the previous level.
3. Height and Depth:

• The height of a full binary tree with n nodes is ⌊log⁡2(n+1)⌋.
• The depth of the deepest node is the height of the tree.
4. Examples:

• Here's an example of a full binary tree with height h=2:

markdown
    1
/ \
2   3
/ \
4   5
• In this example, every non-leaf node has exactly two children, and all leaf nodes are at the same level.

## Code Examples

### #1 Full Binary Tree implement in Python

Code - Python Programming

class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None

class FullBinaryTree:
def __init__(self):
self.root = None

def insert(self, key):
if not self.root:
self.root = Node(key)
else:
self._insert(key, self.root)

def _insert(self, key, current_node):
if key < current_node.key:
if current_node.left:
self._insert(key, current_node.left)
else:
current_node.left = Node(key)
else:
if current_node.right:
self._insert(key, current_node.right)
else:
current_node.right = Node(key)

def is_full(self):
return self._is_full(self.root)

def _is_full(self, node):
if not node:
return True
if not node.left and not node.right:
return True
if node.left and node.right:
return self._is_full(node.left) and self._is_full(node.right)
return False

# Example usage:
tree = FullBinaryTree()
tree.insert(5)
tree.insert(3)
tree.insert(7)
tree.insert(2)
tree.insert(4)
tree.insert(6)
tree.insert(8)

print("Is the tree full?", tree.is_full())

Copy The Code &

### #2 Full Binary Tree implement in Java

Code - Java Programming

class Node {
int data;
Node left, right;

public Node(int item) {
data = item;
left = right = null;
}
}

public class FullBinaryTree {
Node root;

// Method to insert a new node
private Node insert(Node root, int data) {
if (root == null) {
return new Node(data);
}

if (data  <  root.data) {
root.left = insert(root.left, data);
} else if (data > root.data) {
root.right = insert(root.right, data);
}

return root;
}

// Method to check if the binary tree is full
private boolean isFull(Node root) {
if (root == null) {
return true;
}

// If a node has only one child, it's not a full binary tree
if ((root.left == null && root.right != null) || (root.left != null && root.right == null)) {
return false;
}

// Recursively check the left and right subtrees
return isFull(root.left) && isFull(root.right);
}

// Wrapper method to check if the binary tree is full
public boolean isFullBinaryTree() {
return isFull(root);
}

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()) {
System.out.println("The binary tree is full.");
} else {
System.out.println("The binary tree is not full.");
}
}
}

Copy The Code &

### #3 Full Binary Tree implement in C

Code - C Programming

#include <stdio.h>
#include <stdlib.h>

// Define the structure for a tree node
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;

// Function to create a new node with the given data
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}

// Function to insert a new node into the tree
Node* insert(Node* root, int data) {
if (root == NULL) {
return createNode(data);
}

// Insert in left subtree if data is less than the current node
if (data  <  root->data) {
root->left = insert(root->left, data);
}
// Insert in right subtree if data is greater than or equal to the current node
else {
root->right = insert(root->right, data);
}

return root;
}

// Function to print the tree in-order
void inOrderTraversal(Node* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}

// Function to free the memory allocated for the tree nodes
void freeTree(Node* root) {
if (root != NULL) {
freeTree(root->left);
freeTree(root->right);
free(root);
}
}

int main() {
Node* root = NULL;

// Insert some nodes into the tree
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);

// Print the tree in-order
printf("In-order traversal: ");
inOrderTraversal(root);
printf("\n");

// Free the memory allocated for the tree nodes
freeTree(root);

return 0;
}

Copy The Code &