The boundary of a binary tree is the concatenation of the left boundary, the leaves (represented in left-to-right order), and the reverse order of the right boundary (i.e., starting from the bottom).
The left boundary is the set of nodes defined by the following:
The right boundary is similar to the left boundary, except it is the right side of the root's right subtree. Again, the leaf should not be part of the right boundary, and the right boundary should be in the reverse order. The root is also not part of the right boundary.
Given the root
of a binary tree, return the values of its boundary in a list without duplicates.
Example 1:
Input: root = [1,null,2,3,4] Output: [1,3,4,2] Explanation: - The left boundary is [1,2]. - The leaves are [3,4]. - The right boundary in reverse order is [2]. So the boundary is [1,2] + [3,4] + [2] = [1,3,4,2].
Example 2:
Input: root = [1,2,3,4,5,6,null,null,null,7,8,9,10] Output: [1,2,4,7,8,9,10,6,3] Explanation: - The left boundary is [1,2,4]. - The leaves are [7,8,9,10]. - The right boundary in reverse order is [6,3]. So the boundary is [1,2,4] + [7,8,9,10] + [6,3] = [1,2,4,7,8,9,10,6,3].
Example 3:
Input: root = [1,null,2,null,3,null,4] Output: [1,2,3,4] Explanation: - The left boundary is [1,2,3]. - The leaves are [4]. - The right boundary in reverse order is [3,2]. So the boundary is [1,2,3] + [4] + [3,2] = [1,2,3,4].
Constraints:
[1, 104]
.-1000 <= Node.val <= 1000
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force approach to finding the boundary of a binary tree involves examining every single node in the tree multiple times. We categorize each node as being part of the left boundary, right boundary, or a leaf and then print them in the correct order. This is done without any clever optimization.
Here's how the algorithm would work step-by-step:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def boundary_of_binary_tree_brute_force(root):
if not root:
return []
boundary_nodes = [root.val]
# Traverse left boundary
left_boundary_nodes = []
current_node = root.left
while current_node:
left_boundary_nodes.append(current_node.val)
if current_node.left:
current_node = current_node.left
elif current_node.right:
current_node = current_node.right
else:
break
boundary_nodes.extend(left_boundary_nodes)
# Extract leaf nodes
leaf_nodes = []
def get_leaf_nodes(node):
if not node:
return
if not node.left and not node.right:
leaf_nodes.append(node.val)
return
get_leaf_nodes(node.left)
get_leaf_nodes(node.right)
get_leaf_nodes(root)
# Ensure leaf nodes are not already in boundary
filtered_leaf_nodes = []
for leaf_node in leaf_nodes:
if leaf_node != root.val and leaf_node not in left_boundary_nodes:
filtered_leaf_nodes.append(leaf_node)
boundary_nodes.extend(filtered_leaf_nodes)
# Traverse right boundary
right_boundary_nodes = []
current_node = root.right
while current_node:
right_boundary_nodes.append(current_node.val)
if current_node.right:
current_node = current_node.right
elif current_node.left:
current_node = current_node.left
else:
break
# Reverse the right boundary
right_boundary_nodes.reverse()
# Filter right boundary nodes that were already included
filtered_right_boundary_nodes = []
for right_node in right_boundary_nodes:
if right_node != root.val and right_node not in left_boundary_nodes and right_node not in filtered_leaf_nodes:
filtered_right_boundary_nodes.append(right_node)
boundary_nodes.extend(filtered_right_boundary_nodes)
return boundary_nodes
# Example Usage (Test case 1)
# root = TreeNode(1)
# root.left = TreeNode(2)
# root.right = TreeNode(3)
# root.left.left = TreeNode(4)
# root.left.right = TreeNode(5)
# root.right.left = TreeNode(6)
# root.right.right = TreeNode(7)
# root.left.left.left = TreeNode(8)
# root.left.left.right = TreeNode(9)
# root.left.right.left = TreeNode(10)
# root.left.right.right = TreeNode(11)
# result = boundary_of_binary_tree_brute_force(root)
# print(result)
# Example Usage (Test case 2)
# root = TreeNode(1)
# root.left = TreeNode(2)
# root.left.left = TreeNode(4)
# root.left.right = TreeNode(5)
# root.right = TreeNode(3)
# result = boundary_of_binary_tree_brute_force(root)
# print(result)
# Example Usage (Test case 3)
# root = TreeNode(1)
# root.left = TreeNode(2)
# root.left.left = TreeNode(3)
# root.left.left.left = TreeNode(4)
# result = boundary_of_binary_tree_brute_force(root)
# print(result)
# Example Usage (Test case 4)
# root = TreeNode(1)
# result = boundary_of_binary_tree_brute_force(root)
# print(result)
# Example Usage (Test case 5)
# root = None
# result = boundary_of_binary_tree_brute_force(root)
# print(result)
def boundary_of_binary_tree_brute_force_test_driver():
#Test case 1
root1 = TreeNode(1)
root1.left = TreeNode(2)
root1.right = TreeNode(3)
root1.left.left = TreeNode(4)
root1.left.right = TreeNode(5)
root1.right.left = TreeNode(6)
root1.right.right = TreeNode(7)
root1.left.left.left = TreeNode(8)
root1.left.left.right = TreeNode(9)
root1.left.right.left = TreeNode(10)
root1.left.right.right = TreeNode(11)
result1 = boundary_of_binary_tree_brute_force(root1)
print(f"Test Case 1: {result1}")
#Test case 2
root2 = TreeNode(1)
root2.left = TreeNode(2)
root2.left.left = TreeNode(4)
root2.left.right = TreeNode(5)
root2.right = TreeNode(3)
result2 = boundary_of_binary_tree_brute_force(root2)
print(f"Test Case 2: {result2}")
#Test case 3
root3 = TreeNode(1)
root3.left = TreeNode(2)
root3.left.left = TreeNode(3)
root3.left.left.left = TreeNode(4)
result3 = boundary_of_binary_tree_brute_force(root3)
print(f"Test Case 3: {result3}")
#Test case 4
root4 = TreeNode(1)
result4 = boundary_of_binary_tree_brute_force(root4)
print(f"Test Case 4: {result4}")
#Test case 5
root5 = None
result5 = boundary_of_binary_tree_brute_force(root5)
print(f"Test Case 5: {result5}")
# Uncomment to run all the test cases
# boundary_of_binary_tree_brute_force_test_driver()
The goal is to trace the boundary of the tree in a specific order: left boundary, then leaves, then the right boundary in reverse order. The trick is to avoid duplicating leaf nodes that are also part of the left or right boundary.
Here's how the algorithm would work step-by-step:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def boundaryOfBinaryTree(root):
if not root:
return []
boundary = [root.val]
def leftBoundary(node):
if not node or (not node.left and not node.right):
return
boundary.append(node.val)
if node.left:
leftBoundary(node.left)
else:
leftBoundary(node.right)
def leafNodes(node):
if not node:
return
if not node.left and not node.right:
boundary.append(node.val)
return
leafNodes(node.left)
leafNodes(node.right)
def rightBoundary(node):
if not node or (not node.left and not node.right):
return
if node.right:
rightBoundaryNodes.append(node.val)
rightBoundary(node.right)
else:
rightBoundaryNodes.append(node.val)
rightBoundary(node.left)
#Add left boundary except leaf nodes.
if root.left:
leftBoundary(root.left)
#Add leaf nodes from left to right.
if root.left or root.right:
leafNodes(root)
rightBoundaryNodes = []
#Add right boundary except leaf nodes in reverse order.
if root.right:
rightBoundary(root.right)
# Reverse the right boundary nodes.
boundary.extend(rightBoundaryNodes[::-1])
return boundary
Case | How to Handle |
---|---|
Null or empty tree | Return an empty list if the root is null, as there are no boundary nodes. |
Tree with only a root node | Return a list containing only the root node's value, as it is the entire boundary. |
Tree with root and left child only | Return root, then left child (which is also a leaf). |
Tree with root and right child only | Return root, then right child (which is also a leaf). |
Skewed tree (all left or all right children) | Traverse the left boundary (or right boundary), adding nodes until a leaf is reached, then process leaves and the remaining right boundary (or left boundary). |
Perfectly balanced binary tree | Handle left boundary, then leaves, then reversed right boundary, skipping root in last two steps. |
Duplicate values in the tree | The algorithm correctly identifies boundary nodes regardless of duplicate values, as node identity is based on position in the tree, not the value. |
Large tree (potential stack overflow with recursion) | Consider iterative solutions using stacks or queues to avoid stack overflow errors in deep trees. |