A binary tree is a nonlinear data structure in which a node cannot have more than two child nodes. it means if in a tree each node is either a leaf node or has one or two child nodes then this tree is called a binary tree.

The T1 is called the left subtree and T2 is called the right subtree.

where I >= 0
and the tree which has nodes equal to their height are called skew trees.
because the height can't be more than n so there should be at least one node at every level and if the height is H then the maximum number of nodes possible is 2H - 1.
n = number of nodes
e = number of edges
then e = n -1
Because every node has exactly one parent except the root node and n-1 nodes have exactly one parent so there is only one edge between a parent and child.
if the n = 1 and e = 0 then n = 1 so the property is true.
n0 = number of nodes with no child
n2 = number of nodes with 2 children then n0 = n2 + 1


Path length: The number of edges traversed from that node to the root node is called the path length of a node.
Internal path length: it's is a sum of path lengths of all internal nodes.
External path length: it's a sum of path lengths of all external nodes.
Property: In an extended binary tree, if E is the external path length, I is the internal path length and n is the number of internal nodes, then E = I + 2n.

the height of a complete binary tree = [ log2(n+1)]


What is a binary tree in Data structures
It is a finite set of nodes that is either empty or either consists of a distinguished node known as root and remaining nodes are partitioned into two disjoint sets T1 and T2 and both of them are binary trees.The T1 is called the left subtree and T2 is called the right subtree.

Properties of Binary tree in Data structure
Property first
In a binary tree, the maximum number of nodes on any level I is 2iProperty second
In a binary tree of height H, the maximum number of nodes possible is 2H - 1Property third
In a binary tree of height H, the minimum number of nodes possible is H. because the minimum number of nodes possible at any level is 1 in a tree of height H and there are H levels.and the tree which has nodes equal to their height are called skew trees.
Property fourth
For any binary tree with n nodes, the maximum height possible is n and minimum height possible is [ log2(n+1)]because the height can't be more than n so there should be at least one node at every level and if the height is H then the maximum number of nodes possible is 2H - 1.
Property fifth
In a non-empty binary tree ifn = number of nodes
e = number of edges
then e = n -1
Because every node has exactly one parent except the root node and n-1 nodes have exactly one parent so there is only one edge between a parent and child.
if the n = 1 and e = 0 then n = 1 so the property is true.
Property sixth
In a non-empty binary tree, ifn0 = number of nodes with no child
n2 = number of nodes with 2 children then n0 = n2 + 1
Types of Binary Trees
- Strictly binary tree
- Extended binary tree
- Full binary tree
- Complete binary tree
What is a Strictly binary tree
A binary tree in which each node is either a left node or has two children is called a strictly binary tree and a strictly binary tree with n leaf nodes has n-1 non-leaf nodes and a total 2n - 1 node.
What is Extended Binary tree
In a binary tree if each empty subtree is replaced by a special node then the resulting tree is called an extended binary tree or 2-tree. and the special nodes are called external nodes and original nodes are called internal nodes.
Path length: The number of edges traversed from that node to the root node is called the path length of a node.
Internal path length: it's is a sum of path lengths of all internal nodes.
External path length: it's a sum of path lengths of all external nodes.
Property: In an extended binary tree, if E is the external path length, I is the internal path length and n is the number of internal nodes, then E = I + 2n.
What is Full binary tree
A binary tree in which each level has the maximum number of nodes is called a full binary tree. and if H is the height of a tree then the binary tree will have 2H - 1 node. then the height of a full binary tree is log2(n+1).
What is Complete binary tree
In a complete binary tree, all levels have a maximum number of nodes except possibly the last level and in the last level, the number of nodes ranges from 1 to 2H - 1 and all these nodes are towards the left.the height of a complete binary tree = [ log2(n+1)]

Program to implement a binary tree using python programming language.
from collections import deque class Node: def __init__(self, value): self.info = value self.lchild = None self.rchild = None class BinaryTree: def __init__(self): self.root = None def is_empty(self): return self.root is None def display(self): self._display(self.root, 0) print() def _display(self,p,level): if p is None: return self._display(p.rchild, level+1) print() for i in range(level): print(" ", end='') print(p.info) self._display(p.lchild, level+1) def preorder(self): self._preorder(self.root) print() def _preorder(self,p): if p is None: return print(p.info, " ", end='') self._preorder(p.lchild) self._preorder(p.rchild) def inorder(self): self._inorder(self.root) print() def _inorder(self,p): if p is None: return self._inorder(p.lchild) print(p.info," ", end='') self._inorder(p.rchild) def postorder(self): self._postorder(self.root) print() def _postorder(self,p): if p is None: return self._postorder(p.lchild) self._postorder(p.rchild) print(p.info," ",end='') def level_order(self): if self.root is None: print("Tree is empty") return qu = deque() qu.append(self.root) while len(qu) != 0: p = qu.popleft() print(p.info + " ", end='') if p.lchild is not None: qu.append(p.lchild) if p.rchild is not None: qu.append(p.rchild) def height(self): return self._height(self.root) def _height(self,p): if p is None: return 0 hL = self._height(p.lchild) hR = self._height(p.rchild) if hL > hR: return 1 + hL else: return 1 + hR def create_tree(self): self.root = Node('p') self.root.lchild = Node('Q') self.root.rchild = Node('R') self.root.lchild.lchild = Node('A') self.root.lchild.rchild = Node('B') self.root.rchild.lchild = Node('X') ########################## bt = BinaryTree() bt.create_tree() bt.display() print() print("Preorder : ") bt.preorder() print("") print("Inorder : ") bt.inorder() print() print("Postorder : ") bt.postorder() print() print("Level order : ") bt.level_order() print() print("Height of tree is ", bt.height())
Also, read these posts
- What are Data Structures and algorithms
- Algorithm design and analysis
- Classification of algorithms
- How to calculate the running time of an algorithm.
- Worst Average and Best-case analysis of the algorithm.
- Big o notation
- Big o notation examples
- Linked List in Data Structures
- Traversing in Linked list
- Operations on the linked list
- Insertion in the linked list
- Deletion in a linked list
- Reversing a linked list
- Sorting a linked list
- Find and remove the loop in the linked list
- Doubly linked list
- Insertion in the doubly linked list
- Deletion in the doubly linked list
- Reversing a doubly linked list
- Circular linked list
- Insertion in the circular linked list
- Deletion in the circular linked list
- Merge two linked list
- Header linked list
- Sorted linked list
- Stack in data structures
- Queue in data structures
- Circular queue
- Dequeue in the data structure
- Priority queue
- Polish notation
- Tree in the data structure
- Array representation of the binary tree
- linked representation of a binary tree
- Traversing in the binary tree
- Inorder traversal in the binary tree
- Preorder traversal in the binary tree
- Postorder traversal in the binary tree
- Level order traversal in the binary tree
- Binary search tree
- Insertion in the binary search tree
- Deletion in the binary search tree
- Heap in data structures
- What are Data Structures and algorithms
- Algorithm design and analysis
- Classification of algorithms
- How to calculate the running time of an algorithm.
- Worst Average and Best-case analysis of the algorithm.
- Big o notation
- Big o notation examples
- Linked List in Data Structures
- Traversing in Linked list
- Operations on the linked list
- Insertion in the linked list
- Deletion in a linked list
- Reversing a linked list
- Sorting a linked list
- Find and remove the loop in the linked list
- Doubly linked list
- Insertion in the doubly linked list
- Deletion in the doubly linked list
- Reversing a doubly linked list
- Circular linked list
- Insertion in the circular linked list
- Deletion in the circular linked list
- Merge two linked list
- Header linked list
- Sorted linked list
- Stack in data structures
- Queue in data structures
- Circular queue
- Dequeue in the data structure
- Priority queue
- Polish notation
- Tree in the data structure
- Array representation of the binary tree
- linked representation of a binary tree
- Traversing in the binary tree
- Inorder traversal in the binary tree
- Preorder traversal in the binary tree
- Postorder traversal in the binary tree
- Level order traversal in the binary tree
- Binary search tree
- Insertion in the binary search tree
- Deletion in the binary search tree
- Heap in data structures
0 Comments