Given a Binary tree, the task is to Print Boundary View in Binary Tree, visiting the boundary nodes in an anticlockwise direction starting from the root.
Code Flow for Print Boundary View In Binary Tree
-
Start at the root.
-
Add the root to the result if it's not a leaf.
-
Traverse and add left boundary nodes, excluding leaf nodes.
-
Traverse and add bottom boundary nodes, ie, all leaf nodes.
-
Traverse and add right boundary nodes, excluding leaf nodes, which are added in reverse order.
-
Return the list of boundary nodes.
Let's see the code now
package org.wesome.dsalgo;
import lombok.Data;
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
@Data
class Node {
int data;
Node left;
Node right;
Node(int val) {
data = val;
}
}
public class BinaryTree {
/* check if a node is a leaf Node, i.e., if it has left and right child node, then this node will not be a boundary */
boolean isLeafNode(Node root) {
var bool = Objects.isNull(root.left) && Objects.isNull(root.right);
System.out.println("BinaryTree.isLeafNode:- " + root.data + " is leaf node " + bool);
return bool;
}
/* add Left Leaf nodes excluding Bottom leaf Node, because those will be part of the bottom boundary */
void addLeftLeafNode(Node root, List<Integer> result) {
Node currNode = root.left;
while (Objects.nonNull(currNode)) {
/* if the current node is not a leaf node, i.e., it has a child node, then add its value into the list */
if (!isLeafNode(currNode)) {
result.add(currNode.data);
}
/* if the current node left exists, then move to next left else move to right */
if (Objects.nonNull(currNode.left)) {
currNode = currNode.left;
} else {
currNode = currNode.right;
}
}
}
/* add right Leaf nodes excluding Bottom leaf Node in reverse order, because those will be part of the bottom boundary */
void addRightLeafNode(Node root, List<Integer> result) {
Node currNode = root.right;
List<Integer> tempList = new ArrayList<>();
while (Objects.nonNull(currNode)) {
/* if the current node is not a leaf node, i.e., it has child nodes, then add it to the temp list for further iteration */
if (!isLeafNode(currNode)) {
tempList.add(currNode.data);
}
/* if the current node right exists, then move to next right else move to left */
if (Objects.nonNull(currNode.right)) {
currNode = currNode.right;
} else {
currNode = currNode.left;
}
}
/* the right leaf nodes are added in top to down or clock wise direction, but the result has to be bottom to up or anticlockwise wise direction, hence reverse the temp list */
result.addAll(tempList.reversed());
}
/* traverse in a preorder manner, i.e., left-> root-> right, but ignore root since it has child hence it's not boundary, add bottom Leaf nodes */
void addBottomLeafNode(Node root, List<Integer> result) {
/* if the node has no left and right child, then its bottom leaf node */
if (isLeafNode(root)) {
System.out.println("BinaryTree.addBottomLeafNode:- root = " + root.data);
result.add(root.data);
return;
}
/* if the node has a left and right child, then it's not a bottom leaf node, so keep iterating left and right node */
if (Objects.nonNull(root.left)) {
addBottomLeafNode(root.left, result);
}
if (Objects.nonNull(root.right)) {
addBottomLeafNode(root.right, result);
}
}
List<Integer> printBinaryTreeLeaf(Node root) {
List<Integer> list = new ArrayList<>();
if (Objects.isNull(root)) {
System.out.println("BinaryTree.printBinaryTreeLeaf root is null");
return list;
}
/* if root is not a leaf node, i.e., it has child nodes, add in list */
if (!isLeafNode(root)) {
System.out.println("BinaryTree.printBinaryTreeLeaf root is not a leaf node");
list.add(root.data);
}
/* add left leaf nodes in the list */
addLeftLeafNode(root, list);
/* add bottom leaf nodes in the list */
addBottomLeafNode(root, list);
/* add left leaf nodes in the list */
addRightLeafNode(root, list);
return list;
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;
import java.util.List;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;
public class BinaryTreeTest {
private BinaryTree binaryTree;
@BeforeEach
void setUp() {
binaryTree = new BinaryTree();
}
// Test case 1: Empty Tree
@Test
void testEmptyTree() {
Node root = null;
List<Integer> result = binaryTree.printBinaryTreeLeaf(root);
assertTrue(result.isEmpty(), "The result should be empty for an empty tree.");
}
// Test case 2: Tree with only one node (Leaf node)
@Test
void testSingleNode() {
Node root = new Node(1);
List<Integer> result = binaryTree.printBinaryTreeLeaf(root);
assertEquals(List.of(1), result, "The result should contain only the single root node.");
}
// Test case 3: Tree with two nodes (One parent and one child)
@Test
void testTwoNodes() {
Node root = new Node(1);
root.left = new Node(2); // left child
List<Integer> result = binaryTree.printBinaryTreeLeaf(root);
assertEquals(List.of(1, 2), result, "The result should contain the boundary nodes: root and the leaf node.");
}
// Test case 4: Simple tree with left and right subtrees
@Test
void testSimpleTree() {
// Constructing the following tree:
// 1
// / \
// 2 3
// \ /
// 4 5
Node root = new Node(1);
root.left = new Node(2);
root.left.right = new Node(4);
root.right = new Node(3);
root.right.left = new Node(5);
List<Integer> result = binaryTree.printBinaryTreeLeaf(root);
assertEquals(List.of(1, 2, 4, 5, 3), result, "The result should contain the boundary nodes in anticlockwise order.");
}
// Test case 5: Tree with only left children (Linear Tree)
@Test
void testLeftLinearTree() {
// Constructing the following tree:
// 1
// /
// 2
// /
// 3
Node root = new Node(1);
root.left = new Node(2);
root.left.left = new Node(3);
List<Integer> result = binaryTree.printBinaryTreeLeaf(root);
assertEquals(List.of(1, 2, 3), result, "The result should contain the boundary nodes in anticlockwise order.");
}
// Test case 6: Tree with only right children (Linear Tree)
@Test
void testRightLinearTree() {
// Constructing the following tree:
// 1
// \
// 2
// \
// 3
Node root = new Node(1);
root.right = new Node(2);
root.right.right = new Node(3);
List<Integer> result = binaryTree.printBinaryTreeLeaf(root);
assertEquals(List.of(1, 3, 2), result, "The result should contain the boundary nodes in anticlockwise order.");
}
// Test case 7: Tree with both left and right children with a larger structure
@Test
void testLargeTree() {
// Constructing the following tree:
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
List<Integer> result = binaryTree.printBinaryTreeLeaf(root);
assertEquals(List.of(1, 2, 4, 5, 6, 7, 3), result, "The result should contain the boundary nodes in anticlockwise order.");
}
// Test case 8: Tree with all leaf nodes on the right side
@Test
void testAllLeafNodesRight() {
// Constructing the following tree:
// 1
// \
// 2
// \
// 3
// \
// 4
Node root = new Node(1);
root.right = new Node(2);
root.right.right = new Node(3);
root.right.right.right = new Node(4);
List<Integer> result = binaryTree.printBinaryTreeLeaf(root);
assertEquals(List.of(1, 4, 3, 2), result, "The result should contain the boundary nodes in anticlockwise order.");
}
// Test case 9: Tree with duplicate values
@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);
List<Integer> result = binaryTree.printBinaryTreeLeaf(root);
assertEquals(List.of(1, 1, 1, 1, 1, 1, 1), result, "The result should contain all boundary nodes in anticlockwise order.");
}
@Test
void testTreeWithCustomValues() {
// Creating a sample binary tree
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
assertEquals(List.of(1, 2, 4, 5, 6, 7, 3), binaryTree.printBinaryTreeLeaf(root), "The result should contain the root, left boundary nodes and right boundary nodes in anticlockwise order.");
}
}
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
-
Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity
-
Space Complexity: O(n), where n is the number of nodes in the tree.
