BST In-Order Traversal — VisualAlgorithms Docs

How it works

Traverse a binary search tree left-root-right with an explicit stack to emit keys in sorted order.

Implementation

      
 function bstInorderOp(state) {
  const keys = state.keys;
  const left = state.left;
  const right = state.right;
  const stack = [];
  let current = state.root;
  while (current !== -1 || stack.length > 0) {
    while (current !== -1) {
      visitNode(current);
      stack[stack.length] = current;
      current = left[current];
    }
    current = stack[stack.length - 1];
    stack.length = stack.length - 1;
    traverseNode(current);
    current = right[current];
  }
  finish();
} def bstInorderOp(state):
    keys = state.keys
    left = state.left
    right = state.right
    stack = []
    current = state.root
    while ((current != -1) or (stack.length > 0)):
        while (current != -1):
            visitNode(current)
            stack[stack.length] = current
            current = left[current]
        current = stack[(stack.length - 1)]
        stack.length = (stack.length - 1)
        traverseNode(current)
        current = right[current]
    finish() #include <vector>
#include <algorithm>
void bstInorderOp(int state) {
    auto keys = state.keys;
    auto left = state.left;
    auto right = state.right;
    auto stack = [];
    auto current = state.root;
    while(((current != -1) || (stack.length > 0))) {
        while((current != -1)) {
            visitNode(current);
            stack[stack.length] = current;
            current = left[current];
        }
        current = stack[(stack.length - 1)];
        stack.length = (stack.length - 1);
        traverseNode(current);
        current = right[current];
    }
    finish();
} public void bstInorderOp(int state) {
    var keys = state.keys;
    var left = state.left;
    var right = state.right;
    var stack = [];
    var current = state.root;
    while(((current != -1) || (stack.length > 0))) {
        while((current != -1)) {
            visitNode(current);
            stack[stack.length] = current;
            current = left[current];
        }
        current = stack[(stack.length - 1)];
        stack.length = (stack.length - 1);
        traverseNode(current);
        current = right[current];
    }
    finish();
} #include <stdio.h>
void bstInorderOp(int state) {
    var keys = state.keys;
    var left = state.left;
    var right = state.right;
    var stack = [];
    var current = state.root;
    while(((current != -1) || (stack.length > 0))) {
        while((current != -1)) {
            visitNode(current);
            stack[stack.length] = current;
            current = left[current];
        }
        current = stack[(stack.length - 1)];
        stack.length = (stack.length - 1);
        traverseNode(current);
        current = right[current];
    }
    finish();
} 