Introduction to Degenerate Binary Tree – GeeksforGeeks

Every non-leaf node has just one child in a binary tree known as a Degenerate Binary tree. The tree effectively transforms into a linked list as a result, with each node linking to its single child.

• When a straightforward and effective data structure is required, degenerate binary trees, a special case of binary trees, may be employed. For instance, a degenerate binary tree can be used to create a stack data structure since each node simply needs to store a reference to the next node.
• Degenerate binary trees are less effective than balanced binary trees at searching, inserting, and deleting data, though. This is due to the fact that degenerate binary trees may become unbalanced, resulting in performance that is comparable to a linked list in the worst case.
• Degenerate binary trees are rarely employed by themselves as a data structure in general. Rather, they are frequently utilized as a component of other data structures like linked lists, stacks, and queues. Degenerate binary trees can also be utilized as a particular instance to take into account in algorithms that traverse or search over binary trees.

Degenerate Binary tree is of two types:

• Left-skewed Tree:  If all the nodes in the degenerate tree have only a left child.
• Right-skewed Tree: If all the nodes in the degenerate tree have only a right child.

Examples:

Input: 1, 2, 3, 4, 5
Output:

Representation of right skewed tree

Explanation: Each parent node in this tree only has one child node. In essence, the tree is a linear chain of nodes.

Approach: To solve the problem follow the below idea:

 Idea is to use handle degenerate binary trees relies on the issue at hand. Degenerate trees may typically be transformed into linked lists or arrays, which can make some operations easier.

Steps involved in the implementation of code:

• Initializing structure of Tree.
• Inserting all data on the right side of a current node.
• Printing node by considering only the right node of each node.

Below is the implementation of the Right-skewed Tree:

Output : 

 

Below is the implementation of the Left-skewed Tree:

Time Complexity: O(N)
Auxiliary Space: O(N)