Leetcode 545. Boundary of Binary Tree

Problem Explanation

This problem is asking us to return the values of the boundary of a binary tree in anti-clockwise direction starting from the root. The boundary includes the left boundary, the leaves, and the right boundary, all in order.

The left boundary is defined as the path from the root to the left-most node, and the right boundary is defined as the path from the root to the right-most node. If the root doesn't have a left subtree or a right subtree, then the root itself is the left or right boundary.

The problem specifies that the left-most node is defined as a leaf node you could reach when you always firstly travel to the left subtree if exists. If not, travel to the right subtree. The same applies for the right-most node with left and right exchanged.

We are asked to avoid duplicate nodes in the output. However, duplicate values are allowed, since a node's values can still be duplicates.

Let's walk through an example:

Consider the following binary tree:

1
2
3    ____1_____
4   /          \
5  2            3
6 / \          / \
74   5        6   7

To solve the problem using the given guidelines, we follow this approach:

1. The left boundary nodes are 1 and 2.
2. The leaf nodes are 4, 5, 6, and 7.
3. The right boundary nodes are 1 and 3. So ordering all these nodes in anti-clockwise direction starting from root without duplicates, we get [1, 2, 4, 5, 6, 7, 3]

Solution Approach

The idea of the solution is to perform a depth-first-search (DFS) on the binary tree. While navigating the tree, we consider three flags - left boundary, right boundary, and leaf node.

Our approach would be to perform preorder traversal for the left nodes and leaf nodes, and postorder traversal for right nodes. We keep pushing the node values into our array based on these conditions. This is followed by recursion on the left child and then right child. If the tree has only one child, then that child takes its parent's boundary label.

Next, in the above approach, we need to ensure the nodes which are firstly traversed as the left or right boundary, but not leaf nodes, will not be traversed again when we try to collect the leaf nodes, to prevent duplications in the output.

Python Solution

1
2python
3class Solution:
4    def dfs(self, node, is_left, is_right, ans):
5        if not node:
6            return
7        if is_left or (not node.left and not node.right):  # preorder
8            ans.append(node.val)
9        if node.left:
10            self.dfs(node.left, is_left, is_right and not node.right, ans)
11        if node.right:
12            self.dfs(node.right, is_left and not node.left, is_right, ans)
13        if is_right or (not node.left and not node.right):  # postorder
14            ans.append(node.val)
15
16    def boundaryOfBinaryTree(self, root):
17        if not root:
18            return []
19        ans = [root.val]
20        self.dfs(root.left, True, False, ans)
21        self.dfs(root.right, False, True, ans)
22        return ans

Java Solution

1
2java
3import java.util.ArrayList;
4import java.util.List;
5
6class Solution {
7    List<Integer> ans = new ArrayList<>();
8
9    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
10        if (root != null) {
11            ans.add(root.val);
12            dfs(root.left, true, false);
13            dfs(root.right, false, true);
14        }
15        return ans;
16    }
17
18    private void dfs(TreeNode node, boolean isLeftBoundary, boolean isRightBoundary) {
19        if (node == null) return;
20
21        if (isLeftBoundary) ans.add(node.val);
22        dfs(node.left, isLeftBoundary && node.left != null, isRightBoundary && node.right == null);
23        dfs(node.right, isLeftBoundary && node.left == null, isRightBoundary && node.right != null);
24
25        if (!isLeftBoundary && !isRightBoundary && node.left == null && node.right == null) ans.add(node.val);
26        else if (isRightBoundary) ans.add(node.val);
27    }
28}

JavaScript, C++, and C# solutions will be added soon.

JavaScript Solution

1
2javascript
3class TreeNode {
4  constructor(val, left = null, right = null) {
5    this.val = val;
6    this.left = left;
7    this.right = right;
8  }
9}
10
11function boundaryOfBinaryTree(root) {
12  if (!root) return [];
13  const result = [root.val];
14  dfs(root.left, true, false, result);
15  dfs(root.right, false, true, result);
16  return result;
17}
18
19function dfs(node, isLeft, isRight, ans) {
20  if (!node) return;
21
22  if (isLeft || (!node.left && !node.right)) {
23    ans.push(node.val);
24  }
25
26  if (node.left) {
27    dfs(node.left, isLeft, false, ans);
28  }
29
30  if (node.right) {
31    dfs(node.right, false, isRight, ans);
32  }
33
34  if (!isLeft && !isRight && !node.left && !node.right) {
35    ans.push(node.val);
36  } else if (isRight) {
37    ans.push(node.val);
38  }
39}

In the JS solution, we defined a TreeNode class for the binary tree nodes. Then we implemented the boundaryOfBinaryTree function which checks if the root exists and if so, push it to the resulting array and perform dfs on both left and right child nodes.

The dfs function checks if the node exists. If it is a left boundary or a leaf node, it pushes the node value to the answer array. It then recursively calls the dfs function on the left and right child nodes with updated boundary flags. At the end, it pushes the node value to the answer array if it is either a right boundary or a leaf node.

By using a result array, we can easily keep track of the order of the boundary and leaf nodes. This solution ensures that duplicated nodes are eliminated because each node is only checked once. The left and right child nodes of each node are processed separately in the dfs function, which allows us to build up the solution from the root to the leaf nodes.