Boundary Traversal of Binary Tree

Q: What is the time complexity of boundary traversal?

O(n) . The two edge walks follow one path each, and the leaf walk visits every node once. The extra space is O(h) for the recursion or the stack.

MediumTree traversal

+10

The array root holds a binary tree in level order: the root at index 0, the children of index i at 2i+1 (left) and 2i+2 (right), -1 for an empty spot, and possibly extra -1 entries at the end. A leaf is a node with no children.

Return the boundary anticlockwise from the root:

The root.
The left boundary, top to bottom: from the root's left child, move to the left child if there is one, otherwise to the right child. Stop before a leaf.
Every leaf, from left to right.
The right boundary, bottom to top: the mirror of the left one, from the root's right child.

No node is listed twice, so a one-node tree gives only its root.

Function

boundaryTraversal(root: integer-array) → integer-array

rootinteger-array: the binary tree in level order, with -1 for an empty spot
Returnsinteger-array: the boundary values, anticlockwise from the root

Constraints

1 ≤ root.length ≤ 32767
Each root[i] is -1 or a value with 0 ≤ root[i] ≤ 10⁵.
root[0] is never -1, so the tree has at least one node.
The array may end with extra -1 entries past the last node.
Both children of an empty spot are empty too, and the depth is at most 14.
Node values are distinct.

Examples

Input: root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]
Output: [7, 3, 1, 4, 6, 8, 9]
Explanation: After the root 7, the left boundary is 3: its child 1 is a leaf. The leaves are 1, 4, 6, 8. The right boundary is 9, above the leaf 8.

Input: root = [10, 4, -1, -1, 6, -1, -1, -1, -1, 5, 8]
Output: [10, 4, 6, 5, 8]
Explanation: 4 has no left child, so the left boundary turns to 6, then stops at the leaf 5. The leaves 5, 8 follow. The root has no right child.

Follow-up

How would you list the boundary clockwise: the root, the right edge top to bottom, the leaves from right to left, then the left edge bottom to top?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The answer joins four parts: the root, a path down the left edge, the leaves from left to right, and a path down the right edge read backwards. At the joins, a leaf ending an edge and a root that is a leaf must each be listed once.

Walk the three parts separately

Intuition

Each edge is one path: from the root's child, list nodes until the next one would be a leaf, which the leaf part lists instead. A pre-order walk that goes left before right meets the leaves in left-to-right order, because every node of a left subtree lies to the left of the right subtree, whatever its depth. Collect the right edge top-down and append it reversed.

The edges follow one path each and the leaf walk visits each node once: O(n) time, with recursion h levels deep.

Algorithm

Start with the root; if it is a leaf, return it.
From index 1, while the node exists and is not a leaf, append it and move to its left child, or to its right child if there is no left one.
Walk pre-order, left first, from indexes 1 and 2, appending every leaf.
From index 2, do the same as step 2 preferring right children, collecting the nodes.
Append the collected nodes in reverse.

def boundaryTraversal(root):
    n = len(root)

    def real(i):
        return i < n and root[i] != -1

    def is_leaf(i):
        return not real(2 * i + 1) and not real(2 * i + 2)

    result = [root[0]]
    if is_leaf(0):
        return result

    # 1. The left boundary, top-down, stopping before its leaf.
    i = 1
    while real(i) and not is_leaf(i):
        result.append(root[i])
        i = 2 * i + 1 if real(2 * i + 1) else 2 * i + 2

    # 2. Every leaf: a pre-order walk meets them from left to right.
    def add_leaves(i):
        if not real(i):
            return
        if is_leaf(i):
            result.append(root[i])
            return
        add_leaves(2 * i + 1)
        add_leaves(2 * i + 2)

    add_leaves(1)
    add_leaves(2)

    # 3. The right boundary, collected top-down and added bottom-up.
    right = []
    i = 2
    while real(i) and not is_leaf(i):
        right.append(root[i])
        i = 2 * i + 2 if real(2 * i + 2) else 2 * i + 1
    result.extend(reversed(right))
    return result

One pre-order pass with edge flags

Intuition

Fold the walks into one pre-order pass on a stack by giving each node a flag: 1 on the left edge, 2 on the right edge, 0 inside. The root's children start with 1 and 2. An edge node passes its flag to the child on its side, or to its only child; every other child gets 0. In the second example the 1 passes from 4 to 6 to 5.

As nodes come off the stack, append every leaf and every non-leaf flagged 1; collect the non-leaves flagged 2 and append them reversed at the end. Pre-order reaches every left-edge node before any leaf, because the edge turns right only where nothing lies to its left.

Algorithm

Start with the root. Push its right child with flag 2, then its left child with flag 1.
Pop a node. Append it if it is a leaf or has flag 1; add a non-leaf with flag 2 to the right list.
Push its right child, then its left child, each with the flag the rule gives it.
When the stack is empty, append the right list reversed.

def boundaryTraversal(root):
    n = len(root)

    def real(i):
        return i < n and root[i] != -1

    result = [root[0]]
    right = []  # the right boundary, top-down; it goes on the end reversed
    # Each entry is (index, edge): 1 = left boundary, 2 = right boundary, 0 = inside.
    stack = []
    if real(2):
        stack.append((2, 2))
    if real(1):
        stack.append((1, 1))
    while stack:
        i, edge = stack.pop()
        has_left, has_right = real(2 * i + 1), real(2 * i + 2)
        if not has_left and not has_right:
            result.append(root[i])  # a leaf; pre-order meets them left to right
        elif edge == 1:
            result.append(root[i])  # the left boundary, top-down
        elif edge == 2:
            right.append(root[i])
        # An edge passes to the child on its own side, or to an only child.
        # The right child goes on the stack first, so the left one comes out first.
        if has_right:
            stack.append((2 * i + 2, edge if edge == 2 or not has_left else 0))
        if has_left:
            stack.append((2 * i + 1, edge if edge == 1 or not has_right else 0))
    result.extend(reversed(right))
    return result

Pitfalls and edge cases

Listing a node twice. An edge walk that does not stop before its leaf lists 1 twice in example 1, and a one-node tree must not list its root again as a leaf.
Taking each level's first node as the left boundary. If the root's left child is a leaf and the right subtree is deeper, the deeper levels start with right-subtree nodes, yet the left boundary is empty.
Following only left children. In example 2 the boundary must go from 4 to its right child 6.
Collecting leaves level by level. Example 1 then gives 1, 8, 4, 6.
In Lua and R, keep node indexes 0-based for the 2i+1 arithmetic and read root[i + 1].

Frequently asked questions3

What is the boundary traversal of a binary tree?

It lists the outline of the tree anticlockwise: the root, the left edge from top to bottom, the leaves from left to right, and the right edge from bottom to top. The edges leave out their leaves, so no node appears twice.

What is the time complexity of boundary traversal?

O(n). The two edge walks follow one path each, and the leaf walk visits every node once. The extra space is O(h) for the recursion or the stack.

Does the left boundary always follow left children?

No. It moves to the left child when there is one and to the right child otherwise: the outermost path you see from the left. If the root has no left child, the left boundary is empty.

def boundaryTraversal(root):
    # Write code here

Test #1

Test #2

Test #3

Argument

root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]

Expected Output

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