## Print Edge Nodes (Boundary) of a Binary Tree

October 20, 2010

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.

Thanks to one reader who contributed this interesting question.

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.

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.

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 ? true : false));
}

void printRightEdges(BinaryTree *p, bool print) {
if (!p) return;
printRightEdges(p->left, (print && !p->right ? true : 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);
}

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.

VN:F [1.9.22_1171]
Print Edge Nodes (Boundary) of a Binary Tree, 4.9 out of 5 based on 12 ratings

### 39 responses to Print Edge Nodes (Boundary) of a Binary Tree

1. Good analysis! Thank you.

VA:F [1.9.22_1171]
0
2. _30_
/ \
10 20
/ \
45 35
/ \
42 47

Just wonder, in this binary tree, is 45 an edge node? It's not on the left most path, but it seems to look like an edge.

VA:F [1.9.22_1171]
0
• I got a straightforward solution in C. Seems to handles all cases.

VA:F [1.9.22_1171]
0
3. The formatting is kinda messed-up.
I assume you meant 45 is the left child of 20, and you want to know if 45 is an edge node, right?
Yeah it does look like an edge node, and this is a good question to ask during the interview. The question is not clear enought to answer your question, unfortunately. However, it shouldn't be hard to modify the solution to adapt to the new requirements. You can pass information down the nodes as you traverse the leftmost nodes. This requirement still stay the same, that is, the child of a leftmost node must also be a leftmost node.

VA:F [1.9.22_1171]
0
4. Very decent algorithm. When I tried to attack this problem, I used sometime like.

void PrintEdge(Node* root)
{
PrintLeftEdge(root);
PrintLeaves(root);
PrintRightEdge(root->right);
}

PrintLeaves() is just DFS. So the complexity of my algorithm is overall O(n).

VA:F [1.9.22_1171]
0
5. By the way, I am also very interested in hearing different solutions for finding the least common ancestor of two nodes in a binary tree.

There could be several variations for this problem.
(1) each node can have a parent pointer.
(2) If each node doesn't have a parent, how to solve it?

Topcoder has an article telling about an advanced algorithm to solve this problem. But I don't think it is doable for an interview session.

This is a Google phone interview question for which I was asked.

VA:F [1.9.22_1171]
0
6. You raise an interesting point.
The LCA of two nodes in a BST is easy to solve. But for general binary tree it is non-trivial. Are you sure they asked this question during an interview? Even so, I believe they do not expect something like in topcoder article. Maybe a brute force approach will do?

VA:F [1.9.22_1171]
0
• Raj said on May 8, 2011

Yes. What about a BFS to find a path to the first node, and keeping the path in a queue. Now do a BFS to find a path to the second node, and when done, see which nodes are common from the saved queue

VA:F [1.9.22_1171]
0
7. Hi, you code seems could not print out the edge of this tree.

28
/ \
/ \
/ \
/ \
/ \
/ \
4 69
\ / \
8 / \
/ \ 56 233
/ \ /
7 12 34
/ \
5 13
\
6

Base on your code the output is 28 4 6 13 34 233 69

As node 8 is the right tree and also have two child, so your code does not print out its value.

Could you check?

VA:F [1.9.22_1171]
0
8. Hi, the tree is messy, But can you try to create this tree and using your code. You will see.

int data[]={28,4,69,233,4,8,4,56,34,56,7,5,6,7,4,5,6,12,13};

To resolve this, it seems you need to modify your code to be this:

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

Same for the print out of the right edge.

VA:F [1.9.22_1171]
0
9. >>As node 8 is the right tree and also have two child, so your code does not print out its value.

Are you sure node 8 is the rightmost node? That is, is it reachable by following the right child of each node from its root?

Could you specify which method you use to create the tree? Is the tree a BST or binary tree? If it is a BST, there are duplicate values in it, how do you insert those nodes in? If it is a binary tree, then you have to specify the sentinel in it.

VA:F [1.9.22_1171]
0
10. Hi, I attached the tree img on mitbbs here:

http://www.mitbbs.com/article_t/test/31181365.html

VA:F [1.9.22_1171]
0
11. Thanks, hangyu.

Your modified solution is very close to being correct. It does print the correct output for your above example.

I changed your example a little (see my updated post above) to show a counter-example. You just need to add one extra condition in your modified solution.

VA:F [1.9.22_1171]
0
12. @All:
Thanks to my kind readers who pointed out a problem with the above solution. See my update and the remedy in the "Further Thoughts" section. Thanks

VA:F [1.9.22_1171]
0
13. Why put "print ? true : false" instead of simply "print". Aren't they the same?…

VA:F [1.9.22_1171]
+1
14. No. Not sure if you understand c++ syntax.
In C++, "printLeftEdges(p->left, (print ? true : false));" simply means the following:
if (print) {
printLeftEdges(p->left, true);
} else {
printLeftEdges(p->left, false);
}

VA:F [1.9.22_1171]
0
15. @1337c0d3r:
I'm totally confused… you are actually passing variable print, which is of type bool, to function printLeftEdges(). Since you are passing by value in C++ anyway,

printLeftEdges(p->left, print);

is not equal to the following?????

if (print) {
printLeftEdges(p->left, true);
} else {
printLeftEdges(p->left, false);
}

VA:F [1.9.22_1171]
0
16. @Tracy:
Haha, you're right! I am so embarrassed for this. I don't quite understand why I would do such thing, but I believe it must have happened due to me refactoring the code.

Thanks to you for pointing this out. Above code is corrected.

VA:F [1.9.22_1171]
0
17. Quick question, what does “complete” binary tree mean in the problem statement? Is it referring to the “perfect” binary tree as defined in the wikipedia, that the number of nodes = 2^(h+1) – 1?

VA:F [1.9.22_1171]
0
• My post is assuming that a complete binary tree is a perfect binary tree. But I believe the original question defines a complete binary tree as:

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Then according to the above definition, there would be no ambiguity which is pointed out in my post. Anyway, the general solution above works whether the tree is complete or not.

VN:F [1.9.22_1171]
0
18. in your examples, they are no longer complete binary trees so I assume you are trying to solve it for general binary tree cases.

In that case, for the updated definition in further thoughts, it is possible that a right-most node is in the left sub tree as well, if there is no other nodes in the same level on its right. For example, in the images you have in Further thoughts, remove the subtree starting from node 34 and node 27. In that case, node 12 becomes a right-most node by your updated definition. The updated code would still not be able to print node 12.

More complicated, if you remove the node 56 and all its decedents, node 8 becomes both a left-most node and right-most node by your update definition. Should it be printed twice such as 4->8->7->5->6->11->13->12->8->69?

VA:F [1.9.22_1171]
0
19. an even simpler counter example, add a left node to node 4 in the image in “Further Thoughts” section. Your program will not be able to print node 7 in that case.

After trying a few things, I think in that updated definition, the only way to work with the general case would be BFS, with the help of a stack to hold on to the right-most nodes first before all leaf nodes are printed.

VA:F [1.9.22_1171]
0
20. Hi. There still is ambiguity in your updated solution. Say the root “r” has only one child, “lChild”, the left child . Suppose that the node “lChild” has two children “ll” and “lr”. Should the edge lChild->lr be counted as one of the right-most edges? If the edge is counted. Then how should the edge r–>lChild? left-most or right-most or both? print it out once or twice?

VA:F [1.9.22_1171]
0
21. Your updated solution still does not work for some case, e.g. if you put node 5 as the left child of node 12, then your updated solution can not print 5.
Here is my solution:
void printLeftEdges(Node * node, int cur_dep, int & max_dep)
{
if (!node)
return;
bool leftmost = false;
if (cur_dep>max_dep)
{
leftmost = true;
max_dep = cur_dep;
}
if (leftmost || (!node->left && !node->right))
cout<value<left, cur_dep+1, max_dep);
printLeftEdges(node->right, cur_dep+1, max_dep);
}

void printRightEdges(Node * node, int cur_dep, int & max_dep, stack & s)
{
if (!node)
return;
bool rightmost = false;
if (cur_dep>max_dep)
{
rightmost = true;
max_dep = cur_dep;
}
if (rightmost || (!node->left && !node->right))
s.push(node);
printRightEdges(node->right, cur_dep+1, max_dep,s);
printRightEdges(node->left, cur_dep+1, max_dep,s);
}

void printOuterEdges(Node * root)
{
if (!root)
return;
cout<data<left,1, left_depth);
cout<<" ";
stack s;
printRightEdges(root->right,1, right_depth, s);
while (!s.empty())
{
cout<data<<" ";
s.pop();
}
}

VA:F [1.9.22_1171]
0
• Good observation!

VA:F [1.9.22_1171]
0
• Thanks for pointing out this. I have updated my post with the “Note: section” at the end. According my own “left-most node” definition, the algorithm in “Further thoughts” section is correct. You can use whatever definition of “left-most node” as you pleased, since the problem statement is ambiguous to start with.

VN:F [1.9.22_1171]
0
22. @ihas1337code: A minor comment

The below code

printLeftEdges(p->right, (print && !p->left ? true : false)); –> line 6
printRightEdges(p->left, (print && !p->right ? true : false)); –> line 11

can be re-written as

printLeftEdges(p->right, !p->left ? print : false)); –> line 6
printRightEdges(p->left, !p->right ? print : false)); –> line 11

VA:F [1.9.22_1171]
0
23. It seems you still miss the case where the root has only right subtree. For example, if you remove the left subtree of the root node of the tree in the Further Thought section, your final code will produce 28 10 9 39 27 56 69, but according to your final definition, the correct answer should be 28 69 56 34 2 10 9 39 27 56 69. The get rid of this problem, you should whether the root has only one subtree. If so, apply printOuterEdges() to that subtree.

VA:F [1.9.22_1171]
0
24. This is my solution (in a pythonic language), though I haven’t tested it yet…

def printBoundaries(Node n, leftMost, rightMost):
if n is None:
break
elif n.left is None and n.right is None:
print n
else:
if leftMost or rightMost:
print n
if leftMost and rightMost:
printBoundaries(n.left, true, n.right is None)
printBoundaries(n.right, false, n.left is None)
else:
printBoundaries(n.left, leftMost and not rightMost, rightMost and n.right is None)
printBoundaries(n.right, leftMost and n.left is None, rightMost and not leftMost)

printBoundaries(root, true, true)

VN:F [1.9.22_1171]
0
25. 6
/
3
/ \
7 8
/
9

i think i this 8 will not print…

VA:F [1.9.22_1171]
+1
26. By “boundary” I would expect those nodes that can be seen if any one stands on left side, down side and right side of the tree. In technical terms boundary includes left view, bottom view and right view of a binary tree.

The following code prints the boundary of a binary tree.

VN:F [1.9.22_1171]
0
27. Some how the previous code was not fully printed, here is the code

VN:F [1.9.22_1171]
0
28. 1337c0d3r – what about doing a BFS and print the first and last node in each level(Of course we can track if are moving into next level while doing BFS – from your post ) And also print all the nodes of last level..?

VN:F [1.9.22_1171]
0

VA:F [1.9.22_1171]
0
30. My solution is:
(1)print root
(2)BFS the tree
(2.1) print the 1st node of each level (they are the left most nodes), and push the last node into a stack(they are the right most nodes)
(2.2) print the every node of the last level
(3) pop from the stack and print (they are the right most nodes)

VN:F [1.9.22_1171]
0
31. Just want to contribute my code.

VN:F [1.9.22_1171]
0