Taro Logo

Boundary of Binary Tree

Medium
Asked by:
Profile picture
Profile picture
Profile picture
Profile picture
+5
More companies
Profile picture
Profile picture
Profile picture
Profile picture
Profile picture
25 views
Topics:
TreesRecursion

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 root node is always a part of the left boundary.
  • If a node has a left child, then the left child is part of the left boundary, and all descendants of the left child are not in the right boundary.
  • If a node does not have a left child, then the right child is part of the left boundary, and its descendants are not in the right boundary.
  • The leftmost leaf is not part of the left boundary.

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:

  • The number of nodes in the tree is in the range [1, 104].
  • -1000 <= Node.val <= 1000

Solution


Clarifying Questions

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:

  1. Can the tree be empty? If so, what should the output be?
  2. What is the expected order of nodes in the boundary? Should it be clockwise or counter-clockwise?
  3. Are node values guaranteed to be unique, or can there be duplicates?
  4. For leaf nodes, if a node is both a left boundary node and a leaf node, should it be included twice, or only once?
  5. Does the definition of 'leaf node' strictly mean nodes with both left and right children being null, or can a node with only one child also be considered a leaf node for this problem?

Brute Force Solution

Approach

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:

  1. First, we'll definitely include the root node as part of the boundary.
  2. Then, we travel down the left side of the tree as far as we can go, collecting all these nodes as part of the left boundary.
  3. Next, we travel down the right side of the tree as far as we can go, collecting all of these nodes as part of the right boundary but making sure to go from bottom to top.
  4. Finally, we go through every single node in the tree and check if it's a leaf (has no children). If it is, and if it hasn't already been included in either the left or right boundary, we add it to our list of leaf nodes.
  5. Combine the left boundary nodes, the leaf nodes and the right boundary nodes to generate our answer.

Code Implementation

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()

Big(O) Analysis

Time Complexity
O(n) – The algorithm visits each node in the binary tree multiple times, but each visit performs a constant amount of work. The left boundary traversal visits at most n nodes (where n is the total number of nodes in the tree). The right boundary traversal similarly visits at most n nodes. Identifying all leaf nodes involves traversing the entire tree, also taking O(n) time. Combining these O(n) operations results in a total time complexity of O(n).
Space Complexity
O(N) – The auxiliary space complexity is determined by the space required to store the left boundary, the right boundary, and the leaf nodes. In the worst-case scenario, where the binary tree is skewed to one side or a complete binary tree where almost all nodes are leaves, these lists could potentially store a significant portion of the nodes in the tree. Therefore, the space needed grows linearly with the number of nodes, N, where N is the total number of nodes in the binary tree. Consequently, the overall auxiliary space complexity is O(N).

Optimal Solution

Approach

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:

  1. First, take the root node as the starting point of the boundary.
  2. Next, trace the left boundary of the tree. This involves going down the left-most path until you hit a leaf node or a node without a left child.
  3. As you trace the left boundary, make sure to include each node in your list, except for leaf nodes. Leaf nodes will be handled later.
  4. Now, traverse the entire tree to identify all leaf nodes. Add these leaf nodes to your boundary list, making sure to include them in left-to-right order.
  5. Next, trace the right boundary of the tree. Start from the root's right child and go down the right-most path. Stop when you reach a leaf node or a node without a right child.
  6. Include the nodes on the right boundary in your list, but this time add them in the reverse order (bottom-up). Also, exclude leaf nodes.
  7. Finally, combine the nodes from the left boundary, the leaf nodes, and the reversed right boundary into a single list. Be careful to handle the cases where the root itself may be a leaf.

Code Implementation

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

Big(O) Analysis

Time Complexity
O(n) – The algorithm visits each node in the binary tree at most a constant number of times. Tracing the left boundary visits at most n nodes (where n is the total number of nodes). Finding the leaves also requires traversing the tree, which takes O(n) time. Tracing the right boundary similarly takes at most O(n) time. Combining these operations results in a total time complexity of O(n) + O(n) + O(n) which simplifies to O(n).
Space Complexity
O(N) – The algorithm uses auxiliary space primarily for three data structures: the list to store the left boundary, the list to store leaf nodes, and the list to store the reversed right boundary. In the worst-case scenario, a skewed tree could result in the left boundary, leaf nodes, and right boundary all containing a significant portion of the N nodes of the tree. Therefore, the space complexity is proportional to the number of nodes, N, in the tree. The recursion stack used for traversing the tree could also contribute O(H) where H is height of the tree, but in worst case (skewed tree) H = N so the main contributor is still O(N).

Edge Cases

CaseHow to Handle
Null or empty treeReturn an empty list if the root is null, as there are no boundary nodes.
Tree with only a root nodeReturn a list containing only the root node's value, as it is the entire boundary.
Tree with root and left child onlyReturn root, then left child (which is also a leaf).
Tree with root and right child onlyReturn 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 treeHandle left boundary, then leaves, then reversed right boundary, skipping root in last two steps.
Duplicate values in the treeThe 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.