9.1.4 Compute The Exterior of a Binary Tree: Better solution?

#1

Most of the problems in the book provide very well-reasoned solutions, which typically use very concise and minimal code as they utilize one of the logical ‘best’ approaches. However, I feel like the solution to this problem provided by EPI is very piecemeal; it basically breaks down a tree problem into three separate tree problems (find path from root to left + find leaves in-order + find path from rightmost leaf to root) rather than utilizing a more ‘elegant’ recursive solution that covers all of these cases.

I just wanted to share a solution I came up with to the ‘exterior of a binary tree’ problem, as I felt the solution provided by the text was not in good keeping with the rest. Please let me know if you see any fundamental flaws with my code or approach.

All the best!

Code:

  public static List<BinaryTreeNode<Integer>> exteriorBinaryTree(BinaryTreeNode<Integer> tree) {
    if(tree == null) return Collections.emptyList();
    List<BinaryTreeNode<Integer>> list = new ArrayList<>(){
      { add(tree); }
    };
    exterior(list, tree.left, true, false);
    exterior(list, tree.right, false, true);
    return list;
  }

  private static void exterior(List<BinaryTreeNode<Integer>> list, BinaryTreeNode<Integer> tree,
                                boolean leftMost, boolean rightMost) {
    if(tree == null) {
      // null: return from function
    } else if(tree.left == null && tree.right == null) { // leaf: add it and return
      list.add(tree);
    } else {
      if(leftMost) list.add(tree); // add leftmost branches before continuing traversal
      exterior(list, tree.left, leftMost, rightMost && tree.right == null);
      exterior(list, tree.right, leftMost && tree.left == null, rightMost);
      if(rightMost && !leftMost) list.add(tree); // add rightmost branches after traversal (!leftMost avoids duplicates)
    }
  }
0 Likes

#2

Is it possible to format it in code blocks for better readability?

I am a piece of code.
Make your code like me.
0 Likes

#4

Yeah, I suppose I’m not making any friends making people read through that mess!

0 Likes