Similar Problems
Similar Problems not available
Boundary Of Binary Tree  Leetcode Solution
LeetCode: Boundary Of Binary Tree Leetcode Solution
Difficulty: Medium
Topics: tree binarytree depthfirstsearch
The problem "Boundary of Binary Tree" on LeetCode asks us to find and return the boundary of a binary tree in anticlockwise direction starting from root.
We can solve this problem using a combination of three subproblems:
 Finding the left boundary of the binary tree
 Finding the right boundary of the binary tree
 Finding the leaf nodes of the binary tree
We will create three helper functions for these subproblems and call them in the main function to get the final solution.

Finding the left boundary of the binary tree: We can find the left boundary of the binary tree by traversing the root node, then traversing all the left nodes until we reach a leaf node. At each node, we check if it has a left child. If it has a left child, we move to that child and add the current node value to the result list. If it doesn't have a left child, we move to the right child and continue the traversal.

Finding the right boundary of the binary tree: We can find the right boundary of the binary tree by traversing the root node, then traversing all the right nodes until we reach the leaf node. At each node, we check if it has a right child. If it has a right child, we move to that child and add the current node value to the result list. If it doesn't have a right child, we move to the left child and continue the traversal.

Finding the leaf nodes of the binary tree: We can find the leaf nodes of the binary tree using depthfirst search. We traverse the left child, then the right child until we reach a leaf node. We add the leaf node's value to the result list.
Now, we can combine these three functions to get the final solution. We add the root node's value to the result list, then call the three subproblems in the following order:
 Find the left boundary of the binary tree, starting from the root's left child.
 Find the leaf nodes of the binary tree.
 Find the right boundary of the binary tree, starting from the root's right child in reverse order.
Finally, we concatenate these three lists and return the result.
Here is the Python implementation of the solution:
class Solution:
def boundaryOfBinaryTree(self, root: TreeNode) > List[int]:
if not root:
return []
res = [root.val]
self.leftBoundary(root.left, res)
self.leaves(root, res)
self.rightBoundary(root.right, res)
return res
def leftBoundary(self, node, res):
if not node or (not node.left and not node.right):
return
res.append(node.val)
if node.left:
self.leftBoundary(node.left, res)
else:
self.leftBoundary(node.right, res)
def rightBoundary(self, node, res):
if not node or (not node.left and not node.right):
return
if node.right:
self.rightBoundary(node.right, res)
else:
self.rightBoundary(node.left, res)
res.append(node.val)
def leaves(self, node, res):
if not node:
return
if not node.left and not node.right:
res.append(node.val)
return
self.leaves(node.left, res)
self.leaves(node.right, res)
Overall, the time complexity of this solution is O(n) where n is the number of nodes in the binary tree as we traverse every node once. The space complexity is also O(n) in the worstcase scenario when the tree is completely unbalanced and resembles a linked list.
Boundary Of Binary Tree Solution Code
1