#include <iostream>

void traverse_leftmost(int& curr, int len) {
  while (true) {
    // Note: (curr * 2 + 1) is the left child of curr.
    int next = curr * 2 + 1;
    if (next >= len) break;
    curr = next;
  }
}

void inorder(int a[], int len) {
  if (len == 0) return;
  int curr = 0;
  traverse_leftmost(curr, len);

  while(true) {
    printf("%d ", a[curr]);
    // Note: (curr * 2 + 2) is the right child of curr.
    int right_child = curr * 2 + 2;
    if (right_child < len) {
      // Case 1: If a right child exists, travers to right child's leftmost
      // descendant.
      curr = right_child;
      traverse_leftmost(curr, len);
    } else if (curr % 2 == 1) {
      // Case 2: No right child. Curr is a left child. Simply traverse to
      // parent node.
      curr /= 2;
    } else {
      if (curr == 0) {
        // If the root node has no right child. Terminate.
        printf("\n");
        return;
      }
      // Case 3: No right child. Curr is a right child. Keep traversing to
      // parent level until curr is not a right child.
      while (curr % 2 == 0) {
        curr = (curr - 2) / 2;
        if (curr == 0) {
          // If going back to root node from a right child, terminate.
          printf("\n");
          return;
        }
      }
      curr /= 2;
    }
  }
}

int main() {
  int len = 6;
  int input[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  inorder(input, 0);
  inorder(input, 1);
  inorder(input, 2);
  inorder(input, 3);
  inorder(input, 4);
  inorder(input, 5);
  inorder(input, 6);
  inorder(input, 7);
  inorder(input, 8);
}