BINARY TREE
In this blog post will study what is a binary tree, types, properties and applications.
Definition
A tree with atmost two child nodes is called as a binary tree i.e. a binary tree can have either zero or one or two child nodes only.
We can visualize a binary tree as consisting of a root and two disjoint binary trees.
Types
- Strict BT: A binary tree is called strict binary tree if each node has exactly two children or no children.
- Perfect BT: A binary tree is called perfect/full binary tree if each node has exactly two children and all leaf nodes are at the same level.
- Complete BT: A binary tree is called complete binary tree if all leaf nodes are at height h or h – 1 and also without any missing number in the sequence (will see this in Heap Tree).
Properties
- The maximum no. of nodes in a BT of height h is 2h+1+1.
- The number of leaf nodes in a perfect binary tree is 2h.
Applications
- Binary Expression trees are used in compilers.
- Binary Search Tree (BST), which supports search, insertion and deletion on a collection of items in O(logn) (average).
- Huffman coding trees that are used in data compression algorithms.
- Priority Queue (PQ), which supports search and deletion of minimum (or maximum) on a collection of items in logarithmic time (in worst case).
That's it from this blog post. If you liked it then do share this blog with your friends or people who wanna get into programming world. Thank You!