WikiGalaxy
WikiGalaxy💙Blue💛🌹
Personalize
Degenerate Tree
Introduction to Degenerate Trees
A degenerate (or pathological) tree is a tree where each parent node has only one associated child node. This structure resembles a linked list, as each node points to the next in a single linear fashion.
Characteristics of a Degenerate Tree
- Each node has at most one child.
- The tree height is equal to the number of nodes minus one.
- It behaves like a linked list.
Example 1: Simple Degenerate Tree
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class DegenerateTree {
Node root;
void addNode(int data) {
if (root == null) {
root = new Node(data);
} else {
Node current = root;
while (current.next != null) {
current = current.next;
}
current.next = new Node(data);
}
}
}
Console Output:
Node added to degenerate tree
Example 2: Traversing a Degenerate Tree
class DegenerateTreeTraversal {
Node root;
void traverse() {
Node current = root;
while (current != null) {
System.out.println(current.data);
current = current.next;
}
}
}
Console Output:
10 20 30 40
Example 3: Searching in a Degenerate Tree
class DegenerateTreeSearch {
Node root;
boolean search(int key) {
Node current = root;
while (current != null) {
if (current.data == key) {
return true;
}
current = current.next;
}
return false;
}
}
Console Output:
Search Result: Found
Example 4: Deleting a Node in a Degenerate Tree
class DegenerateTreeDelete {
Node root;
void deleteNode(int key) {
if (root == null) return;
if (root.data == key) {
root = root.next;
return;
}
Node current = root;
while (current.next != null) {
if (current.next.data == key) {
current.next = current.next.next;
return;
}
current = current.next;
}
}
}
Console Output:
Node Deleted
Example 5: Converting a Degenerate Tree to a Balanced Tree
class BalancedTreeConversion {
Node root;
Node convertToBalanced(Node head) {
if (head == null || head.next == null) return head;
Node slow = head, fast = head, prev = null;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
Node root = slow;
prev.next = null;
root.left = convertToBalanced(head);
root.right = convertToBalanced(slow.next);
return root;
}
}
Console Output:
Tree Converted to Balanced
