Binary tree
A binary tree is a sequential data structure in which each node has at least two children, commonly called the left child and the right child.
Each node contains three components:
- Pointer to left subtree
- Pointer to right subtree
- Data element
The topmost node in the tree is called the root. A NULL pointer represents an empty tree.
- Binary Tree: Common Terminologies
- Root: Topmost node in a tree.
- Parent: Every node (except root) in a tree is connected by a pointed edge from one single node. This node is called a parent.
- Child: An area directly connected to another node when it emerges from the root.
- Leaf/External node: Node with no children.
- Internal node: Node with at least one children.
- Node depth: Number of edges from root to area.
- Node length: Number of edges from node to deep layer. The height of the tree is the height of the root.
Binary Tree Types (Based on Structure)
- Rooted Binary tree has a root node, and each node has at least two children..
- Full Binary Tree: It is a tree where every tree area has 0 or 2 children.
- Perfect Binary Tree: A binary tree where all the inner nodes have two offspring and leaves have the same depth or level.
- Complete the binary tree: It is a binary tree where all levels, except the last one, are completely filled, and all the nodes are as far away as possible.
- Balanced Binary Tree: Binary tree height is measured if it satisfies the following criteria:
The height of the left and right subtrees varies greatly from one to another, AND
The left subtree is rated, AGAIN
The correct subtree is rated
Empty tree of average height.
- Degenerate Tree: It is a tree where each parent's node has only one child node. It behaves like a linked list.
