TreeNode

tree

# Tree

Tree implementations in different programming languages.

tree.dart

import 'dart:collection';
import "dart:core";
import "dart:core" as core show print;

/**
 * Helper for a Node class
 */
class TreeNodeHelpers {
  static int _nodeId = 0;
  static HashMap<int, TreeNode> _nodeList = HashMap();

  static set register(TreeNode node) {
    node._id = _nodeId++;
    _nodeList[node._id] = node;
  }
}

/**
 * Represent Node of a tree
 */
class TreeNode {
  int _id = -1;
  late String _name;
  dynamic _value;
  TreeNode? _parent;
  List<TreeNode> _children = [];

  TreeNode({
    required String name,
    dynamic? value,
    List<TreeNode>? children,
  }) {
    TreeNodeHelpers.register = this;
    this.name = name;
    this.value = value;
    this.children = children ?? [];
  }

  static TreeNode fromObject(Map<String, dynamic> input) {
    final name = input['name'] as String;
    final value = input['value'];
    final children = (input['children'] ?? []) as List;

    // // bottom to top
    // return new TreeNode(
    //   name: name,
    //   value: value,
    //   children: children.map((child) => fromObject(child)).toList(),
    // );

    // top to bottom
    final treeNode = new TreeNode(name: name, value: value, children: []);
    treeNode.children = children.map((child) => fromObject(child)).toList();
    return treeNode;
  }

  dynamic get value {
    return _value;
  }

  set value(dynamic value) {
    _value = value;
  }

  String get name {
    return _name;
  }

  set name(String name) {
    _name = name;
  }

  TreeNode? get parent {
    return _parent;
  }

  set parent(TreeNode? parent) {
    _parent = parent;
  }

  List<TreeNode> get children {
    return _children;
  }

  set children(List<TreeNode> children) {
    for (final child in children) {
      child.parent = this;
      _children.add(child);
    }
  }

  // List<dynamic> get tree {
  //   return [{_id: value}, ...children.map((child) => child.tree).toList()];
  // }

  List<TreeNode> get ancestors {
    final list = <TreeNode>[];
    if (parent != null) list.addAll([parent!, ...parent!.ancestors]);
    return list;
  }

  bool get isLastChild {
    if (parent == null) return true;
    final myIndex = parent!.children.indexOf(this);
    return parent!.children.length == myIndex + 1;
  }

  /**
   * reverse the order of children
   */
  void invert() {
    _children = _children.reversed.toList();
    for (final child in children) {
      child.invert();
    }
  }

  /**
   * helps with conditions
   * @returns {*} value of node
   */
  dynamic valueOf() {
    return _value;
  }

  /**
   * cast to string
   * @returns {string}
   */
  String toString() {
    return '$_id\_$name: ${value ?? null} [$children]';
  }

  /**
   * Print Tree
   */
  void print() {
    final nodes =
        [this, ...ancestors].sublist(0, ancestors.length).reversed.toList();

    final line = nodes.map((node) {
      if (identical(this, node)) return isLastChild ? '└─' : '├─';
      return node.isLastChild ? '  ' : '│ ';
    }).toList();

    // line.add('$_id:$name');
    line.add('$name - $_id');
    core.print(line.join(" "));

    for (final child in children) {
      child.print();
    }
  }
}

void main() {
  final tree = TreeNode.fromObject({
    'name': '#',
    'value': 'root',
    'children': [
      {
        'name': 'A',
        'value': '1',
        'children': [
          {
            'name': 'A1',
            'value': '1.1',
            'children': [
              {'name': 'A1.1', 'value': '1.1.1', 'children': []}
            ]
          },
        ],
      },
      {
        'name': 'B',
        'value': '2',
        'children': [
          {
            'name': 'B1',
            'value': '2.1',
            'children': [
              {'name': 'B1.1', 'value': '2.1.1', 'children': []},
              {
                'name': 'B1.2',
                'value': '2.1.2',
                'children': [
                  {'name': 'B1.2.1', 'value': '2.1.2.1', 'children': []},
                  {'name': 'B1.2.2', 'value': '2.1.2.2', 'children': []},
                  {'name': 'B1.2.3', 'value': '2.1.2.3', 'children': []},
                ],
              },
              {'name': 'B1.3', 'value': '2.1.3', 'children': []},
            ],
          },
          {'name': 'B2', 'value': '2.2', 'children': []},
          {'name': 'B3', 'value': '2.3', 'children': []},
        ],
      },
      {
        'name': 'C',
        'value': '3',
        'children': List.generate(2, (index1) {
          return {
            'name': 'C${index1 + 1}',
            'value': '3.${index1 + 1}',
            'children': List.generate(2, (index2) {
              return {
                'name': 'C${index1 + 1}.${index2 + 1}',
                'value': '3.${index1 + 1}.${index2 + 1}',
                'children': List.generate(2, (index3) {
                  return {
                    'name': 'C${index1 + 1}.${index2 + 1}.${index3 + 1}',
                    'value': '3.${index1 + 1}.${index2 + 1}.${index3 + 1}',
                    'children': [],
                  };
                }),
              };
            }),
          };
        }),
      },
    ],
  });

  // core.print(TreeNodeHelpers._nodeList);
  // core.print(tree.children[1].children[0].children[0].ancestors);
  // tree.children[2].print();
  // tree.invert();
  tree.print();
  core.print('Total Nodes: ${TreeNodeHelpers._nodeList.length}');
}

tree.ts

#!/usr/bin/env vite-node --script

/**
 * Helper for a Node class
 */
class TreeNodeHelpers {
  static _nodeId = 0;
  static _nodeList = new Map<number, TreeNode>();

  static set register(node: TreeNode) {
    node._id = this._nodeId++;
    this._nodeList.set(node._id, node);
  }
}

type TreeNodeJSON = {
  name: string;
  value?: unknown;
  children?: TreeNodeJSON[];
};

/**
 * Represent Node of a tree
 */
class TreeNode {
  _id = -1;
  private _name: string = "";
  private _value: unknown = undefined;
  private _parent?: TreeNode = undefined;
  private _children: TreeNode[] = [];

  constructor(params: { name: string; value?: unknown; children?: TreeNode[] }) {
    TreeNodeHelpers.register = this;
    this.name = params.name;
    this.value = params.value;
    this.children = params.children ?? [];
  }

  static fromObject(input: TreeNodeJSON) {
    const { name, value, children = [] } = input;

    // // bottom to top
    // return new TreeNode({
    //   name,
    //   value,
    //   children: children.map((child) => TreeNode.fromObject(child)),
    // });

    // top to bottom
    const treeNode = new TreeNode({ name, value, children: [] });
    treeNode.children = children.map((child) => TreeNode.fromObject(child));
    return treeNode;
  }

  get value() {
    return this._value;
  }

  set value(value) {
    this._value = value;
  }

  get name() {
    return this._name;
  }

  set name(name) {
    this._name = name;
  }

  get parent() {
    return this._parent;
  }

  set parent(parent) {
    this._parent = parent;
  }

  get children() {
    return this._children;
  }

  set children(children: TreeNode[]) {
    for (const child of children) {
      child.parent = this;
      this._children.push(child);
    }
  }

  // get tree(): any[] {
  //   return [{ [this._id]: this.value }, this.children.map((child) => child.tree)];
  // }

  get ancestors() {
    const list: TreeNode[] = [];
    if (this.parent) list.push(this.parent, ...this.parent.ancestors);
    return list;
  }

  get isLastChild() {
    if (!this.parent) return true;
    const myIndex = this.parent.children.indexOf(this);
    return this.parent.children.length === myIndex + 1;
  }

  /**
   * reverse the order of children
   */
  invert() {
    this._children = this._children.reverse();
    for (const child of this.children) {
      child.invert();
    }
  }

  /**
   * helps with conditions
   * @returns {*} value of node
   */
  valueOf() {
    return this._value;
  }

  /**
   * cast to string
   * @returns {string}
   */
  toString() {
    return `${this._id}_${this.name}: ${this.value ?? null} [${this.children}]`;
  }

  /**
   * Print Tree
   */
  print() {
    const nodes = [this, ...this.ancestors].slice(0, this.ancestors.length).reverse();

    const line: string[] = nodes.map((node) => {
      if (this === node) return this.isLastChild ? "└─" : "├─";
      return node.isLastChild ? "  " : "│ ";
    });
    // line.push(`${this._id}:${this.name}`);
    line.push(`${this.name} - ${this._id}`);
    console.log(line.join(" "));

    for (const child of this.children) {
      child.print();
    }
  }
}

function main() {
  const tree = TreeNode.fromObject({
    name: "#",
    value: "root",
    children: [
      {
        name: "A",
        value: "1",
        children: [
          {
            name: "A1",
            value: "1.1",
            children: [{ name: "A1.1", value: "1.1.1", children: [] }],
          },
        ],
      },
      {
        name: "B",
        value: "2",
        children: [
          {
            name: "B1",
            value: "2.1",
            children: [
              { name: "B1.1", value: "2.1.1", children: [] },
              {
                name: "B1.2",
                value: "2.1.2",
                children: [
                  { name: "B1.2.1", value: "2.1.2.1", children: [] },
                  { name: "B1.2.2", value: "2.1.2.2", children: [] },
                  { name: "B1.2.3", value: "2.1.2.3", children: [] },
                ],
              },
              { name: "B1.3", value: "2.1.3", children: [] },
            ],
          },
          { name: "B2", value: "2.2", children: [] },
          { name: "B3", value: "2.3", children: [] },
        ],
      },
      {
        name: "C",
        value: "3",
        children: new Array(2).fill(undefined).map(function (_, index1) {
          return {
            name: `C${index1 + 1}`,
            value: `3.${index1 + 1}`,
            children: new Array(2).fill(undefined).map(function (_, index2) {
              return {
                name: `C${index1 + 1}.${index2 + 1}`,
                value: `3.${index1 + 1}.${index2 + 1}`,
                children: new Array(2).fill(undefined).map(function (_, index3) {
                  return {
                    name: `C${index1 + 1}.${index2 + 1}.${index3 + 1}`,
                    value: `3.${index1 + 1}.${index2 + 1}.${index3 + 1}`,
                    children: [],
                  };
                }),
              };
            }),
          };
        }),
      },
    ],
  });

  // console.log(TreeNodeHelpers._nodeList);
  // console.log(tree.children[1].children[0].children[0].ancestors);
  // tree.children[2].print();
  // tree.invert();
  tree.print();
  console.log("Total Nodes:", TreeNodeHelpers._nodeList.size);
}

main();