Getting everything ready for you…

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

0s

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

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

  1. Inorder = traverse the left subtree, visit the node, traverse the right subtree.
  2. 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);
    }
}

Solve Inorder Traversal online · All practice problems