Extended Binary Tree
A form of binary tree known as an extended binary tree replaces all of the original tree's null subtrees with special nodes known as external nodes, while the remaining nodes are known as internal nodes.
In the extended binary tree, it is fixed that every internal node has two children. And it is also fixed that every external node is a leaf node. The result of the constructed binary tree is generally a Complete binary tree.
In the above diagram, the circle denotes the Internal nodes whereas the box denotes the external nodes.
Extended Binary Trees are useful for the algebraic expression representation.
External Binary Tree Properties:
- The special nodes are external nodes, whereas the nodes from the original tree are internal nodes.
- Internal nodes are non-leaf nodes, whereas all external nodes are leaf nodes.
- Every external node is a leaf, and every internal node has precisely two children. It gives the complete binary tree as the output.
Dealing with random values in the actual world is frequently impossible; the likelihood that you are dealing with non-random variables (such as sequential) results in largely skew trees, which brings us to the worst situation. So, using rotations, we balance the height of the binary tree.
Let’s see an example of making the extended binary tree.
Initially all the external nodes are marked as -1.
The JAVA implementation of constructing the extended binary tree.
// A JAVA Program for the construction of an Extended Binary Tree.
class ExtendedBinaryTreeDemo
{
// A Node is created for the binary tree.
static class Node
{
int data;
Node left, right;
};
// This method creates a new node in the binary tree.
static Node newNode (int data)
{
Node temp_node = new Node ();
Temp_node.data = data;
Temp_node.left = temp_node.right = null;
return (temp_node);
}
// method which demonstrates the Inorder traversal of a binary tree.
static void inordertraverse (Node root)
{
//Checking if the root node is empty or not.
if (root != null)
{
inordertraverse(root.left);
System.out.print(root.data + " ");
inordertraverse(root.right);
}
else
{
//If the given node is NULL, then external nodes are made.
// The external nodes are indicated with -1.
root = newNode(-1);
System.out.print(root.data + " ");
}
}
// The Driver program code for executing the above functions.
public static void main (String args [])
{
Node root = newNode (10);
root.left = newNode (20);
root.right = newNode (30);
root.left.left = newNode (50);
root.right.right = newNode (40);
inordertraverse (root);
}
}
OUTPUT:
-1 50 -1 2 -1 10 -1 30 -1 40 -1
The C++ implementation of constructing the extended binary tree.
#include <bits/stdc++.h>
using namespace std;
// A Node is created for the binary tree.
struct Node {
int data;
struct Node *left, *right;
};
// This method creates a new node in the binary tree.
// This type of method is known as utility function.
Node* newNode (int data)
{
Node* temp_Node = new Node;
Temp_Node->data = data;
Temp_Node->left = temp_Node->right = NULL;
return (temp_Node);
}
// method which demonstrates the Inorder traversal of a binary tree.
void inordertraverse (Node* root)
{
if (root != NULL) {
inordertraverse(root->left);
cout << root->data << " ";
inordertraverse(root->right);
}
else {
// Initialize the external nodes with -1 (Marker value).
root = newNode(-1);
cout << root->data << " ";
}
}
// The Driver program code for executing the above functions.
int main ()
{
Node* root = newNode (10);
root->left = newNode (20);
root->right = newNode (30);
root->left->left = newNode (50);
root->right->right = newNode (40);
inordertraverse(root);
return 0;
}
OUTPUT:
-1 50 -1 2 -1 10 -1 30 -1 40 -1
The Python implementation of constructing the extended binary tree.
# A program for constructing an Extended binary tree.
# A node for the given binary tree.
class Node:
def __init__(self):
self.data= -1
self.left=self.right=None
# The below fumction helps in creating a new node.
# This function is also called as utility function.
def newNode (data):
temp_node = Node ()
temp_node.data = data
temp_node.left = temp_node.right = None
return temp_node# This Function produces the inorder traversal for the given binary tree.
def inordertraverse (root):
if (root != None):
inordertraverse (root.left)
print (root.data, end=" ")
inordertraverse (root.right)
else:
# Initializing the external node with -1.
root = newNode (-1)
print (root.data, end=" ")
# Driver code for the execution of the above functions.
if __name__ == '__main__':
root = newNode (10)
root.left = newNode (20)
root.right = newNode (30)
root.left.left = newNode (50)
root.right.right = newNode (40)
inordertraverse (root)
print ()OUTPUT:
-1 50 -1 2 -1 10 -1 30 -1 40 -1
To construct the Extended Binary Tree, a time complexity of O(N) and space complexity of O(N) is required.
Extended Binary Tree Applications:
- We can calculate the weighted path length easily. It calculates the total path length in case of a weighted tree.
The total path length can be easily calculated from the given extended binary tree.
Total Path Length is
P = 9*3 + 10*3 + 8*2 + 6*2 + 9*3 + 11*3
P = 145
It is much simpler to determine the overall path length of a tree with the supplied weights in this case since the entire weights' sum has already been determined and is kept in the external nodes. A network's routing tables can be updated using the same method.
- Extended Binary tree is useful in converting the binary tree into a Complete Binary Tree. Even after all external nodes have been deleted, the tree in the example above is not a full binary tree. External nodes are added to any tree to make it a full tree. Each binary tree may be described as heap if extra nodes are added to it since heap is a fantastic illustration of a complete binary tree.