28:null 29:["$","title",null,{"children":"General Tree Data Structures | Jo Wood | Observable"}] 2e:T12d4,

Tree

A general-purpose tree with no restriction on the uniqueness of node values. Supports standard traversals and node-based search. Tree nodes are instances of TreeNode.

`constructor(root?: TreeNode)`

Creates a new Tree with the given root node, or an empty tree if no root is provided.

`root: TreeNode | null`

The root node of the tree, or null if the tree is empty.

`addChild(parent: TreeNode, child: TreeNode): Tree`

Adds the given child node to the specified parent node. If the tree is currently empty, parent becomes the root. Updates the child’s parent reference accordingly.
The parent must belong to this tree unless the tree is empty. The child must be an unattached TreeNode and the operation must not create a cycle.
Returns this tree to support method chaining.
Throws: Error if either argument is missing.

`clear(): Tree`

Removes all nodes from the tree. Returns the tree to support method chaining.

`*[Symbol.iterator](): Iterable<any>`

Returns an iterator over all items in the tree in depth-first pre-order. This provides a convenient way of iterating over all items. For example,
for (const x of tree)
or
[...tree].

`*nodesPreOrder(): Iterable<TreeNode>`

Generator that yields nodes in depth-first pre-order (nodes before children), starting from the root.

`*dfsPreOrder(): Iterable<any>`

Generator that yields node values in depth-first pre-order (node before children), starting from the root.

`*nodesPostOrder(): Iterable<TreeNode>`

Generator that yields nodes in depth-first post-order (children before node), starting from the root.

`*dfsPostOrder(): Iterable<any>`

Generator that yields node values in depth-first post-order (children before node), starting from the root.

`*bfs(): Iterable<any>`

Generator that yields node values in breadth-first order, starting from the root.

`toArray(traversal?: "pre"|"post"|"bfs"): Array<any>`

Returns an array of node values using the specified traversal order. Defaults to breadth-first.
Throws: Error if an unsupported traversal type is specified.

`find(value: any): TreeNode | null`

Returns the first match in depth-first pre-order, or null if not found.

`findAll(value: any): TreeNode[]`

Returns an array of all matches in depth-first pre-order.

`findWhere(predicate: (node: TreeNode) => boolean): TreeNode | null`

Returns the first predicate match in depth-first pre-order, or null if no true predicate match is found.

`toDot(options?: object): HTMLElement`

Generates a GraphViz dot visualization of the tree. Accepts the following options:

rankDir: Layout direction ("TB", "LR", etc.; default: "TB")
scale: Display scale factor (default: 1)
compact: Use compact node style (default: true)
fillClr: Function mapping a node to fill colour (default: () => "white")
labelClr: Function mapping a node to label text colour (default: () => "black")

2f:T753,

TreeNode

A single node in a general tree. Each node stores a value, a reference to its parent and an ordered list of children.

`constructor(value: any)`

Creates a new TreeNode with the given value. Initially has no parent and no children.

`value: any`

Gets or sets the value stored in this node.

`children: TreeNode[]`

An ordered array of this node’s children. While readable, modifications should be via addChild() and removeChild().

`parent: TreeNode | null`

The node’s parent, or null if this is the root node.

`addChild(node: TreeNode): TreeNode`

Adds the given node as a child of this node setting its parent accordingly. Returns this node to support method chaining.

`removeChild(node: TreeNode): TreeNode`

Removes the given child node if present, and clears its parent reference. Returns this node to support method chaining.

`isLeaf(): boolean`

Returns true if the node has no children.

`childValues(): any[]`

Returns an array of this node's children’s values.

30:T1216,

BinaryTree

A general-purpose binary tree with support for traversal, node search, and visualization. No tree balancing is applied. Duplicate node values are allowed.

`constructor(root?: BinaryTreeNode)`

Creates a new BinaryTree with the given root node, or an empty tree if root is null.

`root: BinaryTreeNode | null`

The root node of the tree, or null if the tree is empty.

`setChild(parent: BinaryTreeNode, child: BinaryTreeNode | null, direction?: "L"|"R"): BinaryTree`

Sets the left child (the default) or right child of parent. Passing null removes the child on that side. Direction is case-insensitive. If the tree is empty, parent becomes its root. Returns this tree to support method chaining.
Throws: Error if direction is not code>"L" or "R".

`find(x: any): Array<BinaryTreeNode>`

Returns an array of all matches in depth-first pre-order.

`findWhere(pred: (node: BinaryTreeNode) => boolean): BinaryTreeNode | null`

Returns the first predicate match in depth-first pre-order, or null if no predicate true value is found.

`clear(): BinaryTree`

Clears the tree. Returns this tree to support method chaining.

`*[Symbol.iterator](): Iterable<any>`

Returns an iterator over all items in the tree in depth-first in-order. This provides a convenient way of iterating over all items. For example,
for (const x of tree)
or
[...tree].

`*nodesPreOrder(): Iterable<BinaryTreeNode>`

Generator that yields tree nodes in depth-first pre-order (VLR), starting from the root.

`*dfsPreOrder(): Iterable<any>`

Generator that yields node values in depth-first pre-order (VLR), starting from the root.

`*dfsInOrder(): Iterable<any>`

Generator that yields node values in depth-first in-order (LVR), starting from the root.

`*dfsPostOrder(): Iterable<any>`

Generator that yields node values in depth-first post-order (LRV), starting from the root.

`*bfs(): Iterable<any>`

Generator that yields node values in breadth-first order, starting from the root.

`toArray(traversal?: "in"|"pre"|"post"|"bfs"): Array<any>`

Array of the values in the tree using the specified traversal order, defaulting to breadth-first.
Throws: Error if an unsupported traversal type is given.

`toDot(options?: object): Element`

Generates a GraphViz dot visualization of the tree. Each node is assigned a unique internal ID, allowing duplicate values to be visualized correctly. Accepts the following options:

rankDir: Direction of layout (e.g. "TB", "LR"; default: "TB")
scale: Scale factor for visualization (default: 1)
compact: If true, uses smaller node/edge layout (default: true)
fillClr: Function mapping node to fill colour (default: (node) => "white")
labelClr: Function mapping node to text colour (default: (node) => "black")

31:Tb21,

BinaryTreeNode

A single node within a binary tree. A node can have a value, a parent and left and right child nodes.

`constructor(x: any, left?: BinaryTreeNode | null, right?: BinaryTreeNode | null)`

Creates a new BinaryTreeNode with the given value. Optional left and right child nodes can be provided, in which case they will have their parent set to this node.

`value: any`

Gets or sets the value stored in this node.

`parent: BinaryTreeNode | null`

This node’s parent, or null if this node is the root.

`left: BinaryTreeNode | null`

This node’s left child. While readable, it should only be modified via setLeft().

`right: BinaryTreeNode | null`

This node’s right child. While readable, it should only be modified via setRight().

`leftValue: any`

The value of the left child, or null if no left child exists.

`rightValue: any`

The value of the right child, or null if no right child exists.

`setLeft(node: BinaryTreeNode | null): BinaryTreeNode`

Sets the node’s left child to node. The child's parent is updated to this node. Returns this node to support method chaining.

`setRight(node: BinaryTreeNode | null): BinaryTreeNode`

Sets the node’s right child to node. The child's parent is updated to this node. Returns this node to support method chaining.

`isLeaf(): boolean`

true if the node has no children; otherwise false.

`hasLeft(): boolean`

true if the node has a left child; otherwise false.

`hasRight(): boolean`

true if the node has a right child; otherwise false.

32:[] 2c:{"id":"5bf5df2d35e53b34","slug":"data-structures-tree","title":"General Tree Data Structures","thumbnail":"aa3db03566f2e1d60398732916da6a77c35aaf356e4785aa1bc1142f27eff172","access_level":"public","create_time":"$D2025-07-23T04:45:11.876Z","update_time":"$D2026-09-22T10:10:16.676Z","view_time":null,"first_public_time":"$D2026-09-22T14:23:44.687Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":"starter_2024"},"version":493,"publish_version":493,"role":null,"authored":false,"authors":[{"type":"individual","id":"e2432cc13dc447d3","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":null}],"members":[{"type":"individual","id":"e2432cc13dc447d3","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":null,"role":"editor"},{"type":"team","id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":"starter_2024","role":"viewer"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"cf3a41cde0560514","slug":"data-structures","title":"data structures","owner":{"id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood"}},"type":"notebook","body":{"title":"General Tree Data Structures","cells":[{"id":0,"value":"# General Tree Data Structures","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":5,"value":"## 1. General Tree","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":69,"value":"A _rooted tree_ is a connected, acyclic collection of nodes and edges with one root node. When its edges are directed from parent to child, the root has no parent and every other node has exactly one parent. This implementation represents an ordered general tree: each node may have any number of children, and node values need not be unique.\n\nGeneral trees can be used to model a variety of data relations such as [abstract syntax trees](https://en.wikipedia.org/wiki/Abstract_syntax_tree), file systems or [biological taxonomies](https://en.wikipedia.org/wiki/Taxonomy_%28biology%29).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":7,"value":"Here's an example:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":79,"value":"import {Tree, TreeNode} from \"observable:@jwolondon/adts-and-data-structures\";","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":100,"value":"{\n const myTree = new Tree(new TreeNode(\"ant\"));\n myTree\n .addChild(myTree.find(\"ant\"), new TreeNode(\"bat\"))\n .addChild(myTree.find(\"ant\"), new TreeNode(\"cat\"))\n .addChild(myTree.find(\"bat\"), new TreeNode(\"dog\"))\n .addChild(myTree.find(\"ant\"), new TreeNode(\"eel\"))\n .addChild(myTree.find(\"eel\"), new TreeNode(\"fox\"))\n .addChild(myTree.find(\"eel\"), new TreeNode(\"gnu\"))\n .addChild(myTree.find(\"eel\"), new TreeNode(\"hen\"))\n .addChild(myTree.find(\"eel\"), new TreeNode(\"imp\"))\n .addChild(myTree.find(\"hen\"), new TreeNode(\"jay\"))\n .addChild(myTree.find(\"hen\"), new TreeNode(\"cat\"))\n .addChild(myTree.find(\"hen\"), new TreeNode(\"cat\"));\n display(myTree.toDot({scale: 0.8}));\n}","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":11,"value":"$2e","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":9,"value":"$2f","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":24,"value":"## 2. Binary Tree","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":27,"value":"A [binary tree](https://en.wikipedia.org/wiki/Binary_tree) is a rooted tree in which each node has at most two children, conventionally called the left and right children. Node values need not be unique. The binary structure supports algorithms based on left and right branching that can improve efficiency of various operations.\n\nBinary trees can be used for a variety of applications including [machine learning decision trees](https://medium.com/@Packt_Pub/binary-decision-trees-1ec94cfed208), tournament modelling and expression trees.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":118,"value":"Here's an example that represents the expression `3 + (4 * (2 + 1))` as an abstract syntax tree (AST):","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":121,"value":"import {\n BinaryTree,\n BinaryTreeNode\n} from \"observable:@jwolondon/adts-and-data-structures\";","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":124,"value":"const ast = new BinaryTree(\n new BinaryTreeNode(\n \"+\",\n new BinaryTreeNode(3),\n new BinaryTreeNode(\n \"*\",\n new BinaryTreeNode(4),\n new BinaryTreeNode(\"+\", new BinaryTreeNode(2), new BinaryTreeNode(1))\n )\n )\n);\n\ndisplay(ast.toDot({scale: 0.7}));","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":136,"value":"Here is a recursive evaluator for this binary-expression AST, in which every operator node has exactly two children:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":129,"value":"function evaluate(node) {\n if (node.isLeaf()) {\n return node.value; // All leaf nodes are numbers\n }\n const [left, right] = [evaluate(node.left), evaluate(node.right)];\n switch (node.value) {\n case \"+\":\n return left + right;\n case \"-\":\n return left - right;\n case \"*\":\n return left * right;\n case \"/\":\n return left / right;\n default:\n throw new Error(`Unknown operator: ${node.value}`);\n }\n}","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":140,"value":"evaluate(ast.root)","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":36,"value":"$30","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":38,"value":"$31","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":13,"value":"---\n\n## Appendices","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":15,"value":"_For API doc and page styling:_","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":141,"value":"import {defaultStyle} from \"observable:@jwolondon/utilities-cdt-2026\";","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"import { apiStyle } from \"observable:@jwolondon/data-structure-docs\"","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":143,"value":"defaultStyle()","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"apiStyle()","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W32","stdlib":"2","titling":"auto"}} 2d:"$2c:body"