A binary tree is a hierarchical data structure in which each node has no more than two children, known as left and right children.
Each node is made up of three parts:
- The subtree on the left is indicated by a pointer.
- The right subtree is shown with a pointer.
- Element of data
The root refers to the tree's topmost node. A NULL pointer represents an empty tree.
Common Terminologies for the Binary Tree:
- The topmost node in a tree is called the root.
- Every node in a tree (excluding the root) is connected to exactly one other node by a directed edge. This node is referred to as a parent.
- When going away from the root, a child is a node that is directly related to another node.
- Node with no children (leaf/external node).
- Node having at least one child is referred to as an internal node.
- The number of edges from the root to the node is the depth of a node.
- The number of edges from the node to the deepest leaf determines the height of a node.
- The root's height is the tree's height.
Benefits of Trees:
Trees are so beneficial and widely used because they provide a number of significant benefits:
The structural linkages in the data are shown in trees.
Hierarchies are represented by trees.
Insertion and searching are made easier with trees.
Trees are a very flexible type of data because they allow you to move subtrees around with little effort.
Binary Trees Come in a Variety of Shapes and Sizes (Based on Structure):
Rooted binary tree:
A rooted binary tree contains a root node and at most two children for each node.
Full binary tree:
The full binary tree is a tree in which each node has either 0 or 2 offspring.
In a full binary tree, the number of nodes, n, is at least 2h – 1 and at most 2h+1 – 1, where h is the tree's height.
In a full binary tree, the number of leaf nodes l is equal to the number of internal nodes L + 1, i.e. l = L+1.
Perfect binary tree:
It's a binary tree with all interior nodes having two offspring and all leaves having the same depth or level.
There are n = 2l-1 nodes in a perfect binary tree with l leaves.
l = 2h and n = 2h+1 - 1 in a perfect full binary tree, where n is the number of nodes, h is the tree's height, and l is the number of leaf nodes.
Also Read: Diameter Of A Binary Tree
Complete binary tree:
A complete binary tree is one in which every level is completely filled, save potentially the last, and all nodes are as far left as feasible.
Floor(n/2) is the number of internal nodes in a complete binary tree with n nodes.
Height-balanced binary tree: If a binary tree satisfies the following conditions, it is height-balanced:
The heights of the left and right subtrees differ by only one, AND the left subtree is balanced, AND
The right subtree is in a good place.
The height of an empty tree is balanced.
- A balanced binary tree has a height of O(Log n), where n is the number of nodes.
