Non-boundary nodes in a binary tree

Question

I have a binary tree, i want to print all non-boundary nodes. Boundary Nodes:- All leaf nodes+all nodes on path from root to leftest node+all nodes from root to rightest node.

I ave done this using an extra boolean in tree structure to identify whether it's boundary node or not and then doing a traversal and printing if not boundary nodes. Can someone come up with a better approach, because it's using some extra space(though very less).

Answer 1

One observation you might find helpful is that a non-boundary node in a binary tree is one that (a) isn't a leaf and (b) is one where along the access path to the node, you've taken a step left and a step right. Therefore, one option would be to do a normal tree traversal, tracking whether you've gone left and gone right along the way. Here's some pseudocode:

function printNonBoundaryNodesRec(root, goneLeft, goneRight) {
    if (root == null or root is a leaf) return;

    if (goneLeft and goneRight) print root.value
    printNonBoundaryNodesRec(root.left, true, goneRight);
    printNonBoundaryNodesRec(root.right, goneLeft, true);
}

function printNonBoundaryNodes(root) {
    printNonBoundaryNodesRec(root, false, false);
}

Hope this helps!