Boundary Traversal of Binary Tree in DSA Python - Deep Dive

Overview - Boundary Traversal of Binary Tree

What is it?

Boundary Traversal of a Binary Tree is a way to visit all the nodes on the outer edge of the tree. It starts from the root, then visits the left boundary nodes top-down, all the leaf nodes left to right, and finally the right boundary nodes bottom-up. This traversal gives a list of nodes that form the 'boundary' or 'outline' of the tree.

Why it matters

Without boundary traversal, we might miss the overall shape or outline of a tree when exploring it. It helps in understanding the tree's structure from the outside, which is useful in graphical representations, tree shape analysis, and certain algorithms that need edge nodes. Without it, we would only see internal nodes or miss the tree's edges.

Where it fits

Before learning boundary traversal, you should understand basic binary trees and tree traversals like inorder, preorder, and postorder. After mastering boundary traversal, you can explore advanced tree algorithms like vertical order traversal, top view, and bottom view of trees.

Mental Model

Core Idea

Boundary traversal collects the outermost nodes of a binary tree by walking down the left edge, across the leaves, and up the right edge without repeating nodes.

Think of it like...

Imagine walking around the edge of a garden shaped like a tree. You first walk down the left fence, then along the flowers at the bottom, and finally up the right fence, seeing all the plants on the boundary without stepping inside.

        Root
         │
   ┌─────┴─────┐
 Left Boundary  Right Boundary
   │               │
Leaves (bottom row nodes)

Traversal order:
Root -> Left Boundary (top-down) -> Leaves (left to right) -> Right Boundary (bottom-up)

Build-Up - 7 Steps

1

Foundation

Understanding Binary Tree Structure

Concept: Learn what a binary tree is and how nodes connect with left and right children.

A binary tree is a structure where each node has up to two children: left and right. The top node is called the root. Nodes without children are called leaves. Example: 1 / \ 2 3 / \ \ 4 5 6 Node 1 is root, nodes 4, 5, 6 are leaves.

Result

You can identify root, internal nodes, and leaves in any binary tree.

Understanding the tree's shape and node roles is essential before traversing or collecting nodes.

2

Foundation

Basic Tree Traversals Review

Concept: Recall preorder, inorder, and postorder traversals to understand node visiting orders.

Preorder visits root first, then left subtree, then right subtree. Inorder visits left subtree, root, then right subtree. Postorder visits left subtree, right subtree, then root. Example preorder of above tree: 1 2 4 5 3 6

Result

You know how to visit all nodes in different orders.

Knowing these helps differentiate boundary traversal which visits nodes selectively on edges.

3

Intermediate

Identifying Left Boundary Nodes

🤔Before reading on: Do you think the left boundary includes leaf nodes or only internal nodes? Commit to your answer.

Concept: Left boundary nodes are those on the path from root to the leftmost leaf, excluding leaves if they will be counted separately.

Start from root's left child and keep going left if possible; if no left child, go right. Stop before leaves to avoid duplicates. For example, in the tree: 1 / \ 2 3 / \ \ 4 5 6 Left boundary nodes are 2 (since 4 is leaf, counted later).

Result

You can list left boundary nodes top-down without leaves.

Separating leaves from boundary nodes prevents duplicates and keeps traversal clean.

4

Intermediate

Collecting Leaf Nodes Left to Right

🤔Before reading on: Will leaf nodes on the left boundary be counted twice if not careful? Commit to yes or no.

Concept: Leaves are nodes without children. Collect all leaves in left-to-right order by traversing the whole tree.

Use a simple recursive traversal to check if a node is leaf (no left or right child). If yes, add it to the leaf list. In the example tree, leaves are 4, 5, 6.

Result

You get a list of all leaf nodes in order.

Collecting leaves separately ensures all bottom nodes are included regardless of boundary paths.

5

Intermediate

Identifying Right Boundary Nodes Bottom-Up

🤔Before reading on: Should right boundary nodes be collected top-down or bottom-up? Commit to your answer.

Concept: Right boundary nodes are on the path from root to the rightmost leaf, excluding leaves, collected bottom-up to maintain boundary order.

Start from root's right child and keep going right if possible; if no right child, go left. Collect nodes in a stack or list, then reverse. In the example tree, right boundary node is 3 (6 is leaf). Collecting bottom-up means output 3 after leaves.

Result

You get right boundary nodes in reverse order for final traversal.

Collecting right boundary bottom-up preserves the correct boundary traversal order.

6

Advanced

Combining All Parts for Full Boundary Traversal

🤔Before reading on: Do you think the root node is always included once or can it appear multiple times? Commit to your answer.

Concept: Combine root, left boundary, leaves, and right boundary carefully to avoid duplicates and maintain order.

Steps: 1. Add root node. 2. Add left boundary nodes (excluding leaves). 3. Add all leaf nodes. 4. Add right boundary nodes (excluding leaves) in bottom-up order. Example code snippet: class Node: def __init__(self, val): self.val = val self.left = None self.right = None def boundary_traversal(root): if not root: return [] def is_leaf(node): return not node.left and not node.right def add_left_boundary(node, res): cur = node.left while cur: if not is_leaf(cur): res.append(cur.val) if cur.left: cur = cur.left else: cur = cur.right def add_leaves(node, res): if is_leaf(node): res.append(node.val) return if node.left: add_leaves(node.left, res) if node.right: add_leaves(node.right, res) def add_right_boundary(node, res): cur = node.right stack = [] while cur: if not is_leaf(cur): stack.append(cur.val) if cur.right: cur = cur.right else: cur = cur.left while stack: res.append(stack.pop()) result = [root.val] if not is_leaf(root) else [] add_left_boundary(root, result) add_leaves(root, result) add_right_boundary(root, result) return result # Example tree: # 1 # / \ # 2 3 # / \ \ # 4 5 6 # Output: [1, 2, 4, 5, 6, 3]

Result

[1, 2, 4, 5, 6, 3]

Knowing how to combine parts without duplicates is key to correct boundary traversal.

7

Expert

Handling Edge Cases and Optimizations

🤔Before reading on: If the tree is a straight line to the left, will leaves and left boundary overlap? Commit yes or no.

Concept: Learn how boundary traversal behaves with skewed trees and optimize to avoid repeated checks.

Edge cases: - Single node tree: boundary is just root. - Left skewed tree: left boundary and leaves overlap. - Right skewed tree: right boundary and leaves overlap. Optimization: Avoid adding leaf nodes twice by checking if a node is already in boundary. Example: For a left skewed tree: 1 / 2 / 3 Boundary traversal: [1, 2, 3] Leaves and left boundary overlap, so add leaves only if not already added. This prevents duplicates and keeps traversal efficient.

Result

Boundary traversal works correctly for all tree shapes without duplicates.

Handling edge cases prevents bugs in real-world trees that are not balanced or complete.

Under the Hood

Boundary traversal works by selectively visiting nodes on the tree's edges. It uses three separate traversals: one down the left edge, one for all leaves, and one up the right edge. Internally, it avoids duplicates by excluding leaves from boundary lists and carefully ordering nodes. The traversal uses recursion or loops to navigate the tree structure, checking node properties like presence of children to decide inclusion.

Why designed this way?

This method was designed to capture the tree's outline without repetition. Earlier approaches that combined all nodes or used simple traversals missed the boundary shape or duplicated nodes. Separating left boundary, leaves, and right boundary respects the tree's geometry and ensures a clean, ordered output. It balances simplicity and correctness.

Boundary Traversal Internal Flow:

      [Root]
         │
 ┌───────┴────────┐
 │                │
Left Boundary   Right Boundary
 (top-down)     (bottom-up)
     │                │
     └───┐        ┌───┘
         │        │
       Leaves (all leaf nodes)

Traversal order:
Root -> Left Boundary -> Leaves -> Right Boundary

Myth Busters - 4 Common Misconceptions

Quick: Does the left boundary include leaf nodes? Commit yes or no.

Common Belief: Left boundary always includes all nodes on the left edge including leaves.

Reality: Left boundary excludes leaf nodes because leaves are collected separately to avoid duplicates.

Why it matters: Including leaves in left boundary causes duplicates in the final traversal list, leading to incorrect output.

Quick: Is the root node included in both left and right boundaries? Commit yes or no.

Common Belief: Root node is part of both left and right boundaries and should be added twice.

Reality: Root node is included only once at the start of traversal to avoid repetition.

Why it matters: Adding root multiple times inflates the boundary list and breaks the traversal order.

Quick: Are leaf nodes only at the bottom level of the tree? Commit yes or no.

Common Belief: Leaves are always at the lowest level of the tree.

Reality: Leaves are nodes without children and can appear at any level, not necessarily the lowest level.

Why it matters: Misunderstanding leaf position can cause missing nodes during leaf collection.

Quick: Does the right boundary get collected top-down like the left boundary? Commit yes or no.

Common Belief: Right boundary nodes are collected top-down just like left boundary nodes.

Reality: Right boundary nodes are collected bottom-up to maintain correct boundary order.

Why it matters: Collecting right boundary top-down reverses the boundary order and breaks the traversal sequence.

Expert Zone

1

Left and right boundary collections must exclude leaves to prevent duplicates, but this subtlety is often overlooked.

2

In skewed trees, boundary traversal can degenerate to simple preorder or postorder traversals, revealing its flexibility.

3

Using iterative methods with stacks for boundary parts can optimize space and avoid recursion overhead.

When NOT to use

Boundary traversal is not suitable when you need full tree traversal or specific node orders like inorder or level order. For balanced exploration or searching, use BFS or DFS instead.

Production Patterns

Boundary traversal is used in graphical tree visualizations to draw outlines, in computational geometry for shape detection, and in interview problems testing tree edge cases and traversal logic.

Connections

Graph Perimeter Detection

Boundary traversal in trees is similar to finding perimeter nodes in graphs.

Understanding boundary traversal helps in algorithms that detect outer edges or hulls in graph structures.

Image Edge Detection

Both identify outer boundaries; boundary traversal finds tree edges, edge detection finds image edges.

Knowing boundary traversal deepens understanding of how algorithms isolate outlines in different domains.

Human Visual Perception

Boundary traversal mimics how humans perceive shapes by focusing on edges and outlines.

This connection shows how computer algorithms can model natural perception processes.

Common Pitfalls

#1 Adding leaf nodes twice by including them in both left boundary and leaf collection.

Wrong approach:

def add_left_boundary(node, res):
cur = node.left
while cur:
res.append(cur.val) # Adds leaves too
if cur.left:
cur = cur.left
else:
cur = cur.right

Correct approach:

def add_left_boundary(node, res):
cur = node.left
while cur:
if not is_leaf(cur):
res.append(cur.val)
if cur.left:
cur = cur.left
else:
cur = cur.right

Root cause:

Not checking if a node is leaf before adding causes duplicates.

#2 Collecting right boundary nodes top-down instead of bottom-up.

Wrong approach:

def add_right_boundary(node, res):
cur = node.right
while cur:
if not is_leaf(cur):
res.append(cur.val) # Top-down addition
if cur.right:
cur = cur.right
else:
cur = cur.left

Correct approach:

def add_right_boundary(node, res):
cur = node.right
stack = []
while cur:
if not is_leaf(cur):
stack.append(cur.val)
if cur.right:
cur = cur.right
else:
cur = cur.left
while stack:
res.append(stack.pop()) # Bottom-up addition

Root cause:

Not reversing right boundary nodes breaks traversal order.

#3 Including root node multiple times in traversal.

Wrong approach:

result = []
add_left_boundary(root, result)
add_leaves(root, result)
add_right_boundary(root, result)
result.insert(0, root.val)
result.append(root.val) # Root added twice

Correct approach:

result = [root.val]
add_left_boundary(root, result)
add_leaves(root, result)
add_right_boundary(root, result)

Root cause:

Not managing root inclusion leads to duplicates.

Key Takeaways

Boundary traversal visits the outer edge nodes of a binary tree in a specific order: root, left boundary, leaves, then right boundary.

Separating left boundary, leaves, and right boundary nodes prevents duplicates and preserves traversal order.

Right boundary nodes must be collected bottom-up to maintain the correct sequence in the final output.

Handling edge cases like skewed trees and single-node trees ensures the traversal works for all tree shapes.

Understanding boundary traversal deepens your grasp of tree structure and selective traversal techniques.

Practice

1. What does the boundary traversal of a binary tree include?

easy

A. Left boundary, leaves, and right boundary nodes

B. Only leaf nodes

C. Only root node

D. All nodes in level order

Solution

1. Step 1: Understand boundary traversal components

   Boundary traversal includes nodes on the left edge, all leaf nodes, and nodes on the right edge of the tree.

2. Step 2: Compare options with definition

   Only Left boundary, leaves, and right boundary nodes correctly lists left boundary, leaves, and right boundary nodes.

3. Final Answer:

   Left boundary, leaves, and right boundary nodes -> Option A

4. Quick Check:

   Boundary traversal = left boundary + leaves + right boundary [OK]

Hint: Remember boundary = left edge + leaves + right edge [OK]

Common Mistakes:

• Confusing boundary traversal with level order traversal
• Ignoring leaf nodes in boundary traversal
• Including all nodes instead of just edges and leaves

2. Which of the following is the correct Python function signature for boundary traversal of a binary tree?

easy

A. def boundaryTraversal(root, result):

B. def boundaryTraversal(root, left, right):

C. def boundaryTraversal():

D. def boundaryTraversal(root):

Solution

1. Step 1: Identify typical function signature

   Boundary traversal usually takes the root node as input and returns the traversal list.

2. Step 2: Check options for correct signature

   def boundaryTraversal(root): takes only root as input, which is standard and sufficient.

3. Final Answer:

   def boundaryTraversal(root): -> Option D

4. Quick Check:

   Function signature with root only is correct [OK]

Hint: Boundary traversal function needs only root parameter [OK]

Common Mistakes:

• Adding unnecessary parameters like left and right
• Missing root parameter
• Using empty parameter list

3. What is the output of the boundary traversal for the following binary tree?

    1
   / \
  2   3
 / \   \
4   5   6
   / \  /
  7  8 9

medium

A. [1, 2, 4, 7, 8, 9, 6, 3]

B. [1, 2, 4, 7, 8, 9, 6]

C. [1, 4, 7, 8, 9, 6, 3]

D. [1, 2, 5, 7, 8, 9, 6, 3]

Solution

1. Step 1: Identify left boundary nodes

   Left boundary nodes are 1, 2, 4 (excluding leaf duplicates).

2. Step 2: Identify leaf nodes

   Leaves are 4, 7, 8, 9, 6.

3. Step 3: Identify right boundary nodes

   Right boundary nodes are 3, 6 (excluding leaf duplicates), so only 3.

4. Step 4: Combine nodes in order

   Boundary traversal = left boundary (1,2,4) + leaves (7,8,9,6) + right boundary reversed (3) = [1, 2, 4, 7, 8, 9, 6, 3]

5. Final Answer:

   [1, 2, 4, 7, 8, 9, 6, 3] -> Option A

6. Quick Check:

   Boundary traversal output matches [1, 2, 4, 7, 8, 9, 6, 3] [OK]

Hint: List left boundary, leaves, then right boundary reversed [OK]

Common Mistakes:

• Including leaf nodes twice in boundary
• Missing right boundary node 3
• Incorrect order of nodes

4. The following code attempts boundary traversal but misses some nodes. What is the bug?

def boundaryTraversal(root):
    result = []
    def leftBoundary(node):
        if node and (node.left or node.right):
            result.append(node.val)
            if node.left:
                leftBoundary(node.left)
            else:
                leftBoundary(node.right)
    def leaves(node):
        if node:
            leaves(node.left)
            if not node.left and not node.right:
                result.append(node.val)
            leaves(node.right)
    def rightBoundary(node):
        if node and (node.left or node.right):
            if node.right:
                rightBoundary(node.right)
            else:
                rightBoundary(node.left)
            result.append(node.val)
    if root:
        result.append(root.val)
        leftBoundary(root.left)
        leaves(root.left)
        leaves(root.right)
        rightBoundary(root.right)
    return result

medium

A. Leaves function misses leaf nodes on right subtree

B. Right boundary nodes are appended before recursive call

C. Left boundary includes leaf nodes causing duplicates

D. Root node is not added to result

Solution

1. Step 1: Analyze leftBoundary function

   Left boundary adds nodes with children but does not exclude leaf nodes explicitly, so leaf nodes can be added twice.

2. Step 2: Check leaves and rightBoundary functions

   Leaves function correctly adds leaf nodes; rightBoundary appends after recursion, which is correct.

3. Step 3: Identify bug

   Left boundary includes leaf nodes causing duplicates in result.

4. Final Answer:

   Left boundary includes leaf nodes causing duplicates -> Option C

5. Quick Check:

   Left boundary must exclude leaves to avoid duplicates [OK]

Hint: Exclude leaf nodes from left boundary to avoid duplicates [OK]

Common Mistakes:

• Appending right boundary nodes before recursion
• Not adding root node
• Leaves function missing some leaves

5. Given a binary tree where some nodes have only one child, how should the boundary traversal handle nodes with a single child to ensure all boundary nodes are included exactly once?

hard

A. Skip nodes with only one child in boundary traversal

B. Traverse left boundary by always choosing left child if present, else right child; similarly for right boundary, choose right child if present, else left child

C. Include all nodes regardless of position to avoid missing any

D. Only include leaf nodes and root node in boundary traversal

Solution

1. Step 1: Understand boundary traversal with single-child nodes

   When a node has only one child, boundary traversal must follow that child to include all boundary nodes.

2. Step 2: Apply traversal rules

   For left boundary, choose left child if exists; if not, choose right child. For right boundary, choose right child if exists; if not, choose left child.

3. Step 3: Avoid duplicates by excluding leaves in boundary functions

   Leaves are handled separately to avoid duplicates.

4. Final Answer:

   Traverse left boundary by always choosing left child if present, else right child; similarly for right boundary, choose right child if present, else left child -> Option B

5. Quick Check:

   Follow child presence rules to cover all boundary nodes [OK]

Hint: Choose child present on boundary side to cover all nodes [OK]

Common Mistakes:

• Skipping single-child nodes causing missing boundary nodes
• Including all nodes causing duplicates
• Ignoring leaf nodes in traversal