Boundary Sum Problem in Java
Given a tree, our task is to find the sum of all the boundary nodes present in a binary tree with 'N' nodes, which is the result. The root node, the outermost nodes on the left and right, and all of the tree's leaves are the boundary nodes.
Example 1:
Input:
Output:
The boundary node sum of the given tree is 59.
Explanation:
The boundary nodes of the tree are:
Root node: 10
Leftmost node: 12
Right most node: 3
Leaf Nodes: 9, 11, 6, 8
Therefore, after performing the sum of all nodes, the result obtained is 59, which is an output.
Approach: Using Recursion
In order to calculate the boundary sum of nodes for the given tree, we need to calculate the following 3 things.
- The sum of leftmost nodes
- The sum of rightmost nodes
- The sum of leaf nodes
Algorithm:
Step 1: Traverse every leaf node to get the leaf node sum.
Step 1.1: If left child == "NULL" and right child == "NULL" add node to sum.
Step 2: Traverse the left-sub-tree to get the left-sub-tree boundary sum.
Step 2.1: If left child != "NULL," add the current parent node to sum and traverse the entire left subtree, then traverse to the right subtree of the node.
Step 2.2: If the right child != "NULL," traverse recursively to the right child node until "NULL" occurs.
Step 3: Traverse the right-sub-tree to determine the right-sub-tree sum.
Step 3.1: If the right child != "NULL," add the current parent node to sum and traverse the entire right subtree, then traverse to the left subtree of the node.
Step 3.2: If left child != "NULL," traverse recursively to the left child node until "NULL" occurs.
Step 4: Add the leftmost node sum and rightmost node sum to the boundary sum.
Implementation:
FileName: BoundarySum.java
import java.io.*;
import java.util.*;
public class BoundarySum
{
// Initialization of Binary Tree Node
static class BinaryTreeNode<Tree>
{
Tree data;
BinaryTreeNode<Tree> leftNode;
BinaryTreeNode<Tree> rightNode;
public BinaryTreeNode(Tree data)
{
this.data = data;
this.leftNode = null;
this.rightNode = null;
}
}
private static int sumLeafNode(BinaryTreeNode<Integer> root)
{
int LeavesSum = 0;
if (root != null)
{
LeavesSum += sumLeafNode(root.leftNode);
// Sum it up if it is a leaf node.
if ((root.leftNode == null) && (root.rightNode == null))
{
LeavesSum += root.data;
}
LeavesSum += sumLeafNode(root.rightNode);
}
return LeavesSum;
}
private static int LeftBoundarySum(BinaryTreeNode<Integer> root)
{
int leftSum = 0;
if (root != null)
{
if (root.leftNode != null)
{
// Add current parent node.
leftSum += root.data;
// Left subtree.
leftSum += LeftBoundarySum(root.leftNode);
}
else if (root.rightNode != null)
{
leftSum += root.data;
// Right subtree.
leftSum += LeftBoundarySum(root.rightNode);
}
}
return leftSum;
}
private static int RightBoundarySum(BinaryTreeNode<Integer> root)
{
int rightSum = 0;
if (root != null)
{
if (root.rightNode != null)
{
// Add current parent node.
rightSum += root.data;
// Right subtree.
rightSum += RightBoundarySum(root.rightNode);
}
else if (root.leftNode != null)
{
rightSum += root.data;
// Left subtree.
rightSum += RightBoundarySum(root.leftNode);
}
}
return rightSum;
}
public static int boundarySum(BinaryTreeNode<Integer> root)
{
if (root != null)
{
// Add the root node to the sum.
int sum = root.data;
// Find the leftmost boundary sum with the left subtree.
sum += LeftBoundarySum(root.leftNode);
// Sum of leaf nodes of the left subtree.
sum += sumLeafNode(root.leftNode);
// Sum of leaf nodes of the right subtree.
sum += sumLeafNode(root.rightNode);
// Find the rightmost boundary sum with the right subtree.
sum += RightBoundarySum(root.rightNode);
// Return the answer.
return sum;
}
return 0;
}
public static void main(String[] args)
{
// Creating a binary tree
BinaryTreeNode<Integer> root = new BinaryTreeNode<>(10);
root.leftNode = new BinaryTreeNode<>(12);
root.rightNode = new BinaryTreeNode<>(3);
root.leftNode.leftNode = new BinaryTreeNode<>(9);
root.leftNode.rightNode = new BinaryTreeNode<>(11);
root.rightNode.leftNode = new BinaryTreeNode<>(6);
root.rightNode.rightNode = new BinaryTreeNode<>(8);
// Calculate the sum of boundary nodes
int boundarySum = boundarySum(root);
System.out.println("The Sum of boundary nodes of the tree is : " + boundarySum);
}
}
Output:
The Sum of boundary nodes of the tree is : 59
Complexity Analysis:
The time complexity is O(N), and the Space Complexity is O(N), where 'N' is the number of nodes in the binary tree.