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
- 1 ≤ number of nodes ≤ 10^4
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
- Preorder visits the node first, then the left subtree, then the right subtree.
- 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);
}
}