Getting everything ready for you…

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

0s

Practice › Trees

Preorder Traversal

Easy · Trees · Asked at Amazon, Microsoft, Google, Adobe, Flipkart

Print the preorder traversal of the binary tree: node, then left subtree, then right subtree.

Input

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

Output

The node values in preorder, space-separated.

Constraints

Try the iterative version with a stack: pop a node, print it, push its right child, then its left child.

Example 1

Input

4
1 -1 2 3

Output

1 2 3

Example 2

Input

7
1 2 3 4 5 6 7

Output

1 2 4 5 3 6 7

Hints

  1. Preorder visits the node first, then the left subtree, then the right subtree.
  2. Iteratively: pop a node from a stack, print it, then push its right child and then its left child (so the left one is processed first).

Approach

The recursive version is three lines. The iterative one avoids deep recursion: start with the root on a stack; repeatedly pop, output, and push the right child before the left child, because a stack is last-in-first-out.

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;
}

int main() {
    Node *root = readTree();
    vector<long long> out;
    stack<Node *> st;
    if (root) st.push(root);
    while (!st.empty()) {
        Node *n = st.top();
        st.pop();
        out.push_back(n->val);
        if (n->right) st.push(n->right);
        if (n->left) st.push(n->left);
    }
    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 :]

out, st = [], [root] if root else []
while st:
    n = st.pop()
    out.append(n.val)
    if n.right:
        st.append(n.right)
    if n.left:
        st.append(n.left)
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;
    }

    public static void main(String[] args) {
        Node root = readTree(new Scanner(System.in));
        StringBuilder sb = new StringBuilder();
        Deque<Node> st = new ArrayDeque<>();
        if (root != null) st.push(root);
        while (!st.isEmpty()) {
            Node n = st.pop();
            sb.append(sb.length() > 0 ? " " : "").append(n.val);
            if (n.right != null) st.push(n.right);
            if (n.left != null) st.push(n.left);
        }
        System.out.println(sb);
    }
}

Solve Preorder Traversal online · All practice problems