545. Boundary of Binary Tree - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
Given a binary tree, return the values of its boundary in an anti-clockwise direction starting from the root. The boundary includes three parts:

Left Boundary: The nodes on the path from the root to the left-most node (excluding leaf nodes).
Leaves: All the leaf nodes from left to right.
Right Boundary: The nodes on the path from the root to the right-most node (excluding leaf nodes), added in reverse order.

The root should be included in the boundary. Duplicate nodes (appearing in both left/right boundary and leaves) should only be included once.

Examples:

Example 1:

Input:
```
    1
   / \
  2   3
 / \  / \
4   5 6  7
     \
      8
```
Output:
```
[1, 2, 4, 8, 6, 7, 3]
```
Explanation:
- Left Boundary: [1, 2] (node 2 is the left boundary since 4 is a leaf).
- Leaves: [4, 8, 6, 7]
- Right Boundary: [3] (in reverse order, node 3 is added after the leaves).
- Combining these gives: [1, 2, 4, 8, 6, 7, 3].
Example 2:

Input:
```
    1
     \
      2
     / \
    3   4
```
Output:
```
[1, 3, 4, 2]
```
Explanation:
- Left Boundary: [1] (since there is no left subtree).
- Leaves: [3, 4]
- Right Boundary: [2] (in reverse order).
- The final boundary is: [1, 3, 4, 2].
Example 3:

Input:
```
    1
   /
  2
 /
3
```
Output:
```
[1, 2, 3]
```
Explanation:
- Left Boundary: [1, 2] (3 is a leaf and should be added only once).
- Leaves: [3]
- Right Boundary: [] (no right boundary exists).
- Combined: [1, 2, 3].

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].
Each node's value is between -1000 and 1000.

Hints Before Diving into the Solution

Hint 1:
Consider breaking down the boundary into three distinct parts: left boundary, leaves, and right boundary. How can you define each part clearly using tree traversal?
Hint 2:
When traversing, be careful not to duplicate leaf nodes. Ensure that nodes that appear as part of the left or right boundary and are also leaves are added only once.

Approaches

Approach 1: Recursive DFS (Divide and Conquer)

Idea:

Left Boundary:
Traverse from the root's left child down to the left-most node. For each node encountered (except the leaves), add its value.
Leaves:
Perform a DFS traversal (inorder or preorder) on the entire tree. Add the node’s value if it is a leaf.
Right Boundary:
Traverse from the root's right child down to the right-most node. For each node encountered (except the leaves), add its value to a temporary list. Then reverse this list and append it to the result.

Detailed Steps:

Step 1: Start with the root (always add it unless it is the only node).
Step 2: For the left boundary, traverse starting from root.left and add nodes (skip if it is a leaf).
Step 3: For the leaves, traverse the entire tree and add every leaf node.
Step 4: For the right boundary, traverse starting from root.right and add nodes (skip if it is a leaf). Reverse the collected list before appending.
Step 5: Combine these three parts to form the final boundary list.

Visual Example:

Consider the following tree:

Left Boundary: Starting from node 2 (child of 1) → Add [2]. Node 4 is a leaf, so stop.
Leaves: All leaves from left to right are [4, 7, 6].
Right Boundary: Starting from node 3 (child of 1) → Add [3] (6 is a leaf, so not added in the right boundary). Reverse right boundary remains [3].
Final Boundary: [1, 2, 4, 7, 6, 3].

Approach 2: Iterative Traversal (Using Stacks or Queues)

Idea:

Iterative Left and Right Boundaries:
Use loops to traverse the left boundary and the right boundary iteratively.
Leaf Collection:
Perform an iterative or recursive traversal to collect all the leaves.
Combine:
Merge the three lists appropriately (and reverse the right boundary list before appending).

Pros and Cons:

DFS Recursive Approach:
- Pros: Simple, clear structure by dividing the problem into subproblems.
- Cons: May face stack overflow on very deep trees.
Iterative Approach:
- Pros: Avoids recursion and potential stack overflow.
- Cons: Might require extra space for stacks/queues and can be more complex to implement.

Code Implementation

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time Complexity:
- In the worst case, every node is visited at least once during the DFS traversals for left boundary, leaves, and right boundary. Hence, the time complexity is O(N), where N is the number of nodes in the tree.
Space Complexity:
- The extra space is mainly used for the recursion stack and the output list. In the worst-case scenario (skewed tree), the recursion depth can be O(N). Therefore, the space complexity is O(N).

Step-by-Step Walkthrough & Visual Example

Consider the tree from Example 1:

Root:
- Start with the root node (1). Since 1 is not a leaf, add it to the result.
Left Boundary:
- Start from root.left (node 2). Node 2 is added because it is not a leaf.
- Next, from node 2, move to its left child (node 4). Since node 4 is a leaf, stop adding the left boundary here.
Leaves:
- Perform a full traversal:
  - Node 4 (leaf) → add 4.
  - Traverse node 5 and its right child: Node 7 is a leaf → add 7.
  - Traverse right subtree: Node 6 (leaf) → add 6.
Right Boundary:
- Start from root.right (node 3). Node 3 is added (it is not a leaf).
- Move to node 3’s right child (node 6) is a leaf, so stop.
- Reverse the right boundary list (in this case, [3] remains unchanged).
Combine Parts:
- Final boundary: [1 (root), 2 (left boundary), 4, 7, 6 (leaves), 3 (right boundary in reverse)] → [1, 2, 4, 7, 6, 3].

Common Mistakes

Duplication of Leaves:
Accidentally adding a leaf that already appears in the left or right boundary can lead to duplicate values.
Boundary Conditions:
Not handling trees that have only left or only right subtrees can cause errors.
Incorrect Order:
The order of the right boundary must be reversed before merging with the rest of the boundary.

Edge Cases & Alternative Variations

Edge Case 1:
A tree with only a root node. In this case, the boundary is just the root.
Edge Case 2:
Trees where either the left or right subtree is missing. The solution must correctly handle missing boundaries.
Alternative Variation:
Instead of outputting the boundary values, you might be asked to output the nodes themselves or to format the boundary in a specific order (e.g., clockwise).

Binary Tree Inorder/Preorder/Postorder Traversal:
These problems help practice tree traversal techniques.
Serialize and Deserialize Binary Tree:
Learn to convert a tree structure into a string and vice versa.
Sum of Left Leaves:
Practice identifying and processing left leaf nodes.
Zigzag Level Order Traversal:
Another variation of tree traversal with different ordering rules.

545. Boundary of Binary Tree - Detailed Explanation

Problem Statement

Hints Before Diving into the Solution

Approaches

Approach 1: Recursive DFS (Divide and Conquer)

Idea:

Detailed Steps:

Visual Example:

Approach 2: Iterative Traversal (Using Stacks or Queues)

Idea:

Pros and Cons:

Code Implementation

Python Code

Java Code

Complexity Analysis

Step-by-Step Walkthrough & Visual Example

Common Mistakes

Edge Cases & Alternative Variations

Related Problems for Further Practice