Untitled

 avatar
unknown
plain_text
2 months ago
4.9 kB
2
Indexable
Here’s the recursive implementation of the `addLeftBoundary` method to match the recursive style used for `addRightBoundary`. 

### Recursive `addLeftBoundary`:

```java
private void addLeftBoundary(TreeNode node, List<Integer> result) {
    if (node == null || isLeaf(node)) {
        return;
    }

    // Add the current node before processing its children
    result.add(node.val);

    // Recur for the left child first, then for the right child if left is absent
    if (node.left != null) {
        addLeftBoundary(node.left, result);
    } else {
        addLeftBoundary(node.right, result);
    }
}
```

---

### Updated Full Example:

Here’s the complete `BoundaryTraversal` class with both `addLeftBoundary` and `addRightBoundary` implemented recursively:

```java
import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
        left = right = null;
    }
}

public class BoundaryTraversal {

    public List<Integer> boundaryTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        // Add root value (not a leaf)
        if (!isLeaf(root)) result.add(root.val);

        // Traverse the left boundary
        addLeftBoundary(root.left, result);

        // Traverse the leaf nodes
        addLeaves(root, result);

        // Traverse the right boundary
        addRightBoundary(root.right, result);

        return result;
    }

    private void addLeftBoundary(TreeNode node, List<Integer> result) {
        if (node == null || isLeaf(node)) {
            return;
        }

        // Add the current node before processing its children
        result.add(node.val);

        // Recur for the left child first, then for the right child if left is absent
        if (node.left != null) {
            addLeftBoundary(node.left, result);
        } else {
            addLeftBoundary(node.right, result);
        }
    }

    private void addLeaves(TreeNode node, List<Integer> result) {
        if (node == null) return;
        if (isLeaf(node)) {
            result.add(node.val);
            return;
        }
        addLeaves(node.left, result);
        addLeaves(node.right, result);
    }

    private void addRightBoundary(TreeNode node, List<Integer> result) {
        if (node == null || isLeaf(node)) {
            return;
        }

        // Recur for the right child first, then for the left child if right is absent
        if (node.right != null) {
            addRightBoundary(node.right, result);
        } else {
            addRightBoundary(node.left, result);
        }

        // Add the current node after processing its children
        result.add(node.val);
    }

    private boolean isLeaf(TreeNode node) {
        return node.left == null && node.right == null;
    }

    public static void main(String[] args) {
        // Example Tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        root.left.right.left = new TreeNode(8);
        root.left.right.right = new TreeNode(9);
        root.right.right.left = new TreeNode(10);
        root.right.right.right = new TreeNode(11);

        BoundaryTraversal bt = new BoundaryTraversal();
        List<Integer> boundary = bt.boundaryTraversal(root);
        System.out.println(boundary); // Output: [1, 2, 4, 8, 9, 10, 11, 7, 3]
    }
}
```

---

### Explanation of Recursive `addLeftBoundary`:

1. **Base Condition**:
   - The recursion stops when the current node is `null` or a leaf node.

2. **Action on Current Node**:
   - Add the current node to the `result` list since it is part of the left boundary.

3. **Recursive Call**:
   - Recur on the left child if it exists; otherwise, recur on the right child. This ensures the boundary traversal always follows the leftmost path.

---

### Output for Example Tree:

Input Tree:

```
            1
         /     \
       2         3
     /   \     /   \
    4     5   6     7
         / \         / \
        8   9      10  11
```

**Boundary Traversal**:
- Left Boundary: \( [1, 2, 4] \)
- Leaf Nodes: \( [8, 9, 6, 10, 11] \)
- Right Boundary: \( [3, 7] \) (in reverse order)

**Output**: \( [1, 2, 4, 8, 9, 6, 10, 11, 7, 3] \)

---

### Complexity:

1. **Time Complexity**:
   - \( O(n) \): Each node is visited exactly once.

2. **Space Complexity**:
   - \( O(h) \): Recursion stack space, where \( h \) is the height of the tree.
Editor is loading...
Leave a Comment