Given a Binary tree, the task is to Get Maximum width of Binary Tree, The width of a binary tree refers to the number of nodes at a specific level of the tree.
Code Flow for Get Maximum width of Binary Tree
-
Base case: If the root node is
null, meaning the width of an empty tree is0,returns0, -
maxWidth: A variable to track the maximum width observed during traversal initialized to 0. -
height: The height of the tree is determined by callinggetTreeHeight. -
Level-wise iteration:
-
The method loops through all levels from 1 to the tree's height.
-
For each level, it calls
getWidthto get the number of nodes at the current level -
If
currentWidthis greater thanmaxWidth, the value ofmaxWidthis updated. -
The method returns the largest width found during the iteration.
-
Method: getWidth
-
Base case: If the node is
null, the method returns 0 since no node is present at this level. - If the level is
1, it means the current node is at the desired level, so the method returns1-
If the level is greater than
1, the method recursively calls itself on the left and right subtrees and adds the results together.
-
Let's see the code now
package org.wesome.dsalgo;
import lombok.Data;
import java.util.Objects;
public class BinarySearchTree {
Node root;
public static int getTreeHeight(Node node) {
if (Objects.isNull(node)) {
System.out.println("BinaryTree.countTreeHeight node is null");
return 0;
}
return Math.max(getTreeHeight(node.left), getTreeHeight(node.right)) + 1;
}
/* This method calculates the maximum width of the binary tree, which is the largest number of nodes present at any level in the tree. */
public static int getMaximumWidth(Node node) {
/* If the root node is null, it prints a message and returns 0, meaning the width of an empty tree is 0. */
if (Objects.isNull(node)) {
System.out.println("BinarySearchTree.getMaximumWidth node is null");
return 0;
}
/* variable to track the maximum width observed during traversal */
int maxWidth = 0;
int currentLevelWidth;
int treeHeight = getTreeHeight(node);
for (int i = 1; i <= treeHeight; i++) {
currentLevelWidth = getWidth(node, i);
if (currentLevelWidth > maxWidth) {
System.out.println("BinarySearchTree.getMaximumWidth treeHeight: " + treeHeight + " currentLevelWidth: " + currentLevelWidth + " maxWidth: " + maxWidth);
maxWidth = currentLevelWidth;
}
}
return maxWidth;
}
/* This method calculates the number of nodes at a given level in the tree. */
private static int getWidth(Node node, int level) {
/* If the node is null, the method returns 0 since no node is present at this level. */
if (Objects.isNull(node)) {
return 0;
}
/* f the level is 1, it means the current node is at the desired level, so the method returns 1 */
if (level == 1) {
System.out.println("BinarySearchTree.getWidth level node is " + level);
return 1;
}
/* If the level is greater than 1, the method recursively calls itself on the left and right subtrees and adds the results together. */
else if (level > 1) {
System.out.println("BinarySearchTree.getWidth level is greater then 1 " + level);
return getWidth(node.left, level - 1) + getWidth(node.right, level - 1);
}
return 0;
}
void insert(int data) {
System.out.println("BinarySearchTree.insert data = " + data);
root = insert(root, data);
}
Node insert(Node root, int data) {
if (Objects.isNull(root)) {
Node tempNode = new Node(data);
return tempNode;
}
if (data > root.data) {
root.right = insert(root.right, data);
} else {
root.left = insert(root.left, data);
}
return root;
}
}
@Data
class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
left = right = null;
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;
public class BinaryTreeTest {
@Test
void testEmptyTree() {
BinarySearchTree tree = new BinarySearchTree();
// Test for an empty tree (null root)
assertEquals(0, tree.getMaximumWidth(null), "Maximum width of an empty tree should be 0");
}
@Test
void testSingleNodeTree() {
// Test for a tree with a single node
BinarySearchTree tree = new BinarySearchTree();
tree.insert(10);
assertEquals(1, tree.getMaximumWidth(tree.root), "Maximum width of a single node tree should be 1");
}
@Test
void testBalancedBinarySearchTree() {
// Test for a balanced binary tree
BinarySearchTree tree = new BinarySearchTree();
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(2);
tree.insert(7);
tree.insert(12);
tree.insert(18);
assertEquals(4, tree.getMaximumWidth(tree.root), "Maximum width of balanced binary tree nodes should be correct");
}
@Test
void testUnbalancedBinarySearchTree() {
// Test for an unbalanced binary tree (sorted order insertion creating a right-skewed tree)
BinarySearchTree tree = new BinarySearchTree();
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(40);
tree.insert(50);
assertEquals(1, tree.getMaximumWidth(tree.root), "Maximum width of right-skewed tree nodes should be correct");
}
@Test
void testTreeWithNegativeValues() {
// Test for a tree with negative values
BinarySearchTree tree = new BinarySearchTree();
tree.insert(-5);
tree.insert(-3);
tree.insert(-2);
tree.insert(-1);
tree.insert(-7);
tree.insert(-4);
assertEquals(2, tree.getMaximumWidth(tree.root), "Maximum width of tree with negative values should be correct");
}
@Test
void testLargeTree() {
// Test for a large tree with many nodes
BinarySearchTree tree = new BinarySearchTree();
for (int i = 1; i <= 1000; i++) {
tree.insert(i);
}
assertEquals(1, tree.getMaximumWidth(tree.root), "Maximum width of large tree should be correct");
}
@Test
void testBalancedTree() {
Node root = new Node(10);
root.left = new Node(5);
root.right = new Node(15);
root.left.left = new Node(2);
root.left.right = new Node(7);
root.right.left = new Node(12);
root.right.right = new Node(18);
assertEquals(4, BinarySearchTree.getMaximumWidth(root), "Maximum width of Balanced Tree should be correct");
}
@Test
void testRightSkewedTree() {
// Constructing the following tree:
// 10
// \
// 20
// \
// 30
// \
// 40
// \
// 50
Node root = new Node(10);
root.right = new Node(20);
root.right.right = new Node(30);
root.right.right.right = new Node(40);
root.right.right.right.right = new Node(50);
assertEquals(1, BinarySearchTree.getMaximumWidth(root), "Maximum width of Right Skewed should be correct");
}
@Test
void testLeftSkewedTree() {
// Constructing the following tree:
// 10
// /
// 20
// /
// 30
// /
// 40
// /
// 50
Node root = new Node(10);
root.left = new Node(20);
root.left.left = new Node(30);
root.left.left.left = new Node(40);
root.left.left.left.left = new Node(50);
assertEquals(1, BinarySearchTree.getMaximumWidth(root), "Maximum width of Left Skewed should be correct");
}
@Test
void testTreeWithDuplicateValues() {
// Constructing the following tree:
// 1
// / \
// 1 1
// / \ / \
// 1 1 1 1
Node root = new Node(1);
root.left = new Node(1);
root.right = new Node(1);
root.left.left = new Node(1);
root.left.right = new Node(1);
root.right.left = new Node(1);
root.right.right = new Node(1);
assertEquals(4, BinarySearchTree.getMaximumWidth(root), "Maximum width of Tree with duplicate values.");
}
@Test
public void testCompleteBinaryTree() {
Node root = new Node(10);
root.left = new Node(5);
root.right = new Node(15);
root.left.left = new Node(3);
root.left.right = new Node(7);
root.right.left = new Node(12);
root.right.right = new Node(18);
root.left.left.left = new Node(1);
root.left.left.right = new Node(4);
assertEquals(4, BinarySearchTree.getMaximumWidth(root), "Height of a complete binary tree should be 4.");
}
}
plugins {
id("java")
id("io.freefair.lombok") version "8.13"
}
group = "org.wesome.dsalgo"
version = "1.0-SNAPSHOT"
repositories {
mavenCentral()
}
dependencies {
testImplementation(platform("org.junit:junit-bom:5.10.0"))
testImplementation("org.junit.jupiter:junit-jupiter")
}
tasks.test {
useJUnitPlatform()
}Complexity Analysis
-
Time Complexity: O(n²) in the worst case for skewed trees
-
Space Complexity: O(n) due to recursion stack
