Table of Contents
hide
Introduction
- Binary Tree is considered as the mother tree because most of the trees are derived from this tree.
Definition
- A binary tree is a type of tree in which no node can have more than two children is called a binary tree.
- A tree is a finite set of nodes storing elements such that the nodes have a parent-child relationship that satisfies the binary tree properties.
- A binary tree is a finite set of nodes that is either empty or consists of a root node and two disjoint binary trees, called the left and right subtrees of the root.
Properties of a Binary Tree
- Each internal node in a binary has zero or single or at most two children.
- Binary trees are not a subcategory of trees. In particular, we allow empty binary trees but not empty trees.
- The children of a node are in an ordered pair (left and right) form.
- The children of an internal node in a binary tree may be left child and right child.
- A binary tree can have at most 2n nodes at level n.
- A binary tree of height n can have as many as 2n+1-1 nodes, and as few as n+1.
- A binary tree is said to be full if every level, except possibly the last, has as many nodes as possible.
Specialised Binary Tree
Proper/Plane/Full Binary Tree :
- It is a special type of binary tree in which each internal node of a binary tree has exactly 2 children, it is called a proper binary tree.
Complete Binary Tree :
- A specialized binary tree in which every level, except the last level(leaf node), is completely filled, and all nodes in the last level are as far left as possible.
Perfect Binary Tree :
- A perfect binary tree is a type of binary tree in which all internal nodes must have two children and all the leaves/leaf nodes have the same depth or at the same level.
- Thus, a perfect tree is therefore always a complete tree but a complete tree is not necessarily a perfect tree.
Balanced Binary Tree :
- A balanced binary tree is also a type of binary tree in which the left and right subtrees of every node differ in height by not more than one.
Threaded Binary Tree :
- A threaded binary tree is a modified form of a binary tree where each node has additional links or pointers that facilitate traversals without using recursion or stacks.
- The primary goal of threading is to optimize the process of moving between nodes during traversals like in-order traversal.
- Threaded binary trees introduce threads/pointers that act as shortcuts through the tree, allowing us to move between nodes efficiently without the need for additional data structures(stacks).
- Threaded binary trees can have both threaded and non-threaded nodes. Threaded nodes point to other nodes using threads, while non-threaded nodes have traditional left and right child pointers.
- Threaded binary trees can be useful when memory efficiency is crucial, or when we need to optimize traversals without using additional data structures.
- Threaded binary trees show complexity during insertion and deletion operations because they need the proper maintenance of threads.
Full Binary Tree :
- A binary tree in which all nodes have either zero or two child nodes.
- In a Full binary tree, there is no node that has a single child node.
Degenerate/Pathological Binary Tree :
- A degenerate tree is a special case of the binary tree where each parent node has only one associated child node either are left or right child.
- This tree simply behaves like a linked list data structure in tree form.
Binary Tree Implementation/Representation
Binary tree may be implemented as –
(i) As an Array. (ii) As an Linked List
(i) As an Array based Implementation :
- To implement a binary tree as an simple array, we must linearize the tree, but in such a way that the tree structure is not lost i.e. we must map nodes to array elements, but in such a way that for any given node, we can determine whether or not its subtrees are empty, and if not, we can locate their roots.
- In the array, the root of the binary tree is stored in array element with index 0. If a node is stored in array element n, its left child is stored in element 2n+1, and its right child in element 2n+2. An empty subtree can be denoted by an array element containing the null value.
- One disadvantage of this representation is that space must be allocated for all possible nodes at a given level, whether the level is fully populated/filled or not.
(ii) As a Linked List Implementation :
Operation in Binary Tree
There are following types of operations associated with binary tree –
- Creation of Binary Tree
- Traversal/Printing in Binary Tree
- Insertion of node in Binary Tree
- Deletion of node from Binary Tree
- Searching of individual value from the nodes of Binary Tree
Binary Tree Traversal
- A traversal is a systematic way to visit & print all the data from all nodes of a binary tree.
- Traversing the empty binary tree is trivial i.e. there is nothing to do.
- Binary tree traversal are of 4 types –
- Pre-Order Traversal.
- In-order Traversal.
- Post-order Traversal.
- Level order/Breadth first Traversal.
(a) Pre-order Traversal
- When the binary tree is not empty, we get different linearizations depending on the order in which we access the three components of the binary tree i.e. root, left and right subtrees.
- A preorder traversal of a non-empty binary tree are –
• visits the root first, then
• preorder traverses the left subtree, then
• preorder traverses the right subtree.
Here, we traverse the nodes finally in the pre-order is = A, B, D, E, C, F, G. In this tree, A is the root node B, D, E is the left subtree traversed in preorder and C, F, G is the right subtree in preorder.
(b) In-order Traversal
- When the binary tree is not empty, we get different linearizations depending on the order in which we access the three components of the binary tree i.e. left subtrees, root and right subtrees.
- A Inorder traversal of a non-empty binary tree are –
• inorder traverses the left subtree, then
• visits the root in the middle, then
• inorder traverses the right subtree. - An inorder traversal path of the above binary tree visits nodes in the order D, B, E, A, C, G, F.
(c) Post-order Traversal
- When the binary tree is not empty, we get different linearizations depending on the order in which we access the three components of the binary tree i.e. left subtrees, right subtrees and root.
- A postorder traversal of a non-empty binary tree –
• postorder traverses the left subtree, then
• postorder traverses the right subtree, then
• visits the root in the last.
- The above binary tree traversed in post order yields the path order = D, E, B, G, F, C, A.
(c) Level order Traversal
- A breadth-first or level-order traversal visits all the nodes of each level from left to right before moving to the next level.
- A level order traversal of the binary tree illustrated above visits nodes in the order is = A, B, C, D, E, F, G.
Advantages of Binary Tree
- It is one of the most stable, basic/fundamental type of tree.
- Insertion of data items occur easily.
- It is a simple tree.
Demerits/Disadvantages of Binary Tree
- No specific arrangement of data occurs inside it, like BST.
- Maximum two values can be stored in its parent node.
- The searching & deletion process is very complex and time consuming.
Use/Application of Binary Tree
- Binary tree is used as –
- Arithmetic Expression Tree to represent arithmetic expression of an equation where internal nodes to represent operators and external nodes to represent operands. For example – arithmetic expression tree for the expression: (2 * (a – 1) + (3 * b))
- Binary tree is used as decision tree which is associated with a decision process where internal nodes are used to represent questions with yes/no answer and external nodes to decisions/output.
- To store and search data from a database.
- To represent File System structure.
- In Computer Routing Algorithm.
- To implement Heap data structure.
- Used as Syntax tree.
0 Comments