Boundary Traversal of Binary Tree – Detailed Explanation

You are given the root of a binary tree. Your task is to return the boundary traversal of the tree in anticlockwise order starting from the root.

The boundary traversal should include:

1. Root node (only if it is not a leaf).
2. Left boundary (top to bottom, excluding leaves).
3. All leaf nodes (from left to right).
4. Right boundary (bottom to top, excluding leaves).

Here’s the [Problem Link] to begin with.

Example

Example 1

Input:
        20
       /  \
      8    22
     / \     \
    4  12     25
       / \
      10 14

Output: 20 8 4 10 14 25 22

Example 2

Input:
        1
         \
          2
           \
            3
             \
              4

Output: 1 4 3 2

Intuition and Approach

We can break down the traversal into three parts:

1. Left boundary (excluding leaves):
   • Start from the root’s left child.
   • Keep moving left if possible, otherwise right.
   • Stop at leaves.
2. Leaves (from left to right):
   • Perform a DFS traversal.
   • Add a node if it is a leaf (no children).
3. Right boundary (excluding leaves):
   • Start from the root’s right child.
   • Keep moving right if possible, otherwise left.
   • Stop at leaves.
   • Collect nodes and reverse them because we want bottom → top order.

Finally, concatenate all three parts with the root.

Code Implementation

class Solution:
    def is_leaf(self, node):
        if node != None and node.left == None and node.right == None:
            return True
        return False

    # Left boundary (excluding leaves) O(H)
    def add_left_boundary(self, node, ans):
        cur = node
        while cur:
            if not self.is_leaf(cur):
                ans.append(cur.data)
            if cur.left:
                cur = cur.left
            else:
                cur = cur.right

    # Leaves (left to right) O(N)
    def add_leaves(self, node, ans):
        if not node:
            return
        if self.is_leaf(node):
            ans.append(node.data)
            return
        self.add_leaves(node.left, ans)
        self.add_leaves(node.right, ans)

    # Right boundary (excluding leaves), reversed later O(H)
    def add_right_boundary(self, node, ans):
        cur = node
        stack = []
        while cur:
            if not self.is_leaf(cur):
                stack.append(cur.data)
            if cur.right:
                cur = cur.right
            else:
                cur = cur.left
        while stack:
            ans.append(stack.pop())

    def boundaryTraversal(self, root):
        if not root:
            return []

        ans = []
        if not self.is_leaf(root):
            ans.append(root.data)

        self.add_left_boundary(root.left, ans)
        self.add_leaves(root, ans)
        self.add_right_boundary(root.right, ans)

        return ans

Code Explanation

1. is_leaf(node): Returns True if node has no left or right child.
2. add_left_boundary(node, ans):
   • Traverse down the left boundary.
   • Add nodes that are not leaves.
   • Move left if possible, otherwise right.
3. add_leaves(node, ans):
   • Recursively traverse the whole tree.
   • Append nodes that are leaves.
4. add_right_boundary(node, ans):
   • Traverse down the right boundary and collect nodes (excluding leaves) in a stack.
   • Pop from stack to add nodes in reverse order.
5. boundaryTraversal(root):
   • Add the root (if it is not a leaf).
   • Collect left boundary.
   • Collect leaves.
   • Collect right boundary.
   • Return the combined result.

Dry Run Example

For the first tree:

        20
       /  \
      8    22
     / \     \
    4  12     25
       / \
      10 14

• Root: 20
• Left boundary: 8 → 4
• Leaves: 4, 10, 14, 25
• Right boundary: 22

Final result: [20, 8, 4, 10, 14, 25, 22]

Time and Space Complexity

• Time Complexity:
  • Left boundary: O(H) where H is tree height
  • Right boundary: O(H)
  • Leaves: O(N)
    Overall: O(N) where N = number of nodes.
• Space Complexity:
  • Extra stack for right boundary: O(H)
  • Recursion stack for DFS leaves: O(H)
    Worst case: O(N) for skewed trees.

Conclusion

The Boundary Traversal of Binary Tree is done in four systematic steps:

1. Add root (if not leaf).
2. Add left boundary.
3. Add all leaves (DFS).
4. Add right boundary in reverse.

This ensures the traversal is anticlockwise and avoids duplication of leaf nodes.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.