Practice › Trees
Inorder Traversal
Easy · Trees · Asked at Amazon, Microsoft, Google, TCS, Infosys
Print the inorder traversal (left, root, right) of the binary tree.
Input
First line: k. Second line: k values — the tree in level order, -1 means no node.
Output
The values in inorder, space-separated.
Constraints
- 1 ≤ number of nodes ≤ 10^4
Example 1
Input
4 1 -1 2 3
Output
1 3 2
Example 2
Input
7 4 2 6 1 3 5 7
Output
1 2 3 4 5 6 7
Hints
- Inorder = traverse the left subtree, visit the node, traverse the right subtree.
- Iterative version: push nodes while going left; pop one, visit it, then move to its right child.
Approach
The recursive version is three lines. The iterative version, often asked in interviews, uses an explicit stack. Go as far left as possible, pushing each node. Pop a node, output it, then repeat from its right child. The solutions below use the iterative form, so a deep tree can't overflow the call stack.
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 *cur = readTree();
stack<Node *> st;
vector<long long> out;
while (cur || !st.empty()) {
while (cur) {
st.push(cur);
cur = cur->left;
}
cur = st.top();
st.pop();
out.push_back(cur->val);
cur = cur->right;
}
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
class Node:
def __init__(self, val):
self.val, self.left, self.right = val, None, None
def read_tree():
"""Build a tree from level order where -1 means "no node"."""
data = list(map(int, sys.stdin.read().split()))
k, v = data[0], data[1 : data[0] + 1]
if not v or v[0] == -1:
return None
root = Node(v[0])
q, i = deque([root]), 1
while q and i < k:
cur = q.popleft()
if i < k and v[i] != -1:
cur.left = Node(v[i])
q.append(cur.left)
i += 1
if i < k and v[i] != -1:
cur.right = Node(v[i])
q.append(cur.right)
i += 1
return root
cur, stack, out = read_tree(), [], []
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
out.append(cur.val)
cur = cur.right
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 cur = readTree(new Scanner(System.in));
ArrayDeque<Node> st = new ArrayDeque<>();
StringBuilder sb = new StringBuilder();
while (cur != null || !st.isEmpty()) {
while (cur != null) {
st.push(cur);
cur = cur.left;
}
cur = st.pop();
sb.append(sb.length() > 0 ? " " : "").append(cur.val);
cur = cur.right;
}
System.out.println(sb);
}
}