A binary tree is considered a 2-tree or an extended binary tree in data structure if each node has either 0 or 2 children. In such a case the nodes with 2 children are called internal nodes and the nodes with zero children are called external nodes. Sometimes the nodes are distinguished in diagrams by using a circle to represent internal nodes and a square to represent external nodes.
The term extended binary tree comes from the following operation, consider any binary tree that tree is converted into a new tree by replacing each empty subtree with a new node. A new tree will be considered as an extended tree. Further nodes in the original tree are now the internal nodes in the extended tree and the nodes are the external nodes in the extended tree.
Application of extended binary tree:
An important application of an extended binary tree is the tree corresponding to any algebraic expression which uses only binary operations in which operands will act as external nodes and operators will be internal nodes.
For Example 1) A + B * C
2) (A-B)/ ((c*d)+e)
Path Length
The concept of path length is applied to an extended binary tree the nodes with zero children are called external nodes and the nodes with two children are called internal nodes. Internal nodes are denoted by circles and the external nodes are denoted by squares. In an extended tree, the number (NE) of external nodes is one more than the number (NI) of internal nodes that is NE = NI+1.
We define the external path length (LE) of the extended binary tree to be the sum of all path lengths summed over each path from the root of the tree to an external node. The internal path length of the tree is defined using internal nodes instead of external nodes.
LE = LI +2n where n is the internal nodes of the binary tree
Since the first one is a complete binary tree so, it has a minimum path length.
Discover more from easytechnotes
Subscribe to get the latest posts sent to your email.