Boundary of Binary Tree

Algorithms and Data Structures: TheAlgorist.com

System Design: www.System.Design

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.io
জয় শ্রী রাম
🕉
Boundary of Binary Tree
Given a binary tree, return the values of its boundary in anticlockwise direction starting from root. Boundary includes left boundary, leaves, and right boundary in order without duplicate nodes. (The values of the nodes may still be duplicates.)
Left boundary is defined as the path from root to the leftmost node. Right boundary is defined as the path from root to the rightmost node. If the root doesn't have left subtree or right subtree, then the root itself is left boundary or right boundary. Note this definition only applies to the input binary tree, and not applies to any subtrees.
The leftmost node is defined as a leaf node you could reach when you always firstly travel to the left subtree if exists. If not, travel to the right subtree. Repeat until you reach a leaf node.
The rightmost node is also defined by the same way with left and right exchanged.
Example 1
Input: 1 \ 2 / \ 3 4
Output:
[1, 3, 4, 2]
Explanation:
The root doesn't have left subtree, so the root itself is left boundary. The leaves are node 3 and 4. The right boundary are node 1,2,4. Note the anticlockwise direction means you should output reversed right boundary. So order them in anticlockwise without duplicates and we have [1,3,4,2].
Example 2
Input:
____1_____ / \ 2 3 / \ / 4 5 6 / \ / \ 7 8 9 10
Output:
[1,2,4,7,8,9,10,6,3]
Explanation:
The left boundary are node 1,2,4. (4 is the leftmost node according to definition) The leaves are node 4,7,8,9,10. The right boundary are node 1,3,6,10. (10 is the rightmost node). So order them in anticlockwise without duplicate nodes we have [1,2,4,7,8,9,10,6,3].
Solution:
This is definitely a nontrivial problem to solve. I also think this is a good problem to be asked in a coding interview since this problem could be solved just by knowing basics of Binary tree and binary tree traversal using real logical thinking and ability to think critically in the right direction.
To start with, let's think about how the boundary of a binary tree would look like. It would consist of:
 left most boundary in topdown direction,
 all the leaf nodes from left to right,
 right most boundary in bottomup direction.
The root of the given binary tree is visited first and then we its left subtree to print the left boundary. Does it sound similar to
Preorder Traversal
? Absolutely. In fact, we would also
be able to print the leaf nodes and right boundary using Preorder traversal as you would see in below code.
We would keep three lists: one for left boundary, one for leaf nodes, one for right boundary.

Finding leaf nodes is easy. Any node we encounter which has null as both left child node and
right child node would be a leaf node.

Finding left boundary is nontrivial and could be little challenging.
If you are already on the left boundary then for any node on the left boundary: if the node has a nonnull left child node then the left node becomes part of the left boundary,
but if a node on left boundary does not have a nonnull left node but has a nonnull right node then the right node becomes part of the left boundary.

Finding right boundary is also nontrivial and could be challenging.
We would be computing right boundary topdown (because that is what Preorder Traversal does)
and then reverse the path to get the path bottomup.
If you are already on the right boundary then for any node on the right boundary: if the node has a nonnull right child node then the right node becomes part of the right boundary,
but if a node on right boundary does not have a nonnull right node but has a nonnull left node then the left node becomes part of the right boundary.

Any internal node i.e, nodes which are not part of either left boundary, right boundary or leaf nodes are
visited as part of Preorder Traversal but ignored since they are not on boundary.
Now let's see how we are going to implement the algorithm we just designed above.
Java code:
Login to Access Content
Python 2 code:
Login to Access Content
Time Complexity:
We visit root and then do preorder on root.left and root.right, which means we touch all the nodes of the given tree. The time complexity for this is O(n), where n = total number of nodes in the given tree.
Space Complexity:
Same as space complexity of Preorder Traversal. In average case space complexity = O(height of given binary tree) = O(log_{2}n).
In worst case where the given binary tree is highly skewed, height of binary tree = O(n). SO space complexity = O(height of binary tree) = O(n).
n = total number of nodes in the given binary tree.
Instructor:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.