We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Boundary of Binary Tree

Number: 545

Difficulty: Medium

Paid? Yes

Companies: Meta, Uber, Amazon, Nutanix, Microsoft, Snowflake, Apple, Walmart Labs, Google

Problem Description

Given the root of a binary tree, the task is to return the boundary of the tree as a list of node values. The boundary is defined as the concatenation of:

  • The root node.
  • The left boundary (excluding leaves and the root).
  • All the leaf nodes from left to right.
  • The right boundary (excluding leaves and the root) in reverse order.

The left boundary is obtained by starting from the root's left child and repeatedly moving to the left if possible (or to the right if a left child is not available), excluding the leaf nodes. Similarly, the right boundary is obtained from the root’s right child with the analogous criteria.

Key Insights

  • Break down the problem into three parts:
    • Left boundary (excluding leaves).
    • All leaves (do a DFS to find leaves).
    • Right boundary (excluding leaves, then reverse the collected list).
  • Special handling is needed when the tree doesn't have a left or right subtree.
  • The root is always included and is never considered as a leaf, even if it has no children.
  • Avoid duplication of leaf nodes in the left/right boundaries.

Space and Time Complexity

Time Complexity: O(n) – Every node is visited at most once. Space Complexity: O(n) – O(n) space is used for the output list and recursion stack (in worst case tree is skewed).

Solution

The solution uses a Depth-First Search (DFS) strategy to traverse the tree and collect the boundary nodes in three steps:

  1. For the left boundary, start at root.left and traverse down, adding nodes (skipping leaves).
  2. For the leaves, perform a DFS from the root and add any node that has no children.
  3. For the right boundary, start at root.right and traverse down, adding nodes (skipping leaves). Since the right boundary must be added in reverse order, we reverse the collected list after traversal.
  4. Finally, concatenate these lists in the order: root, left boundary, leaves, reversed right boundary.

The approach makes use of helper functions to clearly separate the logic for gathering left boundary, leaves, and right boundary. This modular approach simplifies reasoning and avoids edge case mistakes such as including duplicate leaf nodes.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def boundaryOfBinaryTree(self, root: TreeNode) -> list:
        if not root:
            return []
        
        # Check if a node is a leaf.
        def isLeaf(node):
            return node and not node.left and not node.right
        
        # Add left boundary nodes (excluding leaves).
        def addLeftBoundary(node, boundary):
            while node:
                if not isLeaf(node):
                    boundary.append(node.val)
                # Prefer left child, if not present then right child.
                if node.left:
                    node = node.left
                else:
                    node = node.right
        
        # Add leaf nodes using DFS.
        def addLeaves(node, leaves):
            if not node:
                return
            if isLeaf(node):
                leaves.append(node.val)
            else:
                addLeaves(node.left, leaves)
                addLeaves(node.right, leaves)
        
        # Add right boundary nodes in reverse order (excluding leaves).
        def addRightBoundary(node, boundary):
            temp = []
            while node:
                if not isLeaf(node):
                    temp.append(node.val)
                if node.right:
                    node = node.right
                else:
                    node = node.left
            # Append in reverse order.
            while temp:
                boundary.append(temp.pop())
        
        boundary = []
        # Add root value if it is not a leaf.
        if not isLeaf(root):
            boundary.append(root.val)
        
        addLeftBoundary(root.left, boundary)
        addLeaves(root, boundary)
        addRightBoundary(root.right, boundary)
        
        return boundary

# Example usage:
# Construct a binary tree and call boundaryOfBinaryTree(root)
← Back to All Questions