Algorithms: Tree Algorithms

Algorithms: Tree Algorithms

Explore algorithms: tree algorithms code snippets and tutorials

Algorithms: Tree Algorithms

Iterative Binary Tree Inorder in JavaScript

Inorder traversal visits each binary-tree node once without recursion..

javascript 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
"use strict";
// Iterative Binary Tree Inorder in JavaScript
//
// PURPOSE
// Inorder traversal visits each binary-tree node once without recursion.
//
// METHOD
// Keep a stack of nodes and visit states. State zero descends left, state one descends
// right, and state two exits. Emit the node at the traversal-specific state.
//
// COMPLEXITY
// O(n) time and O(n) allocated stack space; live stack usage is O(tree height).
//
// CONTRACT
// Parallel left_child and right_child arrays contain -1 or node IDs. root=-1 means empty.
// The structure must be a valid tree, not cyclic or shared. output has n entries; writes
// node IDs and returns visited count.
// Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex
// counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers.
// Sorted order, correct tree topology, and caller-owned data-structure invariants are
// preconditions; checking them on every query would change query complexity.
// Scalar and shape checks are included. Value-range checks are included where needed to
// prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000
// workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python
// uses arbitrary precision. Native allocation failures propagate. In-place outputs may be
// partly updated after arithmetic failure. These are single-threaded, in-memory
// implementations.
//
// LANGUAGE DETAILS
// Node.js 18+: Int32Array inputs and workspaces provide compact integer storage. Automatic
// lengths and checked arithmetic reject values outside signed 32-bit. Invalid inputs or
// overflow throw RangeError.
//
// EXAMPLE
// Expected return: 3.
// Expected output after call: [1, 0, 2].
// Run: node example.js
// Tests for this exact source artifact run before publication. The accompanying source
// archive includes unit cases, runtime results, and source hashes.

function alg_require(valid) { if (!valid) throw new RangeError("invalid algorithm input"); }
function alg_checked(v) { if (!Number.isInteger(v) || v < -2147483648 || v > 2147483647) throw new RangeError("32-bit result overflow"); return v; }
function alg_add(a,b) { return alg_checked(a+b); }
function alg_sub(a,b) { return alg_checked(a-b); }
function alg_mul(a,b) { return alg_checked(a*b); }
function alg_size(n) { alg_require(Number.isInteger(n) && n>=0 && n<=4000000); return n; }

function tree_inorder(left_child, right_child, root, output) {
    alg_require(left_child instanceof Int32Array);
    alg_require(right_child instanceof Int32Array);
    alg_require(Number.isInteger(root) && root >= -2147483648 && root <= 2147483647);
    alg_require(output instanceof Int32Array);
    let n = left_child.length;
    alg_require(((n >= 0) && (n <= 1000000)));
    alg_require((left_child.length == n));
    alg_require((right_child.length == n));
    alg_require((output.length == n));
    alg_require(((root >= alg_sub(0, 1)) && (root < n)));
    for (let alg_i = 0; alg_i < left_child.length; alg_i++) {
        let alg_value = left_child[alg_i];
        alg_require(((alg_value >= alg_sub(0, 1)) && (alg_value < n)));
    }
    for (let alg_i = 0; alg_i < right_child.length; alg_i++) {
        let alg_value = right_child[alg_i];
        alg_require(((alg_value >= alg_sub(0, 1)) && (alg_value < n)));
    }
    let stack = new Int32Array(alg_size(alg_add(n, 1)));
    let state = new Int32Array(alg_size(alg_add(n, 1)));
    let top = 0;
    let u = 0;
    let phase = 0;
    let count = 0;
    if ((root == alg_sub(0, 1))) {
        return 0;
    }
    stack[0] = root;
    top = 1;
    while ((top > 0)) {
        u = stack[alg_sub(top, 1)];
        phase = state[alg_sub(top, 1)];
        if ((phase == 1)) {
            output[count] = u;
            count = alg_add(count, 1);
        }
        if ((phase == 0)) {
            state[alg_sub(top, 1)] = 1;
            if ((left_child[u] != alg_sub(0, 1))) {
                stack[top] = left_child[u];
                state[top] = 0;
                top = alg_add(top, 1);
            }
        } else {
            if ((phase == 1)) {
                state[alg_sub(top, 1)] = 2;
                if ((right_child[u] != alg_sub(0, 1))) {
                    stack[top] = right_child[u];
                    state[top] = 0;
                    top = alg_add(top, 1);
                }
            } else {
                top = alg_sub(top, 1);
            }
        }
    }
    return count;
}

let left_child = new Int32Array([1, -1, -1]);
let right_child = new Int32Array([2, -1, -1]);
let root = 0;
let output = new Int32Array([0, 0, 0]);
let result = tree_inorder(left_child, right_child, root, output);
console.log(result);
// Expected output: [1, 0, 2]
console.log(Array.from(output));
Nov 15, 2026 javascript
Algorithms: Tree Algorithms

Iterative Binary Tree Inorder in Python

Inorder traversal visits each binary-tree node once without recursion..

python 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
from bisect import bisect_left

# Iterative Binary Tree Inorder in Python
#
# PURPOSE
# Inorder traversal visits each binary-tree node once without recursion.
#
# METHOD
# Keep a stack of nodes and visit states. State zero descends left, state one descends
# right, and state two exits. Emit the node at the traversal-specific state.
#
# COMPLEXITY
# O(n) time and O(n) allocated stack space; live stack usage is O(tree height).
#
# CONTRACT
# Parallel left_child and right_child arrays contain -1 or node IDs. root=-1 means empty.
# The structure must be a valid tree, not cyclic or shared. output has n entries; writes
# node IDs and returns visited count.
# Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex
# counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers.
# Sorted order, correct tree topology, and caller-owned data-structure invariants are
# preconditions; checking them on every query would change query complexity.
# Scalar and shape checks are included. Value-range checks are included where needed to
# prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000
# workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python
# uses arbitrary precision. Native allocation failures propagate. In-place outputs may be
# partly updated after arithmetic failure. These are single-threaded, in-memory
# implementations.
#
# LANGUAGE DETAILS
# Python 3.9+: automatic lengths, native lists, arbitrary-precision arithmetic, and
# bisect_left for LIS. Invalid scalar/shape inputs raise ValueError. Integer element types
# and sorted/tree invariants remain caller preconditions.
#
# EXAMPLE
# Expected return: 3.
# Expected output after call: [1, 0, 2].
# Run: python example.py
# Tests for this exact source artifact run before publication. The accompanying source
# archive includes unit cases, runtime results, and source hashes.

def alg_require(condition):
    if not condition:
        raise ValueError("invalid algorithm input; see contract")
def alg_size(n):
    alg_require(0 <= n <= 4000000)
    return n

def tree_inorder(left_child: list[int], right_child: list[int], root: int, output: list[int]) -> int:
    alg_require(isinstance(left_child, (list, tuple)) and len(left_child) <= 1000000)
    alg_require(isinstance(right_child, (list, tuple)) and len(right_child) <= 1000000)
    alg_require(type(root) is int and -2147483648 <= root <= 2147483647)
    alg_require(isinstance(output, list) and len(output) <= 1000000)
    n: int = len(left_child)
    alg_require(n >= 0 and n <= 1000000)
    alg_require(len(left_child) == n)
    alg_require(len(right_child) == n)
    alg_require(len(output) == n)
    alg_require(root >= -1 and root < n)
    for value in left_child:
        alg_require(value >= -1 and value < n)
    for value in right_child:
        alg_require(value >= -1 and value < n)
    stack: list[int] = [0] * alg_size(n + 1)
    state: list[int] = [0] * alg_size(n + 1)
    top: int = 0
    u: int = 0
    phase: int = 0
    count: int = 0
    if root == -1:
        return 0
    stack[0] = root
    top = 1
    while top > 0:
        u = stack[top - 1]
        phase = state[top - 1]
        if phase == 1:
            output[count] = u
            count += 1
        if phase == 0:
            state[top - 1] = 1
            if left_child[u] != -1:
                stack[top] = left_child[u]
                state[top] = 0
                top += 1
        elif phase == 1:
            state[top - 1] = 2
            if right_child[u] != -1:
                stack[top] = right_child[u]
                state[top] = 0
                top += 1
        else:
            top -= 1
    return count

left_child = [1, -1, -1]
right_child = [2, -1, -1]
root = 0
output = [0, 0, 0]
result = tree_inorder(left_child, right_child, root, output)
print(result)
# Expected output: [1, 0, 2]
print(output)
Nov 15, 2026 python
Algorithms: Tree Algorithms

Iterative Binary Tree Inorder in C

Inorder traversal visits each binary-tree node once without recursion..

c 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <limits.h>
#include <errno.h>
// Iterative Binary Tree Inorder in C
//
// PURPOSE
// Inorder traversal visits each binary-tree node once without recursion.
//
// METHOD
// Keep a stack of nodes and visit states. State zero descends left, state one descends
// right, and state two exits. Emit the node at the traversal-specific state.
//
// COMPLEXITY
// O(n) time and O(n) allocated stack space; live stack usage is O(tree height).
//
// CONTRACT
// Parallel left_child and right_child arrays contain -1 or node IDs. root=-1 means empty.
// The structure must be a valid tree, not cyclic or shared. output has n entries; writes
// node IDs and returns visited count.
// Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex
// counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers.
// Sorted order, correct tree topology, and caller-owned data-structure invariants are
// preconditions; checking them on every query would change query complexity.
// Scalar and shape checks are included. Value-range checks are included where needed to
// prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000
// workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python
// uses arbitrary precision. Native allocation failures propagate. In-place outputs may be
// partly updated after arithmetic failure. These are single-threaded, in-memory
// implementations.
//
// LANGUAGE DETAILS
// C99: checked calloc/free workspace, const input pointers, explicit size_t lengths. Errors
// return INT_MIN with errno=EINVAL, ERANGE, or ENOMEM. Check errno before using a result.
// Input/output arrays must not alias. No variable-length stack arrays.
//
// EXAMPLE
// Expected return: 3.
// Expected output after call: [1, 0, 2].
// Run: gcc -std=c99 -O2 example.c -o example && ./example
// Tests for this exact source artifact run before publication. The accompanying source
// archive includes unit cases, runtime results, and source hashes.

static int alg_min(int a, int b) { return a < b ? a : b; }
static int alg_max(int a, int b) { return a > b ? a : b; }
static int alg_checked(int64_t v, int *error) {
    if (v < INT_MIN || v > INT_MAX) { *error = 1; return 0; }
    return (int)v;
}
static int alg_add(int a, int b, int *e) { return alg_checked((int64_t)a+b,e); }
static int alg_sub(int a, int b, int *e) { return alg_checked((int64_t)a-b,e); }
static int alg_mul(int a, int b, int *e) { return alg_checked((int64_t)a*b,e); }

int tree_inorder(const int *left_child, size_t left_child_length, const int *right_child, size_t right_child_length, int root, int *output, size_t output_length) {
    int alg_error = 0;
    int alg_result = INT_MIN;
    errno = 0;
    int *stack = NULL;
    int *state = NULL;
    if (left_child_length > 1000000 || (left_child_length && !left_child)) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (right_child_length > 1000000 || (right_child_length && !right_child)) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (output_length > 1000000 || (output_length && !output)) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    int n = (int)left_child_length;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (!(((n >= 0) && (n <= 1000000)))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (!(((int)left_child_length == n))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (!(((int)right_child_length == n))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (!(((int)output_length == n))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (!(((root >= alg_sub(0, 1, &alg_error)) && (root < n)))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    for (int alg_i = 0; alg_i < (int)left_child_length; alg_i++) {
        int alg_value = left_child[alg_i];
        if (!(((alg_value >= alg_sub(0, 1, &alg_error)) && (alg_value < n)))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    }
    for (int alg_i = 0; alg_i < (int)right_child_length; alg_i++) {
        int alg_value = right_child[alg_i];
        if (!(((alg_value >= alg_sub(0, 1, &alg_error)) && (alg_value < n)))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    }
    {
        int alg_length = alg_add(n, 1, &alg_error);
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        if (alg_length < 0 || alg_length > 4000000) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
        stack = calloc((size_t)(alg_length ? alg_length : 1), sizeof(*stack));
        if (!stack) { errno = ENOMEM; alg_result = INT_MIN; goto alg_cleanup; }
    }
    {
        int alg_length = alg_add(n, 1, &alg_error);
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        if (alg_length < 0 || alg_length > 4000000) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
        state = calloc((size_t)(alg_length ? alg_length : 1), sizeof(*state));
        if (!state) { errno = ENOMEM; alg_result = INT_MIN; goto alg_cleanup; }
    }
    int top = 0;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    int u = 0;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    int phase = 0;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    int count = 0;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    int alg_condition_1 = (root == alg_sub(0, 1, &alg_error));
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (alg_condition_1) {
        alg_result = 0;
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        goto alg_cleanup;
    }
    stack[0] = root;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    top = 1;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    while (1) {
        int alg_condition = (top > 0);
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        if (!alg_condition) break;
        u = stack[alg_sub(top, 1, &alg_error)];
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        phase = state[alg_sub(top, 1, &alg_error)];
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        int alg_condition_2 = (phase == 1);
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        if (alg_condition_2) {
            output[count] = u;
            if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
            count = alg_add(count, 1, &alg_error);
            if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        }
        int alg_condition_3 = (phase == 0);
        if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
        if (alg_condition_3) {
            state[alg_sub(top, 1, &alg_error)] = 1;
            if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
            int alg_condition_4 = (left_child[u] != alg_sub(0, 1, &alg_error));
            if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
            if (alg_condition_4) {
                stack[top] = left_child[u];
                if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
                state[top] = 0;
                if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
                top = alg_add(top, 1, &alg_error);
                if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
            }
        } else {
            int alg_condition_5 = (phase == 1);
            if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
            if (alg_condition_5) {
                state[alg_sub(top, 1, &alg_error)] = 2;
                if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
                int alg_condition_6 = (right_child[u] != alg_sub(0, 1, &alg_error));
                if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
                if (alg_condition_6) {
                    stack[top] = right_child[u];
                    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
                    state[top] = 0;
                    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
                    top = alg_add(top, 1, &alg_error);
                    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
                }
            } else {
                top = alg_sub(top, 1, &alg_error);
                if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
            }
        }
    }
    alg_result = count;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    goto alg_cleanup;
alg_cleanup:
    free(stack);
    free(state);
    return alg_result;
}

int main(void) {
    int left_child[] = {1, -1, -1};
    int right_child[] = {2, -1, -1};
    int root = 0;
    int output[] = {0, 0, 0};
    int result = tree_inorder(left_child, 3, right_child, 3, root, output, 3);
    printf("%d\n", result);
    // Expected output: [1, 0, 2]
    for (int alg_print = 0; alg_print < 3; alg_print++) printf("%d ", output[alg_print]);
    printf("\n");
    if (errno) { perror("algorithm"); return 1; }
    return 0;
}
Nov 15, 2026 C
Algorithms: Tree Algorithms

Iterative Binary Tree Inorder in C++

Inorder traversal visits each binary-tree node once without recursion..

cpp 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stdexcept>
#include <cstdint>
#include <limits>
// Iterative Binary Tree Inorder in C++
//
// PURPOSE
// Inorder traversal visits each binary-tree node once without recursion.
//
// METHOD
// Keep a stack of nodes and visit states. State zero descends left, state one descends
// right, and state two exits. Emit the node at the traversal-specific state.
//
// COMPLEXITY
// O(n) time and O(n) allocated stack space; live stack usage is O(tree height).
//
// CONTRACT
// Parallel left_child and right_child arrays contain -1 or node IDs. root=-1 means empty.
// The structure must be a valid tree, not cyclic or shared. output has n entries; writes
// node IDs and returns visited count.
// Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex
// counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers.
// Sorted order, correct tree topology, and caller-owned data-structure invariants are
// preconditions; checking them on every query would change query complexity.
// Scalar and shape checks are included. Value-range checks are included where needed to
// prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000
// workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python
// uses arbitrary precision. Native allocation failures propagate. In-place outputs may be
// partly updated after arithmetic failure. These are single-threaded, in-memory
// implementations.
//
// LANGUAGE DETAILS
// C++17: const vector references for inputs, mutable references for outputs, RAII workspace,
// standard lower_bound for LIS. Invalid inputs throw invalid_argument; overflow throws
// overflow_error; allocation failure propagates bad_alloc.
//
// EXAMPLE
// Expected return: 3.
// Expected output after call: [1, 0, 2].
// Run: g++ -std=c++17 -O2 example.cpp -o example && ./example
// Tests for this exact source artifact run before publication. The accompanying source
// archive includes unit cases, runtime results, and source hashes.

static int alg_min(int a, int b) { return a < b ? a : b; }
static int alg_max(int a, int b) { return a > b ? a : b; }
static void alg_require(bool valid) { if (!valid) throw std::invalid_argument("invalid algorithm input"); }
static int alg_checked(int64_t v) { if (v < INT32_MIN || v > INT32_MAX) throw std::overflow_error("32-bit result overflow"); return (int)v; }
static int alg_add(int a,int b) { return alg_checked((int64_t)a+b); }
static int alg_sub(int a,int b) { return alg_checked((int64_t)a-b); }
static int alg_mul(int a,int b) { return alg_checked((int64_t)a*b); }
static size_t alg_size(int n) { alg_require(n>=0 && n<=4000000); return (size_t)n; }

int tree_inorder(const std::vector<int>& left_child, const std::vector<int>& right_child, int root, std::vector<int>& output) {
    alg_require(left_child.size() <= 1000000);
    alg_require(right_child.size() <= 1000000);
    alg_require(output.size() <= 1000000);
    int n = (int)left_child.size();
    alg_require(((n >= 0) && (n <= 1000000)));
    alg_require(((int)left_child.size() == n));
    alg_require(((int)right_child.size() == n));
    alg_require(((int)output.size() == n));
    alg_require(((root >= alg_sub(0, 1)) && (root < n)));
    for (int alg_i = 0; alg_i < (int)left_child.size(); alg_i++) {
        int alg_value = left_child[alg_i];
        alg_require(((alg_value >= alg_sub(0, 1)) && (alg_value < n)));
    }
    for (int alg_i = 0; alg_i < (int)right_child.size(); alg_i++) {
        int alg_value = right_child[alg_i];
        alg_require(((alg_value >= alg_sub(0, 1)) && (alg_value < n)));
    }
    std::vector<int> stack(alg_size(alg_add(n, 1)), 0);
    std::vector<int> state(alg_size(alg_add(n, 1)), 0);
    int top = 0;
    int u = 0;
    int phase = 0;
    int count = 0;
    if ((root == alg_sub(0, 1))) {
        return 0;
    }
    stack[0] = root;
    top = 1;
    while ((top > 0)) {
        u = stack[alg_sub(top, 1)];
        phase = state[alg_sub(top, 1)];
        if ((phase == 1)) {
            output[count] = u;
            count = alg_add(count, 1);
        }
        if ((phase == 0)) {
            state[alg_sub(top, 1)] = 1;
            if ((left_child[u] != alg_sub(0, 1))) {
                stack[top] = left_child[u];
                state[top] = 0;
                top = alg_add(top, 1);
            }
        } else {
            if ((phase == 1)) {
                state[alg_sub(top, 1)] = 2;
                if ((right_child[u] != alg_sub(0, 1))) {
                    stack[top] = right_child[u];
                    state[top] = 0;
                    top = alg_add(top, 1);
                }
            } else {
                top = alg_sub(top, 1);
            }
        }
    }
    return count;
}

int main(void) {
    std::vector<int> left_child = {1, -1, -1};
    std::vector<int> right_child = {2, -1, -1};
    int root = 0;
    std::vector<int> output = {0, 0, 0};
    int result = tree_inorder(left_child, right_child, root, output);
    printf("%d\n", result);
    // Expected output: [1, 0, 2]
    for (int alg_print = 0; alg_print < 3; alg_print++) printf("%d ", output[alg_print]);
    printf("\n");
    return 0;
}
Nov 15, 2026 C++
Algorithms: Tree Algorithms

Iterative Binary Tree Inorder in C#

Inorder traversal visits each binary-tree node once without recursion..

csharp 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
using System;
// Iterative Binary Tree Inorder in C#
//
// PURPOSE
// Inorder traversal visits each binary-tree node once without recursion.
//
// METHOD
// Keep a stack of nodes and visit states. State zero descends left, state one descends
// right, and state two exits. Emit the node at the traversal-specific state.
//
// COMPLEXITY
// O(n) time and O(n) allocated stack space; live stack usage is O(tree height).
//
// CONTRACT
// Parallel left_child and right_child arrays contain -1 or node IDs. root=-1 means empty.
// The structure must be a valid tree, not cyclic or shared. output has n entries; writes
// node IDs and returns visited count.
// Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex
// counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers.
// Sorted order, correct tree topology, and caller-owned data-structure invariants are
// preconditions; checking them on every query would change query complexity.
// Scalar and shape checks are included. Value-range checks are included where needed to
// prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000
// workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python
// uses arbitrary precision. Native allocation failures propagate. In-place outputs may be
// partly updated after arithmetic failure. These are single-threaded, in-memory
// implementations.
//
// LANGUAGE DETAILS
// C# / .NET 10: ReadOnlySpan<int> inputs, Span<int> outputs, primitive workspace arrays,
// Array.BinarySearch for LIS, and checked integer arithmetic. Invalid arguments and overflow
// throw exceptions.
//
// EXAMPLE
// Expected return: 3.
// Expected output after call: [1, 0, 2].
// Run: Use Program.cs in a net10.0 console project; dotnet run.
// Tests for this exact source artifact run before publication. The accompanying source
// archive includes unit cases, runtime results, and source hashes.

class Program {
    static void alg_require(bool valid) { if (!valid) throw new ArgumentException("invalid algorithm input"); }
    static int alg_size(int n) { alg_require(n>=0 && n<=4000000); return n; }

    static int tree_inorder(ReadOnlySpan<int> left_child, ReadOnlySpan<int> right_child, int root, Span<int> output) {
        checked {
            int n = left_child.Length;
            alg_require(((n >= 0) && (n <= 1000000)));
            alg_require((left_child.Length == n));
            alg_require((right_child.Length == n));
            alg_require((output.Length == n));
            alg_require(((root >= (-1)) && (root < n)));
            for (int alg_i = 0; alg_i < left_child.Length; alg_i++) {
                int alg_value = left_child[alg_i];
                alg_require(((alg_value >= (-1)) && (alg_value < n)));
            }
            for (int alg_i = 0; alg_i < right_child.Length; alg_i++) {
                int alg_value = right_child[alg_i];
                alg_require(((alg_value >= (-1)) && (alg_value < n)));
            }
            int[] stack = new int[alg_size((n + 1))];
            int[] state = new int[alg_size((n + 1))];
            int top = 0;
            int u = 0;
            int phase = 0;
            int count = 0;
            if ((root == (-1))) {
                return 0;
            }
            stack[0] = root;
            top = 1;
            while ((top > 0)) {
                u = stack[(top - 1)];
                phase = state[(top - 1)];
                if ((phase == 1)) {
                    output[count] = u;
                    count = (count + 1);
                }
                if ((phase == 0)) {
                    state[(top - 1)] = 1;
                    if ((left_child[u] != (-1))) {
                        stack[top] = left_child[u];
                        state[top] = 0;
                        top = (top + 1);
                    }
                } else {
                    if ((phase == 1)) {
                        state[(top - 1)] = 2;
                        if ((right_child[u] != (-1))) {
                            stack[top] = right_child[u];
                            state[top] = 0;
                            top = (top + 1);
                        }
                    } else {
                        top = (top - 1);
                    }
                }
            }
            return count;
        }
    }

    static void Main() {
        int[] left_child = new int[] {1, -1, -1};
        int[] right_child = new int[] {2, -1, -1};
        int root = 0;
        int[] output = new int[] {0, 0, 0};
        int result = tree_inorder(left_child, right_child, root, output);
        Console.WriteLine(result);
        // Expected output: [1, 0, 2]
        Console.WriteLine("[" + string.Join(", ", output) + "]");
    }
}
Nov 15, 2026 csharp