Skewed Binary Tree in Java

One of the important topics that is asked in the interview regarding binary trees is skewed binary tree in Java. One must know about the skewed binary tree as it paves the way to know why it is important to know AVL and other trees. It is one of the fundamental trees that also affects the time complexity of the data structure (Binary Search Tree).

Types of Skewed Binary Tree

There are two types of skewed binary trees:

1. Left Skewed Binary Tree
2. Right Skewed Binary Tree

We will now explore the mentioned types in detail.

1. Left Skewed Binary Tree

A binary tree is said to be left skewed if all the nodes of the tree contain either left child only or no child at all. One can also say it is a left-side-dominated tree. Note that all the children that occur on the right side are null in this tree.

FileName: LeftSkewedBinaryTree.java

Output:

11 10 9 8 7 

2. Right Skewed Binary Tree

A binary tree is said to be right-skewed if all the nodes of the tree contain either the right child only or no child at all. One can also say it is a right-side-dominated tree. Note that all the children that occur on the left side are null in this case.

FileName: RightSkewedBinaryTree.java

Output:

11 12 13 14 15 

Skewed Binary Tree Affecting Complexity

One can treat a skewed binary tree as a linked list, and we know that traversing a linked list costs O(n) time. A skewed binary tree also takes O(n) time. If we take the case of the Binary Search Tree, we know that searching an element takes O(log(n), which gets increased to O(n) if the binary search tree is skewed. It is reasoning why the necessity of the self-balancing trees came into the picture.