545. Boundary of Binary Tree

Problem Description

The problem requires us to find the boundary of a given binary tree. The boundary is defined as the sequence of nodes that one would encounter while traversing the outer edges of the tree. Starting from the root, the boundary includes the left boundary, followed by all leaves (starting from the leftmost leaf), and then the right boundary in reverse order. The root is always considered as a boundary node unless it's the sole node in the tree. The left boundary is composed of the leftmost nodes that are not leaves, and similarly for the right boundary.

Here's the traversal breakdown:

Start at the root node (if it isn't a leaf).
Traverse the left boundary without including the leftmost leaf.
Collect all the leaves in the tree from left to right.
Traverse the right boundary in reverse order without including the rightmost leaf.

The task is to return a list containing the values of these boundary nodes, in the order they were visited.

Flowchart Walkthrough

First, let's analyze the problem using the Flowchart. Here’s a step-by-step walkthrough for leetcode 545. Boundary of Binary Tree:

Is it a graph?

Yes: A binary tree is a specific type of graph.

Is it a tree?

Yes: Specifically, this problem deals with a binary tree.

DFS

Conclusion: The flowchart points directly to using Depth-First Search (DFS) for trees. DFS is particularly suited for problems involving trees like traversing the boundary of the tree where we need to visit nodes in a specific order - pre-order traversal can be used effectively to collect the left boundary, leaf nodes, and right boundary nodes.

Intuition

To solve this problem, we must traverse the binary tree in a specific order and collect nodes to form the boundary. The solution involves several steps and checks:

First, we check if the root is not a leaf and add it to the result.
The left boundary is obtained by traversing from the root's left child down to the last non-leaf node, always preferring the left child if it exists and otherwise going to the right child.
To get all the leaves, we perform a recursive traversal of the tree. Each time we encounter a leaf, we add it to the result.
The right boundary is collected by moving down from the root's right child to the last non-leaf node. This time, we prefer the right child to the left child. Also, we collect these nodes in a stack for reverse order output later.
After the traversal, we pop elements out of the stack to add the right boundary nodes in reverse order to the result.

By these steps, we collect the boundary nodes in the correct sequence to solve the problem.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The implementation of the solution follows the intuition mentioned earlier and is broken down into a few key functions to achieve the task:

Boundary Extraction Algorithm:
- The main function boundaryOfBinaryTree initiates the boundary extraction process by checking if the root is not a leaf and adding it to the result list self.res.
- Next, it extracts the left boundary by iterating from the root's left child downwards, always preferring the left child for following. If no left child is present, it chooses the right child. Nodes verified as non-leaves are appended to the result list.
- A recursive helper function add_leaves is used to traverse the entire tree, and it adds leaf nodes' values to the result list.
- The right boundary is extracted in a similar way to the left boundary, but this time a temporary stack s is used to store the nodes' values for later reversal.
- After collecting all right boundary nodes in the stack, we pop the elements one by one and append them to our result list to maintain the reverse order required for the right boundary.
is_leaf Helper Function:
- A simple utility function is_leaf determines whether a given node is a leaf by checking that it does not have any left or right children.
Recursion for Leaves Collection:
- The recursion strategy employed by add_leaves adds the benefit of an in-depth tree traversal to find all leaves. Starting from a node, if it is a leaf node (verified via the is_leaf function), its value is appended to self.res.
- Otherwise, the function recursively calls itself on the left child (if exists), then on the right child (if exists), effectively performing a pre-order traversal (since leaves must be collected from left to right as specified in the problem).
Using Stack for Right Boundary:
- To address the requirement of adding the right boundary in reverse order, a stack data structure is introduced, which inherently reverses the order of elements as they are popped out. This approach neatly handles the reverse order without any additional logic or reverse traversal.
Constructing the Final Output:
- Finally, after traversing the left boundary, adding leaves, and using the stack for the right boundary, the complete boundary list self.res is returned containing all boundary elements in the required order.

The effective combination of iterative traversals for left and right boundaries, recursion for leaves, and stack for the reversal of the right boundary creates a comprehensive and clean solution for the boundary traversal problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider a binary tree that looks like the following:

We want to find the boundary of this tree, which includes the left boundary (nodes 1->2), leaves (nodes 4, 5, 6), and the right boundary in reverse (nodes 3, excluding the rightmost leaf node 6). Let's walk through the solution approach:

Boundary Extraction: Begin with the root node (1) which is not a leaf, so we add it to self.res. The result list now contains [1].
Left Boundary: We move to the root's left child (2). Node 2 is not a leaf, so we add it to the result list self.res which becomes [1, 2]. Node 4 is a leftmost leaf, so we stop here for the left boundary.
Leaves Collection: Starting with the root, we recursively check each node. When we reach node 4, we verify it's a leaf (using is_leaf) and add it to the list self.res, which now contains [1, 2, 4]. Next, we find node 5, which is also a leaf, so our list becomes [1, 2, 4, 5]. Finally, we visit node 6, add it to the list, and self.res becomes [1, 2, 4, 5, 6].
Right Boundary: We then move to the root's right child (3). Node 3 goes into a temporary stack s because it's a non-leaf on the right. We've now exhausted all nodes, so we begin popping from the stack s which has [3]. After popping, self.res is updated to [1, 2, 4, 5, 6, 3].
Constructing Final Output: We've visited all nodes in the desired order for a boundary traversal. The final result is the list self.res, which holds [1, 2, 4, 5, 6, 3]. Thus, we have successfully found the boundary of the binary tree.

By following the steps defined in the solution approach, we have identified nodes in the order of the left boundary, leaves from left to right, and the right boundary in reverse order, aligning with the problem's requirements.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def boundaryOfBinaryTree(self, root: TreeNode) -> List[int]:
10        # List to store the boundary values
11        boundary_values = []
12      
13        # Return empty list if the tree is empty
14        if not root:
15            return boundary_values
16      
17        # Include the root value if it is not a leaf node
18        if not self.isLeaf(root):
19            boundary_values.append(root.val)
20
21        # Process left boundary (excluding leaves and root)
22        temp = root.left
23        while temp:
24            if not self.isLeaf(temp):
25                boundary_values.append(temp.val)
26            temp = temp.left if temp.left else temp.right
27
28        # Process all leaves
29        self.addLeaves(root, boundary_values)
30
31        # Process right boundary (excluding leaves and root) in reverse order
32        stack = []
33        temp = root.right
34        while temp:
35            if not self.isLeaf(temp):
36                stack.append(temp.val)
37            temp = temp.right if temp.right else temp.left
38      
39        # Add the right boundary values to the result in the correct order
40        while stack:
41            boundary_values.append(stack.pop())
42
43        # Return the complete boundary of the binary tree
44        return boundary_values
45
46    def addLeaves(self, node: TreeNode, boundary_values: List[int]):
47        # Base case: if it is a leaf node, add to the list
48        if self.isLeaf(node):
49            boundary_values.append(node.val)
50      
51        # Recursively add left and right leaves
52        if node.left:
53            self.addLeaves(node.left, boundary_values)
54        if node.right:
55            self.addLeaves(node.right, boundary_values)
56
57    def isLeaf(self, node: TreeNode) -> bool:
58        # Check if the node is a leaf node
59        return node is not None and node.left is None and node.right is None
60```
61
62Note: This edited version of the code relies on the assumption that `List` has been imported from the `typing` module, as the original code included `List[int]` as a return type hint but did not include an import statement. If not already present in the code context, you should add the following import at the top:
63
64```python
65from typing import List
66

1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5    int val;
6    TreeNode left;
7    TreeNode right;
8  
9    TreeNode() {}
10  
11    TreeNode(int val) { 
12        this.val = val;
13    }
14  
15    TreeNode(int val, TreeNode left, TreeNode right) {
16        this.val = val;
17        this.left = left;
18        this.right = right;
19    }
20}
21
22class Solution {
23    // To keep track of the boundary nodes.
24    private List<Integer> boundaryResult;
25
26    /**
27     * Computes the boundary of a binary tree.
28     * @param root Root node of the binary tree.
29     * @return List containing the values of boundary nodes.
30     */
31    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
32        if (root == null) {
33            return Collections.emptyList();
34        }
35      
36        boundaryResult = new ArrayList<>();
37
38        // Add root if it is not a leaf node.
39        if (!isLeaf(root)) {
40            boundaryResult.add(root.val);
41        }
42
43        // Left boundary (excluding the last leaf node if any).
44        TreeNode current = root.left;
45        while (current != null) {
46            if (!isLeaf(current)) {
47                boundaryResult.add(current.val);
48            }
49            // Move to the left if possible; otherwise, move to the right.
50            current = current.left != null ? current.left : current.right;
51        }
52
53        // Add all leaf nodes.
54        addLeaves(root);
55
56        // Right boundary in reverse order (excluding the last leaf node if any).
57        Deque<Integer> stack = new ArrayDeque<>();
58        current = root.right;
59        while (current != null) {
60            if (!isLeaf(current)) {
61                stack.push(current.val);
62            }
63            // Move to the right if possible; otherwise, move to the left.
64            current = current.right != null ? current.right : current.left;
65        }
66        // Add the right boundary nodes to the result while preserving their order.
67        while (!stack.isEmpty()) {
68            boundaryResult.add(stack.pop());
69        }
70
71        // Return the complete boundary of the binary tree.
72        return boundaryResult;
73    }
74
75    /**
76     * Helper method to add leaves of the tree into boundaryResult.
77     * @param node Current node being checked for being a leaf.
78     */
79    private void addLeaves(TreeNode node) {
80        // A node is considered a leaf if it doesn't have any children.
81        if (isLeaf(node)) {
82            boundaryResult.add(node.val);
83            return;
84        }
85        // Process all left descendants.
86        if (node.left != null) {
87            addLeaves(node.left);
88        }
89        // Process all right descendants.
90        if (node.right != null) {
91            addLeaves(node.right);
92        }
93    }
94
95    /**
96     * Checks if a node is a leaf node.
97     * @param node Node to check.
98     * @return True if the node is a leaf, false otherwise.
99     */
100    private boolean isLeaf(TreeNode node) {
101        return node.left == null && node.right == null;
102    }
103}
104

1#include <vector>
2#include <stack>
3
4// Definition for a binary tree node.
5struct TreeNode {
6    int val;
7    TreeNode *left;
8    TreeNode *right;
9    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10};
11
12// Main function to calculate the boundary of the binary tree.
13std::vector<int> boundaryOfBinaryTree(TreeNode* root) {
14    std::vector<int> boundary;
15
16    // Helper function to add the left boundary of the tree.
17    auto addLeftBoundary = [&boundary](TreeNode* node) {
18        while (node) {
19            int currentValue = node->val;
20            if (node->left) {
21                node = node->left;
22            } else if (node->right) {
23                node = node->right;
24            } else {
25                break; // Leaf node, stop the iteration.
26            }
27            boundary.push_back(currentValue);
28        }
29    };
30
31    // Helper function to add the right boundary of the tree.
32    auto addRightBoundary = [&boundary](TreeNode* node) {
33        std::stack<int> stack;
34        while (node) {
35            int currentValue = node->val;
36            if (node->right) {
37                node = node->right;
38            } else if (node->left) {
39                node = node->left;
40            } else {
41                break; // Leaf node, stop the iteration.
42            }
43            stack.push(currentValue);
44        }
45        // Pop elements from stack to add them in reverse order.
46        while (!stack.empty()) {
47            boundary.push_back(stack.top());
48            stack.pop();
49        }
50    };
51
52    // Helper function to add the leaf nodes of the tree.
53    std::function<void(TreeNode*)> addLeaves = [&](TreeNode* node) {
54        if (node) {
55            if (!node->left && !node->right) {
56                boundary.push_back(node->val);
57            } else {
58                if (node->left) addLeaves(node->left);
59                if (node->right) addLeaves(node->right);
60            }
61        }
62    };
63
64    // The main processing of the boundary starts here.
65    if (root) {
66        // Add root value, it's always part of the boundary.
67        boundary.push_back(root->val);
68      
69        // Add left boundary if there is a left subtree.
70        if (root->left) addLeftBoundary(root->left);
71      
72        // Add leaves, need to check for both left and right sub trees.
73        addLeaves(root);
74      
75        // Add right boundary if there is a right subtree.
76        if (root->right) addRightBoundary(root->right);
77    }
78
79    return boundary;
80}
81

1// TypeScript type definition for a binary tree node.
2type TreeNode = {
3    val: number,
4    left: TreeNode | null,
5    right: TreeNode | null
6};
7
8/**
9 * Main function to calculate the boundary of the binary tree.
10 * @param root The root of the binary tree.
11 * @returns An array of numbers representing the boundary values of the binary tree.
12 */
13const boundaryOfBinaryTree = (root: TreeNode | null): number[] => {
14    // Helper function to determine and add the left boundary of the tree.
15    const leftBoundary = (node: TreeNode | null, boundary: number[]): void => {
16        while (node) {
17            const currentValue = node.val;
18            if (node.left) {
19                node = node.left;
20            } else if (node.right) {
21                node = node.right;
22            } else {
23                break;
24            }
25            boundary.push(currentValue);
26        }
27    };
28
29    // Helper function to determine and add the right boundary of the tree.
30    const rightBoundary = (node: TreeNode | null, boundary: number[]): void => {
31        let stack: number[] = [];
32        while (node) {
33            const currentValue = node.val;
34            if (node.right) {
35                node = node.right;
36            } else if (node.left) {
37                node = node.left;
38            } else {
39                break;
40            }
41            stack.push(currentValue);
42        }
43        while (stack.length) {
44            boundary.push(stack.pop()!);
45        }
46    };
47
48    // Helper function for adding the leaves of the tree at their respective level.
49    const levelBoundary = (node: TreeNode | null, boundary: number[]): void => {
50        if (node) {
51            levelBoundary(node.left, boundary);
52            if (!node.left && !node.right) {
53                boundary.push(node.val);
54            }
55            levelBoundary(node.right, boundary);
56        }
57    };
58
59    let boundary: number[] = [];
60
61    if (root) {
62        boundary.push(root.val);
63        if (root.left) leftBoundary(root.left, boundary);
64        if (root.left || root.right) levelBoundary(root, boundary);
65        if (root.right) rightBoundary(root.right, boundary);
66    }
67
68    return boundary;
69};
70

Time and Space Complexity

The time complexity of the provided function boundaryOfBinaryTree is O(n), where n is the number of nodes in the binary tree. This can be inferred due to the function add_leaves being a recursive call that will visit each node exactly once to check if it is a leaf. Additionally, the while loops to traverse the left and right boundaries of the tree will at most also touch each node once since they do not visit the same nodes as add_leaves.

The space complexity of this function can be primarily attributed to the space needed to store the result (self.res) and the recursion call stack when adding leaves. The list self.res and the stack s collectively can hold up to O(n) node values (where n is the number of leaves for self.res and the number of nodes in the right boundary for s). Furthermore, in the worst case of an extremely unbalanced tree, the space complexity for the recursion call stack could also reach O(n), so the total space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

It's faster

It has better space complexity

Order of computer subproblems does not matter

It has better time complexity

I don't know