# inorder-tree-layout

> Index calculations for inorder layout of balanced binary trees

Latest version **1.0.0** (published 2014-04-28) · MIT license · 0 weekly downloads

## Install

```sh
npm install inorder-tree-layout
pnpm add inorder-tree-layout
yarn add inorder-tree-layout
bun add inorder-tree-layout
```

## Health

**Score 15/100 (F)** — status: abandoned.

Positive: no vulnerabilities.

Warnings: low downloads; no types; no esm support.

Negative: abandoned; low maintenance score.

## Facts

| | |
|---|---|
| Version | 1.0.0 |
| Published | 2014-04-28 |
| First published | 2013-04-11 |
| Weekly downloads | 0 |
| License | MIT |
| TypeScript types | none |
| Module format | CommonJS |
| Dependencies | 1 |
| Known vulnerabilities | 0 |
| Install scripts | no |
| GitHub stars | 10 |
| Author | Mikola Lysenko |
| Maintainers | mikolalysenko |
| Keywords | binary, tree, search, balanced, inorder, array, layout, linkless, successor, parent, left, right, child, iteration, index, traversal |

## Links

- npm: https://www.npmjs.com/package/inorder-tree-layout
- Repository: https://github.com/mikolalysenko/inorder-tree-layout
- Issues: https://github.com/mikolalysenko/inorder-tree-layout/issues
- npm.io page: https://npm.io/package/inorder-tree-layout

## Dependencies (1)

- [bit-twiddle](https://npm.io/package/bit-twiddle.md) ~0.0.1

## Alternatives

- [@snazzah/davey](https://npm.io/package/@snazzah/davey.md) — 1.5M weekly downloads
- [@vendure/testing](https://npm.io/package/@vendure/testing.md) — 8.3K weekly downloads
- [vue-simple-context-menu](https://npm.io/package/vue-simple-context-menu.md) — 6.6K weekly downloads
- [cypress-webpack-preprocessor-v5](https://npm.io/package/cypress-webpack-preprocessor-v5.md) — 2.1K weekly downloads
- [@backstage/plugin-catalog-backend-module-puppetdb](https://npm.io/package/@backstage/plugin-catalog-backend-module-puppetdb.md) — 1.3K weekly downloads

## Recent versions

- 1.0.0 (latest) — 2014-04-28
- 0.0.8 — 2013-04-24
- 0.0.7 — 2013-04-22
- 0.0.6 — 2013-04-18
- 0.0.5 — 2013-04-15
- 0.0.4 — 2013-04-15
- 0.0.3 — 2013-04-12
- 0.0.2 — 2013-04-11
- 0.0.1 — 2013-04-11
- 0.0.0 — 2013-04-11

## README

inorder-tree-layout
===================
Operations on nodes for balanced binary trees stored in in-order layout.  These are useful if you are building data structures, like binary search trees, implicitly (ie not storing pointers to subtrees).

## Install

    npm install inorder-tree-layout
    
## Example

Suppose we have a tree with 10 elements, packed in level order.  Then the inorder labelling of this tree looks like the following picture:

```
The tree:

          6
        /   \
       3     8
      / \   / \
     1   5 7   9
    / \  |
   0   2 4

```

Now given this tree, here is how we can compute some queries using this library:

```javascript
var layout = require("inorder-tree-layout")

console.log(layout.left(10, 3))     //Prints:  1

console.log(layout.parent(10, 7))   //Prints:  8

console.log(layout.height(10, 9))   //Prints:  0

```

## API

```javascript
var layout = require("inorder-tree-layout")
```

**Conventions:**

* `n` is always the size of the tree
* `x` is the index of a node in the tree

### `layout.root(n)`
Returns the index of the root of a tree of size n.

### `layout.begin(n)`
Returns the index of the first node of the tree

### `layout.end(n)`
Returns the index of the last node in the tree

### `layout.height(n, x)`
Returns the height of node `x` in a tree of size `n`

### `layout.prev(n, x)`
Returns the predecessor of `x` in an in-order traversal

### `layout.next(n, x)`
Returns the successor of `x` in an in-order traversal

### `layout.parent(n, x)`
Returns the parent of `x` in a tree of size `n`

### `layout.left(n, x)`
Returns the left child of `x`

### `layout.right(n, x)`
Returns the right child of `x`

### `layout.leaf(n, x)`
Returns true if `x` is a leaf node.

### `layout.lo(n, x)`
Returns the left most ancestor of `x` in the tree

### `layout.hi(n, x)`
Returns the right most ancestor of `x` in the tree

# Credits
(c) 2013 Mikola Lysenko. MIT License

---
_Source: https://npm.io/package/inorder-tree-layout · Machine-readable twin of the npm.io package page. Health data is recomputed on every publish._