Print Edge Nodes (Boundary) of a Binary Tree
October 20, 2010 in binary tree
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 41The 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | 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); } |
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.
toplanguage said on October 21, 2010
Good analysis! Thank you.
Anonymous said on October 27, 2010
_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.
Claud said on January 15, 2013
I got a straightforward solution in C. Seems to handles all cases.
1337c0d3r said on October 27, 2010
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.
Chimpanzee said on November 10, 2010
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).
Chimpanzee said on November 10, 2010
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.
1337c0d3r said on November 10, 2010
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?
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
hangyu said on November 25, 2010
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?
hangyu said on November 25, 2010
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.
1337c0d3r said on November 25, 2010
>>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.
hangyu said on November 26, 2010
Hi, I attached the tree img on mitbbs here:
http://www.mitbbs.com/article_t/test/31181365.html
1337c0d3r said on November 26, 2010
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.
1337c0d3r said on November 26, 2010
@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
Tracy said on January 25, 2011
Why put "print ? true : false" instead of simply "print". Aren't they the same?…
1337c0d3r said on January 25, 2011
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);
}
Tracy said on January 26, 2011
@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);
}
1337c0d3r said on January 26, 2011
@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.
airfang said on March 4, 2011
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?
1337c0d3r said on March 4, 2011
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.
xTristan said on May 3, 2011
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?
xTristan said on May 3, 2011
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.
codingC said on June 1, 2011
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?
xyyang said on July 15, 2011
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();
}
}
Sean said on July 17, 2011
Good observation!
1337c0d3r said on July 18, 2011
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.
Bala said on August 2, 2011
@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
jarricochen said on October 25, 2011
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.
Jon said on December 1, 2011
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)
Jon said on December 1, 2011
Oops, identation lost
Naman said on March 13, 2012
6
/
3
/ \
7 8
/
9
i think i this 8 will not print…
Naman said on March 13, 2012
left child 9 is child of 8
Venki said on April 12, 2012
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.
Venki said on April 12, 2012
Some how the previous code was not fully printed, here is the code
Balaji said on September 16, 2012
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..?
Kamal said on September 23, 2012
Elaborate solution here: http://www.ritambhara.in/print-edge-nodes-boundary-nodes-of-a-binary-tree/
Butler said on April 8, 2013
How about this>