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.
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.
Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?
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
boundaryOfBinaryTreeinitiates the boundary extraction process by checking if the root is not a leaf and adding it to the result listself.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_leavesis 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
sis 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.
- The main function
-
is_leaf Helper Function:
- A simple utility function
is_leafdetermines whether a given node is a leaf by checking that it does not have any left or right children.
- A simple utility function
-
Recursion for Leaves Collection:
- The recursion strategy employed by
add_leavesadds the benefit of an in-depth tree traversal to find all leaves. Starting from a node, if it is a leaf node (verified via theis_leaffunction), its value is appended toself.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).
- The recursion strategy employed by
-
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.resis returned containing all boundary elements in the required order.
- Finally, after traversing the left boundary, adding leaves, and using the stack for the right boundary, the complete boundary list
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.
What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?
Example Walkthrough
Consider a binary tree that looks like the following:
1 1 2 / \ 3 2 3 4 / \ \ 54 5 6
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.reswhich 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 listself.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, andself.resbecomes [1, 2, 4, 5, 6]. -
Right Boundary: We then move to the root's right child (3). Node 3 goes into a temporary stack
sbecause it's a non-leaf on the right. We've now exhausted all nodes, so we begin popping from the stackswhich has [3]. After popping,self.resis 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
661/**
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}
1041#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}
811// 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};
70What is the space complexity of the following code?
1int sum(int n) {
2 if (n <= 0) {
3 return 0;
4 }
5 return n + sum(n - 1);
6}
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.
Consider the classic dynamic programming of longest increasing subsequence:
Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is
[3, 7, 40, 80].
What is the recurrence relation?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.