Boundary of Binary Tree Solution in Java

Ah, the Boundary of Binary Tree problem! It’s like trying to find the perimeter of your neighbor’s yard, but instead of a fence, you have a binary tree. In this problem, we’re tasked with finding the boundary nodes of a binary tree, which is a fancy way of saying we want to know which nodes are on the outer edge.

Imagine you’re at a party, and you want to know who’s standing around the edges of the room, avoiding eye contact. That’s what we’re doing here—finding the nodes that are too cool to mingle in the middle!

Solution Links

C++ Solution
Python Solution

The Code


class Solution {
  public List boundaryOfBinaryTree(TreeNode root) {
    if (root == null)
      return new ArrayList<>();
    List ans = new ArrayList<>(List.of(root.val));
    dfs(root.left, true, false, ans);
    dfs(root.right, false, true, ans);
    return ans;
  }

  private void dfs(TreeNode root, boolean lb, boolean rb, List ans) {
    if (root == null)
      return;
    if (lb)
      ans.add(root.val);
    if (!lb && !rb && root.left == null && root.right == null)
      ans.add(root.val);

    dfs(root.left, lb, rb && root.right == null, ans);
    dfs(root.right, lb && root.left == null, rb, ans);
    if (rb)
      ans.add(root.val);
  }
}

Approach Explanation

The approach here is quite straightforward, yet elegant. We use a depth-first search (DFS) to traverse the tree. The key points are:

We check if the current node is part of the left boundary or the right boundary.
If it’s a left boundary node, we add it before traversing its children (preorder). If it’s a right boundary node, we add it after traversing its children (postorder).
Leaf nodes that are not part of either boundary are added to the result as well.

Time and Space Complexity

Time Complexity: O(N), where N is the number of nodes in the binary tree. We visit each node exactly once.

Space Complexity: O(H), where H is the height of the tree. This is due to the recursion stack.

Real-World Example

Think of a tree as a family reunion. The boundary nodes are like the relatives who stand around the edges, avoiding the awkward conversations in the middle. You want to identify who those relatives are—maybe the ones who always bring the weird potato salad. By traversing the tree, we can pinpoint these boundary nodes and avoid the chaos of the inner family drama!