Non-boundary nodes in a binary tree
I have a binary tree, I want to print all non-border nodes. Border nodes: - all leaf nodes + all nodes in the path from root to left node + all nodes from root to right node.
I did this by using an extra boolean in the tree structure to determine if it is bordering a node or not and then traversing and printing if not bordering nodes. Can someone come up with a better approach because it uses up some extra space (albeit very little).
source to share
One note that you might find useful is that a non-boundary node in a binary tree is one that (a) is not a leaf and (b) is where you took a step left and a step right along the path to access the node ... So one option would be to walk the tree normally, keeping track of whether you went left and left 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!
source to share