Workspace

Problem workspace

3 day streakD

Boundary Traversal

MediumTreesViews

The challenge

Return the anti-clockwise boundary, beginning at the root, without repeating nodes.

Convention: root, non-leaf left boundary, all leaves left to right, then reversed non-leaf right boundary.

Example

Balanced example: [8, 4, 2, 6, 10, 14, 12]. Right chain: [3, 1, 2].

Use the walkthrough below to inspect the input and each state change.

See Boundary, step by step

Follow the branches. Watch the state change.

7 input nodesL = left · R = right
Inspect the input.Labels identify node objects; numbers are their values. Left and right child pointers define the tree. Node labels identify objects; numbers show their values. The pointer table below provides the same structure in text.LRLRLR2D4B6E8A · root10F12C14G
CurrentProcessedPending
View child pointers & node state
Node state · null means no child
NodeValueLeftRightState
A8BC—
B4DE—
C12FG—
D2nullnull—
E6nullnull—
F10nullnull—
G14nullnull—
Step 01 / 10

Inspect the input.

Labels identify node objects; numbers are their values. Left and right child pointers define the tree.

root = A:8
View original input

A:8 [L:B, R:C] · B:4 [L:D, R:E] · C:12 [L:F, R:G] · D:2 [L:null, R:null] · E:6 [L:null, R:null] · F:10 [L:null, R:null] · G:14 [L:null, R:null]

Node IDs stay distinct even when values repeat. Pointer mutations update the diagram; removed nodes remain in the state table for reference.

Put it into code

Assign each boundary node to exactly one phase.

Nodes store value, left, and right. C++ uses C++17 or later.

from collections import deque

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def boundary(root):
    if root is None:
        return []
    def leaf(node):
        return node.left is None and node.right is None
    out = [root.value]
    if leaf(root):
        return out
    node = root.left
    while node:
        if not leaf(node):
            out.append(node.value)
        node = node.left if node.left else node.right
    def leaves(node):
        if node is None:
            return
        if leaf(node):
            out.append(node.value)
        else:
            leaves(node.left)
            leaves(node.right)
    leaves(root.left)
    leaves(root.right)
    right, node = [], root.right
    while node:
        if not leaf(node):
            right.append(node.value)
        node = node.right if node.right else node.left
    out.extend(reversed(right))
    return out

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap