🙏

জয়  শ্রী  রাম

🕉

---

Boundary of Binary Tree

Given a binary tree, return the values of its boundary in anti-clockwise 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 left-most node. Right boundary is defined as the path from root to the right-most 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 left-most 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 right-most 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 anti-clockwise direction means you should output reversed right boundary. So order them in anti-clockwise 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 left-most 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 right-most node). So order them in anti-clockwise without duplicate nodes we have [1,2,4,7,8,9,10,6,3].

Solution:

This is definitely a non-trivial 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:

1. left most boundary in top-down direction,
2. all the leaf nodes from left to right,
3. right most boundary in bottom-up 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 non-trivial 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 non-null left child node then the left node becomes part of the left boundary,
  but if a node on left boundary does not have a non-null left node but has a non-null right node then the right node becomes part of the left boundary.
  
  
• Finding right boundary is also non-trivial and could be challenging. We would be computing right boundary top-down (because that is what Preorder Traversal does) and then reverse the path to get the path bottom-up.
  If you are already on the right boundary then for any node on the right boundary: if the node has a non-null right child node then the right node becomes part of the right boundary,
  but if a node on right boundary does not have a non-null right node but has a non-null 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₂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: