Exterior of a binary tree: wrong formulation of exterior? + easier solution

#1

Hi guys,

I believe the definition of exterior is incorrect. You define it as a path from the root to the leftmost leaf (leaf that appears first in an inorder traversal).
If we run your solution on a modified tree where node B(6) has no left child, the answer would be A,B,F,G,H,…
But nodes F,G are

  • not leaves
  • they are not on the path from root to the leftmost element which is B(6)

The same holds for the right border: if we remove right child of I(6), nodes J and K become part of the answer.

So, I guess you need to change the formulation of the problem.

In addition, using addAll() on a LinkedList has O(n) running time and probably should be replaced by passing LinkedList as an argument to recursive call.

I came up with an (easier?) solution which does a single traversal and uses 2 variables for left and right borders:

public static <T> List<T> computeExterior(TreeNode<T> root) {
    List<T> exterior = new ArrayList<>();
    computeExterior(root, exterior, true, true);
    return exterior;
}

private static <T> void computeExterior(TreeNode<T> node, List<T> exterior, boolean left, boolean right) {
    if (node == null) {
        return;
    }

    if (node.left == null && node.right == null) {
        exterior.add(node.data);
        return;
    }

    if (left) {
        exterior.add(node.data);
    }

    computeExterior(node.left, exterior, left, node.right == null ? right : false);
    computeExterior(node.right, exterior, node.left == null ? left : false, right);

    if (right && !left) {
        exterior.add(node.data);
    }
}

We pass information to the child if it’s a left/right border. If node has no left/right child, then its right/left child become the border.
It’s a mixture of inorder traversal for left border and postorder traversal for right border (because we need right elements from bottom to top).

0 Likes

#2

Hi guys, what do you think about it?

0 Likes

#3

Hey @damluar,

Definitely that the definition of exterior is broken here. I also like the simplicity of your solution although it is not very readable but I think I shall read it more to understand that.

I think it is mixture of preorder and postorder as you process node data before and after the recursive program, respectively.

Also, I cannot find that time complexity of LinkedList addAll() as I thought it would be like splice of list in C++, which is O(1) theoretically. If you find any documentation about its complexity, please let me know.

0 Likes

#4

Here it is:

0 Likes

#5

Hey @damluar,

I have an update for this problem about your argument. I think the program is fine since F and G is on the path to the leftmost “leaf” (you falsely thought we refer to the leftmost “element”). So the program is in fact works fine here.

0 Likes