Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Trees

Boundary Traversal

Medium · Trees · Asked at Amazon, Microsoft, Samsung, Flipkart

Print the boundary of the tree anticlockwise, starting at the root, without repeating any node:

  1. The root.
  2. The left boundary: start at the root's left child and keep going to the left child (or to the right child if there is no left child), stopping before a leaf.
  3. All leaves, from left to right.
  4. The right boundary in reverse (bottom to top): defined like the left boundary, starting at the root's right child and preferring right children, excluding leaves. If the root is a leaf, print only the root.

Input

First line: k. Second line: k values — the tree in level order, -1 means no node.

Output

The boundary values, space-separated.

Constraints

Example 1

Input

11
1 2 3 4 5 6 7 -1 -1 8 9

Output

1 2 4 8 9 6 7 3

Example 2

Input

5
1 -1 2 3 4

Output

1 3 4 2

Hints

  1. Split the job into three lists: the left boundary (no leaves), all leaves left to right, the right boundary (no leaves) reversed.
  2. Walking a boundary: from the child of the root, go left if possible, else right (mirror for the right side), and stop before a leaf.

Approach

If the root is a leaf, print it alone. Otherwise output the root, then walk the left boundary from root.left (prefer left child, else right) adding every non-leaf node. Next, a DFS appends all leaves in left-to-right order. Finally walk the right boundary from root.right (prefer right, else left), collect non-leaves, and append them reversed. Leaves are only added by the leaf pass, so nothing is printed twice.

Complexity: O(n) time · O(h) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

struct Node {
    long long val;
    Node *left = nullptr, *right = nullptr;
    Node(long long v) : val(v) {}
};

// Build a tree from level order where -1 means "no node".
Node *readTree() {
    int k;
    cin >> k;
    vector<long long> v(k);
    for (auto &x : v) cin >> x;
    if (k == 0 || v[0] == -1) return nullptr;
    Node *root = new Node(v[0]);
    queue<Node *> q;
    q.push(root);
    int i = 1;
    while (!q.empty() && i < k) {
        Node *cur = q.front();
        q.pop();
        if (i < k && v[i] != -1) q.push(cur->left = new Node(v[i]));
        i++;
        if (i < k && v[i] != -1) q.push(cur->right = new Node(v[i]));
        i++;
    }
    return root;
}

vector<long long> out;
bool leaf(Node *n) { return !n->left && !n->right; }

void leaves(Node *n) {
    if (!n) return;
    if (leaf(n)) {
        out.push_back(n->val);
        return;
    }
    leaves(n->left);
    leaves(n->right);
}

int main() {
    Node *root = readTree();
    out.push_back(root->val);
    if (!leaf(root)) {
        for (Node *n = root->left; n && !leaf(n); n = n->left ? n->left : n->right) out.push_back(n->val);
        leaves(root);
        vector<long long> right;
        for (Node *n = root->right; n && !leaf(n); n = n->right ? n->right : n->left) right.push_back(n->val);
        out.insert(out.end(), right.rbegin(), right.rend());
    }
    for (size_t i = 0; i < out.size(); i++) cout << out[i] << (i + 1 < out.size() ? " " : "\n");
    return 0;
}

Python solution

import sys
from collections import deque

sys.setrecursionlimit(100000)

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


def build_tree(v):
    """Build a tree from level order where -1 means "no node"."""
    if not v or v[0] == -1:
        return None
    root = Node(v[0])
    q, i = deque([root]), 1
    while q and i < len(v):
        cur = q.popleft()
        if i < len(v) and v[i] != -1:
            cur.left = Node(v[i])
            q.append(cur.left)
        i += 1
        if i < len(v) and v[i] != -1:
            cur.right = Node(v[i])
            q.append(cur.right)
        i += 1
    return root


data = list(map(int, sys.stdin.read().split()))
k = data[0]
root = build_tree(data[1 : 1 + k])
rest = data[1 + k :]


def leaf(n):
    return not n.left and not n.right


out = [root.val]
if not leaf(root):
    n = root.left
    while n and not leaf(n):
        out.append(n.val)
        n = n.left or n.right

    def leaves(n):
        if not n:
            return
        if leaf(n):
            out.append(n.val)
            return
        leaves(n.left)
        leaves(n.right)

    leaves(root)
    right, n = [], root.right
    while n and not leaf(n):
        right.append(n.val)
        n = n.right or n.left
    out += right[::-1]
print(*out)

Java solution

import java.util.*;

public class Main {
    static class Node {
        long val;
        Node left, right;
        Node(long v) { val = v; }
    }

    // Build a tree from level order where -1 means "no node".
    static Node readTree(Scanner sc) {
        int k = sc.nextInt();
        long[] v = new long[k];
        for (int i = 0; i < k; i++) v[i] = sc.nextLong();
        if (k == 0 || v[0] == -1) return null;
        Node root = new Node(v[0]);
        ArrayDeque<Node> q = new ArrayDeque<>();
        q.add(root);
        int i = 1;
        while (!q.isEmpty() && i < k) {
            Node cur = q.poll();
            if (i < k && v[i] != -1) q.add(cur.left = new Node(v[i]));
            i++;
            if (i < k && v[i] != -1) q.add(cur.right = new Node(v[i]));
            i++;
        }
        return root;
    }

    static List<Long> out = new ArrayList<>();

    static boolean leaf(Node n) { return n.left == null && n.right == null; }

    static void leaves(Node n) {
        if (n == null) return;
        if (leaf(n)) {
            out.add(n.val);
            return;
        }
        leaves(n.left);
        leaves(n.right);
    }

    public static void main(String[] args) {
        Node root = readTree(new Scanner(System.in));
        out.add(root.val);
        if (!leaf(root)) {
            for (Node n = root.left; n != null && !leaf(n); n = n.left != null ? n.left : n.right) out.add(n.val);
            leaves(root);
            List<Long> right = new ArrayList<>();
            for (Node n = root.right; n != null && !leaf(n); n = n.right != null ? n.right : n.left) right.add(n.val);
            Collections.reverse(right);
            out.addAll(right);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < out.size(); i++) sb.append(out.get(i)).append(i + 1 < out.size() ? " " : "");
        System.out.println(sb);
    }
}

Solve Boundary Traversal online · All practice problems