Print Edge Nodes (Boundary) of a Binary Tree

Source

Here’s an interview question from Microsoft. Thanks to one reader who contributed this interesting question.

Print all edge nodes of a complete binary tree anti-clockwise.
That is all the left most nodes starting at root, then the leaves left to right and finally all the rightmost nodes.
In other words, print the boundary of the tree.

Variant: Print the same for a tree that is not complete.

Some Examples:
** Please see Further Thoughts section below for an example which points out an ambiguity found in the problem statement. **

Assume we have a binary tree below:

    _30_    /    \      10    20  /     /  \ 50    45  35

The correct solution should print 30, 10, 50, 45, 35, 20.

Another binary tree:

        ______30______        /              \     __20__          __40__    /      \        /      \   10      25      35      50  /  \       \            /  5  15      28          41

The correct solution should print 30, 20, 10, 5, 15, 28, 35, 41, 50, 40.

Solution:

void printLeftEdge(node* pRoot) {

if (pRoot->left) {

printf("%d", pRoot->data);

printLeftEdge(pRoot->left);

}

}

void printLeafNodes(node* pRoot) {

if (pRoot) {

printLeadNodes(pRoot->left);

if(!(pRoot->left || pRoot->right)) {

printf("%d", pRoot->data);

}

printLeafNodes(pRoot->right);

}

}

void printRightEdge(node* pRoot) {

if (pRoot->right) {

printRightEdge(pRoot->right);

printf("%d", pRoot->data);

}

}

void printBTreeEdgeNodes(node* pRoot) {

if (pRoot) {

printLeftEdge(pRoot);

if (pRoot->left || pRoot->right) {

printLeafNodes(pRoot);

}

printRightEdge(pRoot->right);

}

}