Skip to content

Instantly share code, notes, and snippets.

@sdpatil
Created August 12, 2017 19:46
Show Gist options
  • Save sdpatil/2b70bbec883ef54c8c76c0a3eb6192fc to your computer and use it in GitHub Desktop.
Save sdpatil/2b70bbec883ef54c8c76c0a3eb6192fc to your computer and use it in GitHub Desktop.
Write a program that computes exterior of binary tree
/**
* Problem: Write a program that computes exterior of binary tree
*/
public class ComputeExteriorOfBinaryTree {
public List<BinaryTreeNode<String>> exteriorBinaryTree(BinaryTreeNode<String> tree){
List<BinaryTreeNode<String>> result = new LinkedList<>();
if(tree!= null){
result.add(tree);
result.addAll(leftBoundaryAndLeaves(tree.left, true));
result.addAll(rightBoundaryAndLeaves(tree.right, true));
}
return result;
}
public List<BinaryTreeNode<String>> leftBoundaryAndLeaves(BinaryTreeNode<String> subTreeRoot,
boolean isBoundary){
List<BinaryTreeNode<String>> result = new LinkedList<>();
if(subTreeRoot != null){
if(isBoundary || isLeaf(subTreeRoot))
result.add(subTreeRoot);
result.addAll(leftBoundaryAndLeaves(subTreeRoot.left,isBoundary));
result.addAll(leftBoundaryAndLeaves(subTreeRoot.right,isBoundary && subTreeRoot.left == null));
}
return result;
}
public List<BinaryTreeNode<String>> rightBoundaryAndLeaves(BinaryTreeNode<String> subTreeRoot,
boolean isBoundary){
List<BinaryTreeNode<String>> result = new LinkedList<>();
if(subTreeRoot != null){
result.addAll(rightBoundaryAndLeaves(subTreeRoot.left,isBoundary && subTreeRoot.right == null));
result.addAll(leftBoundaryAndLeaves(subTreeRoot.right,isBoundary));
if(isBoundary || isLeaf(subTreeRoot))
result.add(subTreeRoot);
}
return result;
}
public boolean isLeaf(BinaryTreeNode<String> tree){
return tree.left == null && tree.right == null;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment