Print Edge Nodes (Boundary) of a Binary Tree

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.

Hint:
To solve this problem, you first need to pay attention to these three key areas:

• Printing the leftmost edges from top to bottom. When a node is a leftmost edge, its left child must also be a leftmost edge.
• Printing the leaves from left to right. Remember depth-first traversal?
• Printing the rightmost edges. You would need to print from bottom to top. The key is printing in the opposite order. Easy if you know how to manipulate recursion into a stack-based solution. Remember post-order traversal?

Solution:
We could divide the tree into two subtrees. One is the left subtree, and the other is the right subtree. For the left subtree, we print the leftmost edges from top to bottom. Then we print its leaves from left to right. For the right subtree, we print its leaves from left to right, then its rightmost edges from bottom to top.

Printing the leaves from left to right order is a classic example of depth-first traversal. If you are not familiar with depth-first traversal, you should attempt other questions such as Maximum Height of a Binary Tree, Populating Next Right Pointers in Each Node. How do you know if a node is a leaf? Easy, if the node does not have both left and right children.

Printing the leftmost edges is just a trivial addition to the depth-first traversal. When a node is a leftmost edge, then its left child must also be a leftmost edge. We could use a variable to pass this information down the tree. Please note that you must add the condition to avoid printing the node twice (a node could be a leftmost edge as well as a leaf node).

Printing the rightmost edges from bottom to top is easy if you realize the trick of manipulating recursion as a stack. Try relate this with how post-order traversal works. When calling recursive functions, function calls are pushed onto a stack, and therefore you could use the implicit stack to your advantage. This trick is especially handy when applied in situation where you need to reverse the order of operations. See my post: Recursion to the Rescue! and Reversing Linked List Iteratively and Recursively for more practice using this trick.

This solution works whether the tree itself is complete or not.

void printLeftEdges(BinaryTree *p, bool print) {
    if (!p) return;
    if (print || (!p->left && !p->right))
        cout << p->data << " ";
    printLeftEdges(p->left, print);
    printLeftEdges(p->right, false);
}

void printRightEdges(BinaryTree *p, bool print) {
    if (!p) return;
    printRightEdges(p->left, false);
    printRightEdges(p->right, print);
    if (print || (!p->left && !p->right))
        cout << p->data << " ";
}

void printOuterEdges(BinaryTree *root) {
    if (!root) return;
    cout << root->data << " ";
    printLeftEdges(root->left, true);
    printRightEdges(root->right, true);
}

Further Thoughts:
Please note that the above problem statement does not give a clear definition of "left-most" node. Thanks to my dear readers who pointed out this ambiguity, which I didn't consider earlier in my above solution.

For example, consider the binary tree below: Is node 8 a left-most node?

    _______________28_______________
   /                                \
  4____                        ____69
       \                      /
      __8__                __56__
     /     \              /      \
  __7     12__        __34    __27__
 /            \      /       /      \
 5_          _13    _2      _3      39
   \        /      /       /
    6      11     10       9

The above code prints: 28, 4, 6, 11, 10, 9, 39, 69.

It seems that nodes 8, 7, and 5 should be left-most nodes as well, but are not printed by the above code. This is because we made an implicit assumption that all left-most nodes could only be reached by following each node's left branch (similar for right-most nodes).

To remedy this, we use a modified recursive definition for left-most node (similar for right-most node):

• If a node is a left-most node, then its left child must be a left-most node as well.
• If its left child does not exist, then its right child will be a left-most node.

The below code prints the correct output of: 28, 4, 8, 7, 5, 6, 11, 10, 9, 39, 27, 56, 69.

All that are needed is just two lines of code changes. (line 6 and line 11)

void printLeftEdges(BinaryTree *p, bool print) {
    if (!p) return;
    if (print || (!p->left && !p->right))
        cout << p->data << " ";
    printLeftEdges(p->left, print);
    printLeftEdges(p->right, print && !p->left);
}

void printRightEdges(BinaryTree *p, bool print) {
    if (!p) return;
    printRightEdges(p->left, print && !p->right);
    printRightEdges(p->right, print);
    if (print || (!p->left && !p->right))
        cout << p->data << " ";
}

void printOuterEdges(BinaryTree *root) {
    if (!root) return;
    cout << root->data << " ";
    printLeftEdges(root->left, true);
    printRightEdges(root->right, true);
}

Note: Some readers claimed that the above algorithm does not always print all edge nodes. For example, by moving node 5 to be the left child of node 12, we get the binary tree below:

   _______________28_______________
  /                                \
  4___                         ____69
      \                       /
    ___8__                 __56__
   /      \               /      \
   7    __12___        __34    __27__
       /       \      /       /      \
      5_      _13    _2      _3      39
        \    /      /       /
         6  11     10       9

And the algorithm in the Further Thoughts section prints the following: 28, 4, 8, 7, 6, 11, 10, 9, 39, 27, 56, 69.

Some readers argued that node 5 should be printed too. However, if you read the definition of "left-most node" carefully in the above section, you would agree with me that node 5 is not a left-most node. This is because node 8 (which is a left-most node) has a left child, node 7. Therefore, node 7 is a left-most node but not node 12. As a result, all descendants of node 12 must not be left-most nodes.

You could use your own definition of left-most node as you pleased, but keep in mind that the problem statement is ambiguous to start with, so communicating this with your interviewer will be your best bet.