Operation in Binary tree

Binary Tree

 

---

A binary tree is a hierarchical data structure consisting of nodes, where each node can have at most two children: a left child and a right child. Let's delve into binary trees and their properties based on the given concept:

Nodes and Structure:

Each node in a binary tree contains some data and can have up to two children.

The structure of a binary tree is such that each node can have a left child and/or a right child.

Root Node:

The root node is the topmost node of the binary tree.

It serves as the starting point for accessing the entire tree structure.

Left and Right Subtrees:

• Each node in a binary tree has two disjoint subsets: the left subtree and the right subtree.
• The left sub-tree is itself a binary tree, containing nodes that are descendants of the current node's left child.
• Similarly, the right subtree is also a binary tree, containing nodes that are descendants of the current node's right child.

Following tree is example of Binary Tree:

 

Different types of Binary Tree

Full Binary Tree:

• In a full binary tree, every node has either zero or two children.
• Each non-leaf node has exactly two children.
• Also known as a proper binary tree or 2-tree.

Complete Binary Tree:

• In a complete binary tree, every level except possibly the last is completely filled, and all nodes are as far left as possible.
• If the last level is not completely filled, it is filled from left to right.
• Complete binary trees are commonly used in heaps and priority queues.

Perfect Binary Tree:

• In a perfect binary tree, all internal nodes have exactly two children, and all leaf nodes are at the same level.
• It is both full and complete.
• The number of nodes at each level doubles as you move down the tree.

 

Balanced Binary Tree:

• In a balanced binary tree, the heights of the two subtrees of any node differ by at most one.
• Ensures that the tree remains relatively balanced, leading to efficient insertion, deletion, and search operations.
• Examples of balanced binary trees include AVL trees and red-black trees.

Degenerate or Pathological Binary Tree:

• In a degenerate binary tree, each parent node has only one associated child node, leading to a chain-like structure.
• Also known as a pathological tree.
• Degenerate binary trees have poor time complexity for many operations, as they essentially behave like linked lists.

Skewed Binary Tree:

• A skewed binary tree is a special case of a degenerate binary tree where all nodes have only one child, either left or right.
• It can be either left-skewed or right-skewed, depending on the direction of the child nodes.

 

Binary Tree Representation

A node of a binary tree is represented by a structure containing a data part and two pointers to other structures of the same type.

struct node
{
 int data;
 struct node *left;
 struct node *right;
};